关于算法-数据结构:二叉树的四种遍历方式

1.二叉树的遍历算法
1.1三种遍历示例

先序遍历：ABCDEFGH
中序遍历：CBEDFAHG
后续遍历：CEFDBHGA

能够用如下形式进行遍历：假设有个指针p沿着图中蓝色箭头游历整个二叉树。标号1示意第一次通过节点，2示意第二次通过节点，3示意第三次通过节点，别离对应了前序遍历（1）、中序遍历（2）、后序遍历（3）的后果：

1.2二叉树的存储构造:

struct BTNode {
      int val;
      TreeNode *lchild;
      TreeNode *rchild;
  };

1.3先序遍历

void preorder(BTNode *p){
    if(p!=null){
        Visit(p);//能够是打印
        preorder(p->lchild);//先序遍历左子树
        preorder(p->lchild);//先序遍历右子树
    }
}

1.4中序遍历

void inorder(BTNode *p){
    if(p!=null){
        preorder(p->lchild);
        Visit(p);
        preorder(p->lchild);
    }
}

1.5后序遍历

void postorder(BTNode *p){
    if(p!=null){
        preorder(p->lchild);
        preorder(p->lchild);
        Visit(p);
    }
}

2.档次遍历

要进行档次遍历，须要创立一个循环队列。先将二叉树头节点入队列，而后出队列，拜访该节点，如果它有左子树，左子树入队；如果它有右子树，右子树入队。而后出队，对出队节点拜访，如此重复，直到队列为空为止。

void level(BTNode *p){
    int front=0,rear=0;
    BTNode *que[maxSize];
    BTNode *p;
    if(p!=Null){
        rear=(rear+1)%maxSize;
        que[rear]=p;//根节点入队
        while(front!=rear){//队列非空
            front=(front+1)%maxSize;
            q=que[front];//队头出队
            Visit(q);//访问队头
            if(q->lchild!=Null){//左子树非空
                rear=(rear+1)%maxSize;//左子树入队
                que[rear]=q->lchild;
            }
            if(q->rchild!=Null){//右子树非空
                rear=(rear+1)%maxSize;//右子树入队
                que[rear]=q->rchild;
            }
        }
    }
}