二叉树的前中后和层序遍历详细图解（递归和非递归写法）

vlambda
2021-03-09

二叉树的前中后和层序遍历详细图解（递归和非递归写法）

遍历一棵二叉树常用的有四种方法，前序（PreOrder）、中序（InOrder）、后序（PastOrder）还有层序（LevelOrder）。

前中后序三种遍历方式都是以根节点相对于它的左右孩子的访问顺序定义的。

四种遍历的思想：

前序遍历：根节点 -> 左子树 -> 右子树（根左右）

中序遍历：左子树 -> 根结点 -> 右子树（左根右）

后序遍历：左子树 -> 右子树 -> 根结点（左右根）

层序遍历：从根开始一层层从左到右遍历即可。

树的前中后序遍历是个递归的定义，在遍历到根节点的左/右子树时，也要遵循前/中/后序遍历的顺序，例如下面这棵树：

前序遍历：ABDECFG

中序遍历：DBEAFCG

后序遍历：DEBFGCA

层序遍历：ABCDEFG

————————————————

二叉树的前中后和层序遍历详细图解（递归和非递归写法）

前序遍历

遍历结果：ABDHEIJCFGK

中序遍历

遍历结果：DHBIEJAFCKG

后序遍历

遍历结果：HDIJEBFKGCA

层序遍历

遍历结果：ABCDEFGHIJK

二叉树的每个结点最多有两个子树（即不存在度大于2的结点），二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。

二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：


  
    
    
   
   typedef struct BinaryTreeNode{ 
    int data; 
    struct BinaryTreeNode *lchild,*rchild; 
   };

二叉树的创建：


  
    
    
   
   //按先序序列创建二叉树 
   int CreateBiTree(BiTree &T){ 
    char data; 
    //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树 
    scanf("%c",&data); 
    if(data == '#'){ 
    T = NULL; 
    } 
    else{ 
    T = new BinaryTreeNode(); 
    //生成根结点 
    T->data = data; 
    //构造左子树 
    CreateBiTree(T->lchild); 
    //构造右子树 
    CreateBiTree(T->rchild); 
    } 
    return 0; 
   }

二叉树的遍历，前序，中序，后序的递归算法：


  
    
    
   
   //输出 
   void Visit(BinaryTree T){ 
    if(T->data != '#'){ 
    cout<<T->data; 
    } 
   } 
   //前序遍历 
   void PreOrder(BiTree T){ 
    if(T != NULL){ 
    //访问根节点 
    Visit(T); 
    //访问左子结点 
    PreOrder(T->lchild); 
    //访问右子结点 
    PreOrder(T->rchild); 
    } 
   } 
   //中序遍历 
   void InOrder(BinaryTree T){ 
    if(T != NULL){ 
    //访问左子结点 
    InOrder(T->lchild); 
    //访问根节点 
    Visit(T); 
    //访问右子结点 
    InOrder(T->rchild); 
    } 
   } 
   //后序遍历 
   void PostOrder(BinaryTree T){ 
    if(T != NULL){ 
    //访问左子结点 
    PostOrder(T->lchild); 
    //访问右子结点 
    PostOrder(T->rchild); 
    //访问根节点 
    Visit(T); 
    } 
   }

二叉树的遍历的递归算法很简单，非递归算法稍微复杂一点，下面我们来逐个分析一下：

（1）前序遍历

【思路】：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。


  
    
    
   
   //先序遍历(非递归) 
   void PreOrder2(BinaryTree T){ 
    stack<BinaryTree> stack; 
    //p是遍历指针 
    BinaryTree p = T; 
    //栈不空或者p不空时循环 
    while(p || !stack.empty()){ 
    if(p != NULL){ 
    //存入栈中 
    stack.push(p); 
    //访问根节点 
    cout<<p->data; 
    //遍历左子树 
    p = p->lchild; 
    } 
    else{ 
    //退栈 
    p = stack.top(); 
    stack.pop(); 
    //访问右子树 
    p = p->rchild; 
    } 
    }//while 
   }

（2）中序遍历

【思路】：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。


  
    
    
   
   void InOrder2(BinaryTree T){ 
    stack<BinaryTree> stack; 
    //p是遍历指针 
    BinaryTree p = T; 
    //栈不空或者p不空时循环 
    while(p || !stack.empty()){ 
    if(p != NULL){ 
    //存入栈中 
    stack.push(p); 
    //遍历左子树 
    p = p->lchild; 
    } 
    else{ 
    //退栈，访问根节点 
    p = stack.top(); 
    cout<<p->data; 
    stack.pop(); 
    //访问右子树 
    p = p->rchild; 
    } 
    }//while 
   }

（3）后序遍历

【思路】：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。


  
    
    
   
   //后序遍历(非递归) 
   typedef struct BiTNodePost{ 
    BiTree biTree; 
    char tag; 
   }BiTNodePost,*BiTreePost; 
   void PostOrder2(BinaryTree T){ 
    stack<BiTreePost> stack; 
    //p是遍历指针 
    BinaryTree p = T; 
    BiTreePost BT; 
    //栈不空或者p不空时循环 
    while(p != NULL || !stack.empty()){ 
    //遍历左子树 
    while(p != NULL){ 
    BT = new BiTreePost(); 
    BT->biTree = p; 
    //访问过左子树 
    BT->tag = 'L'; 
    stack.push(BT); 
    p = p->lchild; 
    } 
    //左右子树访问完毕访问根节点 
    while(!stack.empty() && (stack.top())->tag == 'R'){ 
    BT = stack.top(); 
    //退栈 
    stack.pop(); 
    BT->biTree; 
    cout<<BT->biTree->data; 
    } 
    //遍历右子树 
    if(!stack.empty()){ 
    BT = stack.top(); 
    //访问过右子树 
    BT->tag = 'R'; 
    p = BT->biTree; 
    p = p->rchild; 
    } 
    }//while 
   }

（4）层次遍历

【思路】：按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。


  
    
    
   
   //层次遍历 
   void LevelOrder(BinaryTree T){ 
    BinaryTree p = T; 
    //队列 
    queue<BinaryTree> queue; 
    //根节点入队 
    queue.push(p); 
    //队列不空循环 
    while(!queue.empty()){ 
    //对头元素出队 
    p = queue.front(); 
    //访问p指向的结点 
    cout<<p->data; 
    //退出队列 
    queue.pop(); 
    //左子树不空，将左子树入队 
    if(p->lchild != NULL){ 
    queue.push(p->lchild); 
    } 
    //右子树不空，将右子树入队 
    if(p->rchild != NULL){ 
    queue.push(p->rchild); 
    } 
    } 
   }

测试用例：

输入：

ABC##DE#G##F###

输出：

代码：


  
    
    
   
   #include<iostream> 
   #include<stack> 
   #include<queue> 
   using namespace std; 
   //二叉树结点 
   typedef struct BiTNode{ 
    //数据 
    char data; 
    //左右孩子指针 
    struct BiTNode *lchild,*rchild; 
   }BiTNode,*BiTree; 
   //按先序序列创建二叉树 
   int CreateBiTree(BiTree &T){ 
    char data; 
   //按先序次序输入二叉树中结点的值(一个字符),'#'表示空树 
    scanf("%c",&data); 
    if(data == '#'){ 
    T = NULL; 
    } 
    else{ 
    T = (BiTree)malloc(sizeof(BiTNode)); 
    //生成根结点 
    T->data = data; 
    //构造左子树 
    CreateBiTree(T->lchild); 
    //构造右子树 
    CreateBiTree(T->rchild); 
    } 
    return 0; 
   } 
   //输出 
   void Visit(BiTree T){ 
    if(T->data != '#'){ 
    printf("%c ",T->data); 
    } 
   } 
   //先序遍历 
   void PreOrder(BiTree T){ 
    if(T != NULL){ 
    //访问根节点 
    Visit(T); 
    //访问左子结点 
    PreOrder(T->lchild); 
    //访问右子结点 
    PreOrder(T->rchild); 
    } 
   } 
   //中序遍历 
   void InOrder(BiTree T){ 
   if(T != NULL){ 
   //访问左子结点 
   InOrder(T->lchild); 
   //访问根节点 
   Visit(T); 
   //访问右子结点 
   InOrder(T->rchild); 
   } 
   } 
   //后序遍历 
   void PostOrder(BiTree T){ 
    if(T != NULL){ 
    //访问左子结点 
    PostOrder(T->lchild); 
    //访问右子结点 
    PostOrder(T->rchild); 
    //访问根节点 
    Visit(T); 
    } 
   } 
   /* 先序遍历(非递归) 
    思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 
   */ 
   void PreOrder2(BiTree T){ 
    stack<BiTree> stack; 
    //p是遍历指针 
    BiTree p = T; 
    //栈不空或者p不空时循环 
    while(p || !stack.empty()){ 
    if(p != NULL){ 
    //存入栈中 
    stack.push(p); 
    //访问根节点 
    printf("%c ",p->data); 
    //遍历左子树 
    p = p->lchild; 
    } 
    else{ 
    //退栈 
    p = stack.top(); 
    stack.pop(); 
    //访问右子树 
    p = p->rchild; 
    } 
    }//while 
   } 
   /* 中序遍历(非递归) 
    思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 
    先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 
   */ 
   void InOrder2(BiTree T){ 
    stack<BiTree> stack; 
    //p是遍历指针 
    BiTree p = T; 
    //栈不空或者p不空时循环 
    while(p || !stack.empty()){ 
    if(p != NULL){ 
    //存入栈中 
    stack.push(p); 
    //遍历左子树 
    p = p->lchild; 
    } 
    else{ 
    //退栈，访问根节点 
    p = stack.top(); 
    printf("%c ",p->data); 
    stack.pop(); 
    //访问右子树 
    p = p->rchild; 
    } 
    }//while 
   } 
   //后序遍历(非递归) 
   typedef struct BiTNodePost{ 
    BiTree biTree; 
    char tag; 
   }BiTNodePost,*BiTreePost; 
   void PostOrder2(BiTree T){ 
    stack<BiTreePost> stack; 
    //p是遍历指针 
    BiTree p = T; 
    BiTreePost BT; 
    //栈不空或者p不空时循环 
    while(p != NULL || !stack.empty()){ 
    //遍历左子树 
    while(p != NULL){ 
    BT = (BiTreePost)malloc(sizeof(BiTNodePost)); 
    BT->biTree = p; 
    //访问过左子树 
    BT->tag = 'L'; 
    stack.push(BT); 
    p = p->lchild; 
    } 
    //左右子树访问完毕访问根节点 
   while(!stack.empty() && (stack.top())->tag == 'R'){ 
    BT = stack.top(); 
    //退栈 
    stack.pop(); 
    BT->biTree; 
    printf("%c ",BT->biTree->data); 
    } 
    //遍历右子树 
    if(!stack.empty()){ 
    BT = stack.top(); 
    //访问过右子树 
    BT->tag = 'R'; 
    p = BT->biTree; 
    p = p->rchild; 
    } 
    }//while 
   } 
   //层次遍历 
   void LevelOrder(BiTree T){ 
    BiTree p = T; 
    //队列 
    queue<BiTree> queue; 
    //根节点入队 
    queue.push(p); 
    //队列不空循环 
    while(!queue.empty()){ 
    //对头元素出队 
    p = queue.front(); 
    //访问p指向的结点 
    printf("%c ",p->data); 
    //退出队列 
    queue.pop(); 
    //左子树不空，将左子树入队 
    if(p->lchild != NULL){ 
    queue.push(p->lchild); 
    } 
    //右子树不空，将右子树入队 
    if(p->rchild != NULL){ 
    queue.push(p->rchild); 
    } 
    } 
   } 
   int main() 
   { 
    BiTree T; 
    CreateBiTree(T); 
    printf("先序遍历：\n"); 
    PreOrder(T); 
    printf("\n"); 
    printf("先序遍历(非递归)：\n"); 
    PreOrder2(T); 
    printf("\n"); 
    printf("中序遍历：\n"); 
    InOrder(T); 
    printf("\n"); 
    printf("中序遍历(非递归)：\n"); 
    InOrder2(T); 
    printf("\n"); 
    printf("后序遍历：\n"); 
    PostOrder(T); 
    printf("\n"); 
    printf("后序遍历(非递归)：\n"); 
    PostOrder2(T); 
    printf("\n"); 
    printf("层次遍历：\n"); 
    LevelOrder(T); 
    printf("\n"); 
   return 0; 
   }

原文链接：

https://blog.csdn.net/monster_ii/article/details/82115772

https://blog.csdn.net/wilson1068/article/details/88409758

https://blog.csdn.net/zhouwei1221q/article/details/45506149

https://blog.csdn.net/sjf0115/article/details/8645991

vlambda博客
学习文章列表