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

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;
            }
        }
    }
}