[算法系列之三]二叉树中序前序序列(或后序)求解树

简介:

【思路】

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

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

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

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

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

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

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

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

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

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

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

测试用例:


【先序 中序 求 后序】

输入:

先序序列:ABCDEGF

中序序列:CBEGDFA

输出后序:CGEFDBA

代码:

[cpp]  view plain copy
  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 plain copy
  1. BiTree T;  
  2.     PreInCreateTree(T,0,0,strlen(InArray));  
  3.     PostOrder(T);  



另一种算法:

[cpp]  view plain copy
  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 plain copy
  1. PreInCreateTree(T,0,strlen(PreArray)-1,0,strlen(InArray)-1);  


/*---------------------------------------
*   日期:2015-04-28
*   作者:SJF0115
*   题目: 105.Construct Binary Tree from Preorder and Inorder Traversal
*   网址:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
*   结果:AC
*   来源:LeetCode
*   博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int size = preorder.size();
        if(size <= 0){
            return nullptr;
        }//if
        return PreInBuildTree(preorder,inorder,0,0,size);
    }
private:
    TreeNode* PreInBuildTree(vector<int> &preorder,vector<int> &inorder,int preIndex,int inIndex,int size){
        if(size <= 0){
            return nullptr;
        }//if
        // 根节点
        TreeNode* root = new TreeNode(preorder[preIndex]);
        // 寻找根节点在中序遍历数组的下标
        int index = 0;
        for(int i = 0;i < size;++i){
            if(preorder[preIndex] == inorder[inIndex+i]){
                index = inIndex+i;
                break;
            }//if
        }//for
        // 左子树个数
        int leftSize = index - inIndex;
        // 右子树个数
        int rightSize = size - leftSize - 1;
        // 左子树
        root->left = PreInBuildTree(preorder,inorder,preIndex+1,inIndex,leftSize);
        // 右子树
        root->right = PreInBuildTree(preorder,inorder,preIndex+1+leftSize,index+1,rightSize);
        return root;
    }
};

void PostOrder(TreeNode* root){
    if(root){
        PostOrder(root->left);
        PostOrder(root->right);
        cout<<root->val<<endl;
    }//if
}

int main(){
    Solution solution;
    vector<int> preorder = {1,2,4,8,5,3,6,7};
    vector<int> inorder = {8,4,2,5,1,6,3,7};
    TreeNode* root = solution.buildTree(preorder,inorder);
    // 输出
    PostOrder(root);
    return 0;
}



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


【中序 后序 求先序】

输入:

中序序列:CBEGDFA

后序序列:CGEFDBA

输出先序:ABCDEGF


代码:

[cpp]  view plain copy
  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 plain copy
  1. BiTree T2;  
  2.     PostInCreateTree(T2,strlen(PostArray) - 1,0,strlen(InArray));  
  3.     PreOrder(T2);  

/*---------------------------------------
*   日期:2015-05-01
*   作者:SJF0115
*   题目: 106.Construct Binary Tree from Inorder and Postorder Traversal
*   网址:https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
*   结果:AC
*   来源:LeetCode
*   博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        int size = inorder.size();
        if(size <= 0){
            return nullptr;
        }//if
        return InPostBuildTree(inorder,postorder,0,size-1,size);
    }
private:
    TreeNode* InPostBuildTree(vector<int> &inorder,vector<int> &postorder,int inIndex,int postIndex,int size){
        if(size <= 0){
            return nullptr;
        }//if
        // 根节点
        TreeNode* root = new TreeNode(postorder[postIndex]);
        // 寻找postorder[postIndex]在中序序列中的下标
        int index = 0;
        for(int i = 0;i < size;++i){
            if(postorder[postIndex] == inorder[inIndex+i]){
                index = inIndex+i;
                break;
            }//if
        }//for
        int leftSize = index - inIndex;
        int rightSize = size - leftSize - 1;
        root->left = InPostBuildTree(inorder,postorder,inIndex,postIndex-1-rightSize,leftSize);
        root->right = InPostBuildTree(inorder,postorder,index+1,postIndex-1,rightSize);
        return root;
    }
};

void PreOrder(TreeNode* root){
    if(root){
        cout<<root->val<<endl;
        PreOrder(root->left);
        PreOrder(root->right);
    }//if
}

int main() {
    Solution solution;
    vector<int> inorder = {8,4,2,5,1,6,3,7};
    vector<int> postorder = {8,4,5,2,6,7,3,1};
    TreeNode* root = solution.buildTree(inorder,postorder);
    PreOrder(root);
}




完整代码:

[cpp]  view plain copy
  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. }  
目录
相关文章
|
1天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
14 5
|
4天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
10 0
|
26天前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
59 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
29天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
17 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
29天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
17 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
1月前
|
存储 算法
【二叉树】—— 算法题
【二叉树】—— 算法题
【二叉树】—— 算法题
|
29天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
22 0
|
2月前
|
算法 数据可视化
基于SSA奇异谱分析算法的时间序列趋势线提取matlab仿真
奇异谱分析(SSA)是一种基于奇异值分解(SVD)和轨迹矩阵的非线性、非参数时间序列分析方法,适用于提取趋势、周期性和噪声成分。本项目使用MATLAB 2022a版本实现从强干扰序列中提取趋势线,并通过可视化展示了原时间序列与提取的趋势分量。代码实现了滑动窗口下的奇异值分解和分组重构,适用于非线性和非平稳时间序列分析。此方法在气候变化、金融市场和生物医学信号处理等领域有广泛应用。
111 19
|
2月前
|
算法 数据可视化 数据安全/隐私保护
基于LK光流提取算法的图像序列晃动程度计算matlab仿真
该算法基于Lucas-Kanade光流方法,用于计算图像序列的晃动程度。通过计算相邻帧间的光流场并定义晃动程度指标(如RMS),可量化图像晃动。此版本适用于Matlab 2022a,提供详细中文注释与操作视频。完整代码无水印。
|
3月前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称,即左右子树是否对称.
26 0