您的位置: 首页  >  IT文章  >  【zz】二叉树遍历及C语言兑现

【zz】二叉树遍历及C语言兑现

分类: IT文章 • 2022-06-06 16:56:17
【zz】二叉树遍历及C语言实现

二叉树遍历及C语言实现

已知中序和前序序列，或者已知中序和后序序列，都能够构造一棵二叉树。在本例中，本人用C语言写程序解答了下面两个算法题：

（1）给出一棵二叉树的中序与后序遍历序列，求出它的先序遍历序列。

（2）给出一棵二叉树的中序与先序遍历序列，求出它的后序遍历序列。

知识点扼要回顾：
所谓二叉树的遍历，是指按一定的顺序对二叉树中的每个结点均访问一次，且仅访问一。按照根结点访问位置的不同，通常把二叉树的遍历分为六种：
TLR（根左右）, TRL（根右左）, LTR（左根右）
RTL（右根左）, LRT（左右根）, RLT（右左根）

其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为前序遍历、中序遍历和后序遍历。

前序遍历的规律是：输出根结点，输出左子树，输出右子树；  
中序遍历的规律是：输出左子树，输出根结点，输出右子树； 
后序遍历的规律是：输出左子树，输出右子树，输出根结点；

不多说了，看代码吧：）

 

  1. #include <iostream>  
  2. #include <string>  
  3.   
  4. using namespace std;  
  5.   
  6. //存储节点数据，为简便起见，这里选用字符  
  7. typedef char   DATA_TYPE;  
  8.   
  9. typedef struct tagBINARY_TREE_NODE  BINARY_TREE_NODE, *LPBINARY_TREE_NODE;  
  10.   
  11. struct tagBINARY_TREE_NODE  
  12. {  
  13.       DATA_TYPE             data;           //节点数据  
  14.       LPBINARY_TREE_NODE    pLeftChild;     //左孩子指针  
  15.       LPBINARY_TREE_NODE    pRightChild;    //右孩子指针  
  16. };  
  17.   
  18. //  
  19. //函数名称：TreeFromMidPost  
  20. //函数功能：给出一棵二叉树的中序与后序序列，构造这棵二叉树。   
  21. //输入参数：LPBINARY_TREE_NODE & lpNode：二叉树的结点   
  22. //          string mid：存储了二叉树的中序序列的字符串   
  23. //          string post：存储了二叉树的后序序列的字符串   
  24. //          int lm, int rm：二叉树的中序序列在数组mid中的左右边界   
  25. //          int lp, int rp：二叉树的后序序列在数组post中的左右边界  
  26. //  
  27. void TreeFromMidPost(LPBINARY_TREE_NODE & lpNode, string mid, string post, int lm, int rm, int lp, int rp)  
  28. {  
  29.     //构造二叉树结点  
  30.     lpNode = new BINARY_TREE_NODE;  
  31.     lpNode->data = post[rp];  
  32.     lpNode->pLeftChild = NULL;  
  33.     lpNode->pRightChild = NULL;  
  34.   
  35.     int pos = lm;  
  36.   
  37.     while (mid[pos] != post[rp])  
  38.     {  
  39.         pos++;  
  40.     }  
  41.     int iLeftChildLen = pos - lm;  
  42.   
  43.     if (pos > lm)//有左孩子，递归构造左子树  
  44.     {  
  45.         TreeFromMidPost(lpNode->pLeftChild, mid, post, lm, pos - 1, lp, lp + iLeftChildLen - 1);  
  46.     }  
  47.   
  48.     if (pos < rm)//有右孩子，递归构造右子树  
  49.     {  
  50.         TreeFromMidPost(lpNode->pRightChild, mid, post, pos + 1, rm, lp + iLeftChildLen, rp - 1);  
  51.     }  
  52. }  
  53.   
  54. //  
  55. //函数名称：TreeFromMidPre  
  56. //函数功能：给出一棵二叉树的先序与中序序列，构造这棵二叉树。   
  57. //输入参数: BINARY_TREE_NODE & lpNode：二叉树的结点  
  58. //          string mid：存储了二叉树的中序序列的字符串   
  59. //          string pre：存储了二叉树的先序序列的字符串   
  60. //          int lm, int rm：二叉树的中序序列在数组mid中的左右边界   
  61. //          int lp, int rp：二叉树的先序序列在数组pre中的左右边界  
  62. //  
  63. void TreeFromMidPre(LPBINARY_TREE_NODE & lpNode, string mid, string pre, int lm, int rm, int lp, int rp)  
  64. {  
  65.     //构造二叉树结点  
  66.     lpNode = new BINARY_TREE_NODE;  
  67.     lpNode->data = pre[lp];  
  68.     lpNode->pLeftChild = NULL;  
  69.     lpNode->pRightChild = NULL;  
  70.   
  71.     int pos = lm;  
  72.   
  73.     while (mid[pos] != pre[lp])  
  74.     {  
  75.         pos++;  
  76.     }  
  77.     int iLeftChildLen = pos - lm;  
  78.   
  79.     if (pos > lm)//有左孩子，递归构造左子树  
  80.     {  
  81.         TreeFromMidPre(lpNode->pLeftChild, mid, pre, lm, pos - 1, lp + 1, lp + iLeftChildLen);  
  82.     }  
  83.   
  84.     if (pos < rm)//有右孩子，递归构造右子树  
  85.     {  
  86.         TreeFromMidPre(lpNode->pRightChild, mid, pre, pos + 1, rm, lp + iLeftChildLen + 1, rp);  
  87.     }  
  88. }  
  89.   
  90. //先序遍历  
  91. void PreOrder(LPBINARY_TREE_NODE p)  
  92. {  
  93.        if(p != NULL)  
  94.        {  
  95.               cout << p->data;          //输出该结点  
  96.               PreOrder(p->pLeftChild);  //遍历左子树   
  97.               PreOrder(p->pRightChild); //遍历右子树  
  98.        }  
  99. }  
  100.   
  101. //中序遍历  
  102. void MidOrder(LPBINARY_TREE_NODE p)  
  103. {  
  104.        if(p != NULL)  
  105.        {  
  106.               MidOrder(p->pLeftChild);   //遍历左子树   
  107.               cout << p->data;           //输出该结点  
  108.               MidOrder(p->pRightChild);  //遍历右子树  
  109.        }  
  110. }  
  111.   
  112. //后序遍历  
  113. void PostOrder(LPBINARY_TREE_NODE p)  
  114. {  
  115.        if(p != NULL)  
  116.        {  
  117.               PostOrder(p->pLeftChild);  //遍历左子树   
  118.               PostOrder(p->pRightChild); //遍历右子树  
  119.               cout << p->data;           //输出该结点  
  120.        }  
  121. }  
  122.   
  123. //释放二叉树  
  124. void Release(LPBINARY_TREE_NODE lpNode)  
  125. {  
  126.     if(lpNode != NULL)  
  127.     {  
  128.         Release(lpNode->pLeftChild);  
  129.         Release(lpNode->pRightChild);  
  130.         delete lpNode;  
  131.         lpNode = NULL;  
  132.     }  
  133. }  
  134.   
  135.   
  136. int main(int argc, char* argv[])  
  137. {  
  138.     string              pre;            //存储先序序列  
  139.     string              mid;            //存储中序序列  
  140.     string              post;           //存储后序序列  
  141.   
  142.     LPBINARY_TREE_NODE  lpRoot;         //二叉树根节点指针  
  143.   
  144.   
  145.     cout<<"程序１已知二叉树的中序与后序序列，求先序序列"<<endl;  
  146.     cout<<"请先输入中序序列，回车后输入后序序列："<<endl;  
  147.   
  148.     cin >> mid;  
  149.     cin >> post;  
  150.   
  151.     TreeFromMidPost(lpRoot, mid, post, 0, mid.size()-1, 0, post.size()-1);  
  152.     cout<<"先序遍历结果：";  
  153.     PreOrder(lpRoot);  
  154.     cout<<endl;  
  155.   
  156.     cout<<"中序遍历结果：";  
  157.     MidOrder(lpRoot);  
  158.     cout<<endl;  
  159.   
  160.     cout<<"后序遍历结果：";  
  161.     PostOrder(lpRoot);  
  162.     cout<<endl;  
  163.     Release(lpRoot);  
  164.     cout<<endl;  
  165.   
  166.     cout<<"程序２已知二叉树的中序与先序序列，求后序序列"<<endl;  
  167.     cout<<"请先输入先序序列，回车后输入中序序列："<<endl;  
  168.     cin >> pre;  
  169.     cin >> mid;  
  170.   
  171.     TreeFromMidPre(lpRoot, mid, pre, 0, mid.size()-1, 0, pre.size()-1);  
  172.     cout<<"先序遍历结果：";  
  173.     PreOrder(lpRoot);  
  174.     cout<<endl;  
  175.   
  176.     cout<<"中序遍历结果：";  
  177.     MidOrder(lpRoot);  
  178.     cout<<endl;  
  179.   
  180.     cout<<"后序遍历结果：";  
  181.     PostOrder(lpRoot);  
  182.     cout<<endl;  
  183.     Release(lpRoot);  
  184.     cout<<endl;  
  185.   
  186.   
  187.     system("pause");  
  188.     return 0;  
  189. }  

 

（1）程序1的输入方式：
已知二叉树的中序与后序序列，求先序序列，请先输入中序序列，回车后输入后序序列：
例如输入：
DGBAECHF
GDBEHFCA
输出：
先序遍历结果：ABDGCEFH
中序遍历结果：DGBAECHF
后序遍历结果：GDBEHFCA

（2）程序2的输入方式：
已知二叉树的先序与中序序列，求后序序列，请先输入先序序列，回车后输入中序序列：
例如输入：
abdefgc
debgfac
输出：
先序遍历结果：abdefgc
中序遍历结果：debgfac
后序遍历结果：edgfbca

最后请看该程序运行效果图：

【zz】二叉树遍历及C语言兑现

这是程序1所确定的二叉树图：

【zz】二叉树遍历及C语言兑现

这是程序2所确定的二叉树图：

【zz】二叉树遍历及C语言兑现

by Loomman, QQ:28077188, MSN: Loomman@hotmail.com QQ裙：30515563 ☆程序天堂☆ 请尊重作者原创，转载注明来自裂帛一剑博客，谢谢合作。

相关推荐