首页 > 代码库 > 经典白话算法之二叉树中序前序序列(或后序)求解树

经典白话算法之二叉树中序前序序列(或后序)求解树

2024-07-02 16:15:14   224人阅读

这种题一般有二种形式，共同点是都已知中序序列。如果没有中序序列，是无法唯一确定一棵树的。

<1>已知二叉树的前序序列和中序序列，求解树。

1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。

2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点

边和右边都为空，则根节点已经为叶子节点。

3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

<2>、已知二叉树的后序序列和中序序列，求解树。

1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。

2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点

边和右边都为空，则根节点已经为叶子节点。

3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

测试用例：


<1>先序 中序 求 后序

输入：

先序序列：ABCDEGF

中序序列：CBEGDFA

输出后序：CGEFDBA

代码：

[cpp] view plaincopy
  1. /* 
  2.     PreIndex: 前序序列字符串中子树的第一个节点在PreArray[]中的下标 
  3.     InIndex:  中序序列字符串中子树的第一个节点在InArray[]中的下标 
  4.     subTreeLen: 子树的字符串序列的长度 
  5.     PreArray： 先序序列数组 
  6.     InArray：中序序列数组 
  7. */  
  8. void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){  
  9.     //subTreeLen < 0 子树为空  
  10.     if(subTreeLen <= 0){  
  11.         T = NULL;  
  12.         return;  
  13.     }  
  14.     else{  
  15.         T = (BiTree)malloc(sizeof(BiTNode));  
  16.         //创建根节点  
  17.         T->data = PreArray[PreIndex];  
  18.         //找到该节点在中序序列中的位置  
  19.         int index = strchr(InArray,PreArray[PreIndex]) - InArray;  
  20.         //左子树结点个数  
  21.         int LenF = index - InIndex;  
  22.         //创建左子树  
  23.         PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF);  
  24.         //右子树结点个数(总结点 - 根节点 - 左子树结点)  
  25.         int LenR = subTreeLen - 1 - LenF;  
  26.         //创建右子树  
  27.         PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR);  
  28.     }  
  29. }  

主函数调用：

[cpp] view plaincopy
  1. BiTree T;  
  2.     PreInCreateTree(T,0,0,strlen(InArray));  
  3.     PostOrder(T);  



另一种算法：

[cpp] view plaincopy
  1. /* 
  2.     PreS       先序序列的第一个元素下标 
  3.     PreE       先序序列的最后一个元素下标 
  4.     InS        中序序列的第一个元素下标  
  5.     InE        先序序列的最后一个元素下标   
  6.     PreArray   先序序列数组 
  7.     InArray    中序序列数组 
  8. */  
  9. void PreInCreateTree(BiTree &T,int PreS ,int PreE ,int InS ,int InE){  
  10.     int RootIndex;  
  11.     //先序第一个字符  
  12.     T = (BiTree)malloc(sizeof(BiTNode));   
  13.     T->data = PreArray[PreS];  
  14.     //寻找该结点在中序序列中的位置  
  15.     for(int i = InS;i <= InE;i++){  
  16.         if(T->data == InArray[i]){  
  17.             RootIndex = i;  
  18.             break;  
  19.         }  
  20.     }  
  21.     //根结点的左子树不为空  
  22.     if(RootIndex != InS){  
  23.         //以根节点的左结点为根建树  
  24.         PreInCreateTree(T->lchild,PreS+1,(RootIndex-InS)+PreS,InS,RootIndex-1);  
  25.     }  
  26.     else{  
  27.         T->lchild = NULL;  
  28.     }  
  29.     //根结点的右子树不为空  
  30.     if(RootIndex != InE){  
  31.         //以根节点的右结点为根建树  
  32.         PreInCreateTree(T->rchild,PreS+1+(RootIndex-InS),PreE,RootIndex+1,InE);  
  33.     }  
  34.     else{  
  35.         T->rchild = NULL;  
  36.     }  
  37. }  
主函数调用：
[cpp] view plaincopy
  1. PreInCreateTree(T,0,strlen(PreArray)-1,0,strlen(InArray)-1);  


具体讲解请看：点击打开链接


<2>中序 后序 求先序

输入：

中序序列：CBEGDFA

后序序列：CGEFDBA

输出先序：ABCDEGF


代码：

[cpp] view plaincopy
  1. /* 
  2.     PostIndex: 后序序列字符串中子树的最后一个节点在PreArray[]中的下标 
  3.     InIndex:  中序序列字符串中子树的第一个节点在InArray[]中的下标 
  4.     subTreeLen: 子树的字符串序列的长度 
  5.     PostArray： 后序序列数组 
  6.     InArray：中序序列数组 
  7. */  
  8. void PostInCreateTree(BiTree &T,int PostIndex,int InIndex,int subTreeLen){  
  9.     //subTreeLen < 0 子树为空  
  10.     if(subTreeLen <= 0){  
  11.         T = NULL;  
  12.         return;  
  13.     }  
  14.     else{  
  15.         T = (BiTree)malloc(sizeof(BiTNode));  
  16.         //创建根节点  
  17.         T->data = PostArray[PostIndex];  
  18.         //找到该节点在中序序列中的位置  
  19.         int index = strchr(InArray,PostArray[PostIndex]) - InArray;  
  20.         //左子树结点个数  
  21.         int LenF = index - InIndex;  
  22.         //创建左子树  
  23.         PostInCreateTree(T->lchild,PostIndex - (subTreeLen - 1 - LenF) - 1,InIndex,LenF);  
  24.         //右子树结点个数(总结点 - 根节点 - 左子树结点)  
  25.         int LenR = subTreeLen - 1 - LenF;  
  26.         //创建右子树  
  27.         PostInCreateTree(T->rchild,PostIndex-1,index + 1,LenR);  
  28.     }  
  29. }  

主函数调用：

[cpp] view plaincopy
  1. BiTree T2;  
  2.     PostInCreateTree(T2,strlen(PostArray) - 1,0,strlen(InArray));  
  3.     PreOrder(T2);  




完整代码：

[cpp] view plaincopy
  1. #include<iostream>  
  2. #include<string>  
  3. using namespace std;  
  4.   
  5. //二叉树结点  
  6. typedef struct BiTNode{  
  7.     //数据  
  8.     char data;  
  9.     //左右孩子指针  
  10.     struct BiTNode *lchild,*rchild;  
  11. }BiTNode,*BiTree;  
  12.   
  13. //先序序列  
  14. char PreArray[101] = "ABCDEGF";  
  15. //中序序列  
  16. char InArray[101] = "CBEGDFA";  
  17. //后序序列  
  18. char PostArray[101] = "CGEFDBA";  
  19. /* 
  20.     PreIndex: 前序序列字符串中子树的第一个节点在PreArray[]中的下标 
  21.     InIndex:  中序序列字符串中子树的第一个节点在InArray[]中的下标 
  22.     subTreeLen: 子树的字符串序列的长度 
  23.     PreArray： 先序序列数组 
  24.     InArray：中序序列数组 
  25. */  
  26. void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){  
  27.     //subTreeLen < 0 子树为空  
  28.     if(subTreeLen <= 0){  
  29.         T = NULL;  
  30.         return;  
  31.     }  
  32.     else{  
  33.         T = (BiTree)malloc(sizeof(BiTNode));  
  34.         //创建根节点  
  35.         T->data = PreArray[PreIndex];  
  36.         //找到该节点在中序序列中的位置  
  37.         int index = strchr(InArray,PreArray[PreIndex]) - InArray;  
  38.         //左子树结点个数  
  39.         int LenF = index - InIndex;  
  40.         //创建左子树  
  41.         PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF);  
  42.         //右子树结点个数(总结点 - 根节点 - 左子树结点)  
  43.         int LenR = subTreeLen - 1 - LenF;  
  44.         //创建右子树  
  45.         PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR);  
  46.     }  
  47. }  
  48. /* 
  49.     PostIndex: 后序序列字符串中子树的最后一个节点在PreArray[]中的下标 
  50.     InIndex:  中序序列字符串中子树的第一个节点在InArray[]中的下标 
  51.     subTreeLen: 子树的字符串序列的长度 
  52.     PostArray： 后序序列数组 
  53.     InArray：中序序列数组 
  54. */  
  55. void PostInCreateTree(BiTree &T,int PostIndex,int InIndex,int subTreeLen){  
  56.     //subTreeLen < 0 子树为空  
  57.     if(subTreeLen <= 0){  
  58.         T = NULL;  
  59.         return;  
  60.     }  
  61.     else{  
  62.         T = (BiTree)malloc(sizeof(BiTNode));  
  63.         //创建根节点  
  64.         T->data = PostArray[PostIndex];  
  65.         //找到该节点在中序序列中的位置  
  66.         int index = strchr(InArray,PostArray[PostIndex]) - InArray;  
  67.         //左子树结点个数  
  68.         int LenF = index - InIndex;  
  69.         //创建左子树  
  70.         PostInCreateTree(T->lchild,PostIndex - (subTreeLen - 1 - LenF) - 1,InIndex,LenF);  
  71.         //右子树结点个数(总结点 - 根节点 - 左子树结点)  
  72.         int LenR = subTreeLen - 1 - LenF;  
  73.         //创建右子树  
  74.         PostInCreateTree(T->rchild,PostIndex-1,index + 1,LenR);  
  75.     }  
  76. }  
  77. //先序遍历    
  78. void PreOrder(BiTree T){    
  79.     if(T != NULL){    
  80.         //访问根节点    
  81.         printf("%c ",T->data);  
  82.         //访问左子结点    
  83.         PreOrder(T->lchild);    
  84.         //访问右子结点    
  85.         PreOrder(T->rchild);     
  86.     }    
  87. }    
  88. //后序遍历    
  89. void PostOrder(BiTree T){    
  90.     if(T != NULL){    
  91.         //访问左子结点    
  92.         PostOrder(T->lchild);    
  93.         //访问右子结点    
  94.         PostOrder(T->rchild);   
  95.         //访问根节点    
  96.         printf("%c ",T->data);  
  97.     }    
  98. }    
  99. int main()  
  100. {  
  101.     BiTree T;  
  102.     PreInCreateTree(T,0,0,strlen(InArray));  
  103.     PostOrder(T);  
  104.     printf("\n");  
  105.     BiTree T2;  
  106.     PostInCreateTree(T2,strlen(PostArray) - 1,0,strlen(InArray));  
  107.     PreOrder(T2);  
  108.     return 0;  
  109. }  


联系
我们