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

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