首页 > 代码库 > 二叉树的遍历

二叉树的遍历

2024-09-14 22:45:09   271人阅读

二叉树的遍历有三种方式，例如以下：

（1）前序遍历（DLR）。首先訪问根结点。然后遍历左子树。最后遍历右子树。简记根-左-右。

（2）中序遍历（LDR），首先遍历左子树，然后訪问根结点。最后遍历右子树。

简记左-根-右。

（3）后序遍历（LRD），首先遍历左子树。然后遍历右子树。最后訪问根结点。简记左-右-根。 

 技术分享

例1：如上图所看到的的二叉树，若按前序遍历，则其输出序列为      。若按中序遍历，则其输出序列为      。若按后序遍历，则其输出序列为      。

前序：根A。A的左子树B，B的左子树没有，看右子树。为D，所以A-B-D。再来看A的右子树。根C，左子树E。E的左子树F，E的右子树G，G的左子树为H，没有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH

中序：先訪问根的左子树,B没有左子树。其有右子树D，D无左子树。以下訪问树的根A。连起来是BDA。

再訪问根的右子树，C的左子树的左子树是F，F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左子树结束。找到根C，无右子树。结束。连起来是FEHGC, 中序结果连起来是BDAFEHGC

后序：B无左子树，有右子树D，再到根B。

再看右子树，最以下的左子树是F，其根的右子树的左子树是H。再到H的根G。再到G的根E。E的根C无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA

例2:有下列二叉树，对此二叉树前序遍历的结果为（    ）。

技术分享

A）ACBEDGFH                                          B）ABDGCEHF

C）HGFEDCBA                                          D）ABCDEFGH

解析：先根A，左子树先根B，B无左子树，其右子树。先根D。在左子树G。连起来是ABDG。

A的右子树，先根C。C左子树E。E无左子树，有右子树为H，C的右子树仅仅有F，连起来是CEHF。

整个连起来是B答案 ABDGCEHF。

 

例3：已知二叉树后序遍历是DABEC。中序遍历序列是DEBAC，它的前序遍历序列是(       )  。

A）CEDBA  B）ACBED C）DECAB D）DEABC

解析：由后序遍历可知。C为根结点。由中序遍历可知，C左边的是左子树含DEBA，C右边无结点，知根结点无右子树。先序遍历先訪问根C，答案中仅仅有A以C开头，为正确答案。

后序遍历是DABEC，中序遍历序列是DEBAC

由后序遍历可知C为根节点，在看中序遍历最后也是C，则该树根节点没有右子树。
在由后序遍历倒数第二个为E，则根节点的左子树节点是E。综合2个遍历，第一个都是D。则D是最左子树。由此可知，结构是
                      C
                  E
             D       B
                             A

 

例4：  例如以下二叉树中序遍历的结果是（　　）。

技术分享

A). ACBDFEG  B). ACBDFGE  C).ABDCGEF  D).FCADBEG

解析:首先中序遍历根F会把左右子树分开。F不会在答案的开头和结尾。排除C和D。

在看F的右子树。G是E的右子树。中序遍历先訪问E，再訪问G。E在G前面，排除B。答案为A。

 

例5：例如以下二叉树后序遍历的结果是（　　）。

技术分享

A)  ABCDEF  B) DBEAFC  C)ABDECF  D)DEBFCA

解析：后序的最后一个必须是二叉树的根。高速推断答案为D。


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

[cpp] view plaincopy
  1. //二叉树结点  
  2. typedef struct BiTNode{  
  3.     //数据  
  4.     char data;  
  5.     //左右孩子指针  
  6.     struct BiTNode *lchild,*rchild;  
  7. }BiTNode,*BiTree;  


二叉树的创建：

通过读入一个字符串，建立二叉树的算法例如以下：

[cpp] view plaincopy
  1. //按先序序列创建二叉树  
  2. int CreateBiTree(BiTree &T){  
  3.     char data;  
  4.     //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树  
  5.     scanf("%c",&data);  
  6.     if(data == ‘#‘){  
  7.         T = NULL;  
  8.     }  
  9.     else{  
  10.         T = (BiTree)malloc(sizeof(BiTNode));  
  11.         //生成根结点  
  12.         T->data = data;  
  13.         //构造左子树  
  14.         CreateBiTree(T->lchild);  
  15.         //构造右子树  
  16.         CreateBiTree(T->rchild);  
  17.     }  
  18.     return 0;  
  19. }  

二叉树的遍历：

遍历是对树的一种最主要的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的全部结点，使每个结点都被訪问一次，并且仅仅被訪问一次。因为二叉树是非线性结构，因此。树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。


递归算法：

[cpp] view plaincopy
  1. //输出  
  2. void Visit(BiTree T){  
  3.     if(T->data != ‘#‘){  
  4.         printf("%c ",T->data);  
  5.     }  
  6. }  
  7. //先序遍历  
  8. void PreOrder(BiTree T){  
  9.     if(T != NULL){  
  10.         //訪问根节点  
  11.         Visit(T);  
  12.         //訪问左子结点  
  13.         PreOrder(T->lchild);  
  14.         //訪问右子结点  
  15.         PreOrder(T->rchild);  
  16.     }  
  17. }  
  18. //中序遍历  
  19. void InOrder(BiTree T){  
  20.     if(T != NULL){  
  21.         //訪问左子结点  
  22.         InOrder(T->lchild);  
  23.         //訪问根节点  
  24.         Visit(T);  
  25.         //訪问右子结点  
  26.         InOrder(T->rchild);  
  27.     }  
  28. }  
  29. //后序遍历  
  30. void PostOrder(BiTree T){  
  31.     if(T != NULL){  
  32.         //訪问左子结点  
  33.         PostOrder(T->lchild);  
  34.         //訪问右子结点  
  35.         PostOrder(T->rchild);  
  36.         //訪问根节点  
  37.         Visit(T);  
  38.     }  
  39. }  

非递归算法：

<1>先序遍历：

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


[cpp] view plaincopy
  1. /* 先序遍历(非递归) 
  2.    思路：訪问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T。出栈，再先序遍历T的右子树。 
  3. */  
  4. void PreOrder2(BiTree T){  
  5.     stack<BiTree> stack;  
  6.     //p是遍历指针  
  7.     BiTree p = T;  
  8.     //栈不空或者p不空时循环  
  9.     while(p || !stack.empty()){  
  10.         if(p != NULL){  
  11.             //存入栈中  
  12.             stack.push(p);  
  13.             //訪问根节点  
  14.             printf("%c ",p->data);  
  15.             //遍历左子树  
  16.             p = p->lchild;  
  17.         }  
  18.         else{  
  19.             //退栈  
  20.             p = stack.top();  
  21.             stack.pop();  
  22.             //訪问右子树  
  23.             p = p->rchild;  
  24.         }  
  25.     }//while  
  26. }  


<2>中序遍历

【思路】：T是要遍历树的根指针。中序遍历要求在遍历完左子树后。訪问根。再遍历右子树。


         先将T入栈，遍历左子树。遍历完左子树返回时，栈顶元素应为T，出栈。訪问T->data，再中序遍历T的右子树。

[cpp] view plaincopy
  1. void InOrder2(BiTree T){  
  2.     stack<BiTree> stack;  
  3.     //p是遍历指针  
  4.     BiTree p = T;  
  5.     //栈不空或者p不空时循环  
  6.     while(p || !stack.empty()){  
  7.         if(p != NULL){  
  8.             //存入栈中  
  9.             stack.push(p);  
  10.             //遍历左子树  
  11.             p = p->lchild;  
  12.         }  
  13.         else{  
  14.             //退栈。訪问根节点  
  15.             p = stack.top();  
  16.             printf("%c ",p->data);  
  17.             stack.pop();  
  18.             //訪问右子树  
  19.             p = p->rchild;  
  20.         }  
  21.     }//while  
  22. }  

<3>后序遍历

【思路】：T是要遍历树的根指针。后序遍历要求在遍历完左右子树后。再訪问根。

须要推断根结点的左右子树是否均遍历过。

[cpp] view plaincopy
  1. //后序遍历(非递归)  
  2. typedef struct BiTNodePost{  
  3.     BiTree biTree;  
  4.     char tag;  
  5. }BiTNodePost,*BiTreePost;  
  6.   
  7. void PostOrder2(BiTree T){  
  8.     stack<BiTreePost> stack;  
  9.     //p是遍历指针  
  10.     BiTree p = T;  
  11.     BiTreePost BT;  
  12.     //栈不空或者p不空时循环  
  13.     while(p != NULL || !stack.empty()){  
  14.         //遍历左子树  
  15.         while(p != NULL){  
  16.             BT = (BiTreePost)malloc(sizeof(BiTNodePost));  
  17.             BT->biTree = p;  
  18.             //訪问过左子树  
  19.             BT->tag = ‘L‘;  
  20.             stack.push(BT);  
  21.             p = p->lchild;  
  22.         }  
  23.         //左右子树訪问完成訪问根节点  
  24.         while(!stack.empty() && (stack.top())->tag == ‘R‘){  
  25.             BT = stack.top();  
  26.             //退栈  
  27.             stack.pop();  
  28.             BT->biTree;  
  29.             printf("%c ",BT->biTree->data);  
  30.         }  
  31.         //遍历右子树  
  32.         if(!stack.empty()){  
  33.             BT = stack.top();  
  34.             //訪问过右子树  
  35.             BT->tag = ‘R‘;  
  36.             p = BT->biTree;  
  37.             p = p->rchild;  
  38.         }  
  39.     }//while  
  40. }  


<4>层次遍历

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

[cpp] view plaincopy
  1. //层次遍历  
  2. void LevelOrder(BiTree T){  
  3.     BiTree p = T;  
  4.     //队列  
  5.     queue<BiTree> queue;  
  6.     //根节点入队  
  7.     queue.push(p);  
  8.     //队列不空循环  
  9.     while(!queue.empty()){  
  10.         //对头元素出队  
  11.         p = queue.front();  
  12.         //訪问p指向的结点  
  13.         printf("%c ",p->data);  
  14.         //退出队列  
  15.         queue.pop();  
  16.         //左子树不空，将左子树入队  
  17.         if(p->lchild != NULL){  
  18.             queue.push(p->lchild);  
  19.         }  
  20.         //右子树不空，将右子树入队  
  21.         if(p->rchild != NULL){  
  22.             queue.push(p->rchild);  
  23.         }  
  24.     }  
  25. }  


測试用例：

技术分享

输入：

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

输出：

技术分享

代码：

[cpp] view plaincopy
  1. #include<iostream>  
  2. #include<stack>  
  3. #include<queue>  
  4. using namespace std;  
  5.   
  6. //二叉树结点  
  7. typedef struct BiTNode{  
  8.     //数据  
  9.     char data;  
  10.     //左右孩子指针  
  11.     struct BiTNode *lchild,*rchild;  
  12. }BiTNode,*BiTree;  
  13.   
  14. //按先序序列创建二叉树  
  15. int CreateBiTree(BiTree &T){  
  16.     char data;  
  17.     //按先序次序输入二叉树中结点的值（一个字符）。‘#’表示空树  
  18.     scanf("%c",&data);  
  19.     if(data == ‘#‘){  
  20.         T = NULL;  
  21.     }  
  22.     else{  
  23.         T = (BiTree)malloc(sizeof(BiTNode));  
  24.         //生成根结点  
  25.         T->data = data;  
  26.         //构造左子树  
  27.         CreateBiTree(T->lchild);  
  28.         //构造右子树  
  29.         CreateBiTree(T->rchild);  
  30.     }  
  31.     return 0;  
  32. }  
  33. //输出  
  34. void Visit(BiTree T){  
  35.     if(T->data != ‘#‘){  
  36.         printf("%c ",T->data);  
  37.     }  
  38. }  
  39. //先序遍历  
  40. void PreOrder(BiTree T){  
  41.     if(T != NULL){  
  42.         //訪问根节点  
  43.         Visit(T);  
  44.         //訪问左子结点  
  45.         PreOrder(T->lchild);  
  46.         //訪问右子结点  
  47.         PreOrder(T->rchild);  
  48.     }  
  49. }  
  50. //中序遍历    
  51. void InOrder(BiTree T){    
  52.     if(T != NULL){    
  53.         //訪问左子结点    
  54.         InOrder(T->lchild);    
  55.         //訪问根节点    
  56.         Visit(T);    
  57.         //訪问右子结点    
  58.         InOrder(T->rchild);    
  59.     }    
  60. }    
  61. //后序遍历  
  62. void PostOrder(BiTree T){  
  63.     if(T != NULL){  
  64.         //訪问左子结点  
  65.         PostOrder(T->lchild);  
  66.         //訪问右子结点  
  67.         PostOrder(T->rchild);  
  68.         //訪问根节点  
  69.         Visit(T);  
  70.     }  
  71. }  
  72. /* 先序遍历(非递归) 
  73.    思路：訪问T->data后。将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈。再先序遍历T的右子树。 
  74. */  
  75. void PreOrder2(BiTree T){  
  76.     stack<BiTree> stack;  
  77.     //p是遍历指针  
  78.     BiTree p = T;  
  79.     //栈不空或者p不空时循环  
  80.     while(p || !stack.empty()){  
  81.         if(p != NULL){  
  82.             //存入栈中  
  83.             stack.push(p);  
  84.             //訪问根节点  
  85.             printf("%c ",p->data);  
  86.             //遍历左子树  
  87.             p = p->lchild;  
  88.         }  
  89.         else{  
  90.             //退栈  
  91.             p = stack.top();  
  92.             stack.pop();  
  93.             //訪问右子树  
  94.             p = p->rchild;  
  95.         }  
  96.     }//while  
  97. }  
  98. /* 中序遍历(非递归) 
  99.    思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后。訪问根。再遍历右子树。 
  100.          先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈。訪问T->data。再中序遍历T的右子树。

     

  101. */  
  102. void InOrder2(BiTree T){  
  103.     stack<BiTree> stack;  
  104.     //p是遍历指针  
  105.     BiTree p = T;  
  106.     //栈不空或者p不空时循环  
  107.     while(p || !stack.empty()){  
  108.         if(p != NULL){  
  109.             //存入栈中  
  110.             stack.push(p);  
  111.             //遍历左子树  
  112.             p = p->lchild;  
  113.         }  
  114.         else{  
  115.             //退栈。訪问根节点  
  116.             p = stack.top();  
  117.             printf("%c ",p->data);  
  118.             stack.pop();  
  119.             //訪问右子树  
  120.             p = p->rchild;  
  121.         }  
  122.     }//while  
  123. }  
  124.   
  125. //后序遍历(非递归)  
  126. typedef struct BiTNodePost{  
  127.     BiTree biTree;  
  128.     char tag;  
  129. }BiTNodePost,*BiTreePost;  
  130.   
  131. void PostOrder2(BiTree T){  
  132.     stack<BiTreePost> stack;  
  133.     //p是遍历指针  
  134.     BiTree p = T;  
  135.     BiTreePost BT;  
  136.     //栈不空或者p不空时循环  
  137.     while(p != NULL || !stack.empty()){  
  138.         //遍历左子树  
  139.         while(p != NULL){  
  140.             BT = (BiTreePost)malloc(sizeof(BiTNodePost));  
  141.             BT->biTree = p;  
  142.             //訪问过左子树  
  143.             BT->tag = ‘L‘;  
  144.             stack.push(BT);  
  145.             p = p->lchild;  
  146.         }  
  147.         //左右子树訪问完成訪问根节点  
  148.         while(!stack.empty() && (stack.top())->tag == ‘R‘){  
  149.             BT = stack.top();  
  150.             //退栈  
  151.             stack.pop();  
  152.             BT->biTree;  
  153.             printf("%c ",BT->biTree->data);  
  154.         }  
  155.         //遍历右子树  
  156.         if(!stack.empty()){  
  157.             BT = stack.top();  
  158.             //訪问过右子树  
  159.             BT->tag = ‘R‘;  
  160.             p = BT->biTree;  
  161.             p = p->rchild;  
  162.         }  
  163.     }//while  
  164. }  
  165. //层次遍历  
  166. void LevelOrder(BiTree T){  
  167.     BiTree p = T;  
  168.     //队列  
  169.     queue<BiTree> queue;  
  170.     //根节点入队  
  171.     queue.push(p);  
  172.     //队列不空循环  
  173.     while(!queue.empty()){  
  174.         //对头元素出队  
  175.         p = queue.front();  
  176.         //訪问p指向的结点  
  177.         printf("%c ",p->data);  
  178.         //退出队列  
  179.         queue.pop();  
  180.         //左子树不空，将左子树入队  
  181.         if(p->lchild != NULL){  
  182.             queue.push(p->lchild);  
  183.         }  
  184.         //右子树不空，将右子树入队  
  185.         if(p->rchild != NULL){  
  186.             queue.push(p->rchild);  
  187.         }  
  188.     }  
  189. }  
  190. int main()  
  191. {  
  192.     BiTree T;  
  193.     CreateBiTree(T);  
  194.     printf("先序遍历：\n");  
  195.     PreOrder(T);  
  196.     printf("\n");  
  197.     printf("先序遍历(非递归)：\n");  
  198.     PreOrder2(T);  
  199.     printf("\n");  
  200.     printf("中序遍历：\n");  
  201.     InOrder(T);  
  202.     printf("\n");  
  203.     printf("中序遍历(非递归)：\n");  
  204.     InOrder2(T);  
  205.     printf("\n");  
  206.     printf("后序遍历：\n");  
  207.     PostOrder(T);  
  208.     printf("\n");  
  209.     printf("后序遍历(非递归)：\n");  
  210.     PostOrder2(T);  
  211.     printf("\n");  
  212.     printf("层次遍历：\n");  
  213.     LevelOrder(T);  
  214.     printf("\n");  
  215.     return 0;  
  216. }  


二叉树的遍历


联系
我们