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

简介:

【思路】

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

<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. }  
目录
相关文章
|
5月前
|
机器学习/深度学习 算法 数据挖掘
基于WOA鲸鱼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB 2022a/2024b实现,采用WOA优化的BiLSTM算法进行序列预测。核心代码包含完整中文注释与操作视频,展示从参数优化到模型训练、预测的全流程。BiLSTM通过前向与后向LSTM结合,有效捕捉序列前后文信息,解决传统RNN梯度消失问题。WOA优化超参数(如学习率、隐藏层神经元数),提升模型性能,避免局部最优解。附有运行效果图预览,最终输出预测值与实际值对比,RMSE评估精度。适合研究时序数据分析与深度学习优化的开发者参考。
|
5月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本内容包含基于BiLSTM与遗传算法(GA)的算法介绍及实现。算法通过MATLAB2022a/2024b运行,核心为优化BiLSTM超参数(如学习率、神经元数量),提升预测性能。LSTM解决传统RNN梯度问题,捕捉长期依赖;BiLSTM双向处理序列,融合前文后文信息,适合全局信息任务。附完整代码(含注释)、操作视频及无水印运行效果预览,适用于股票预测等场景,精度优于单向LSTM。
|
2月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于WOA鲸鱼优化的XGBoost序列预测算法matlab仿真
基于WOA优化XGBoost的序列预测算法,利用鲸鱼优化算法自动寻优超参数,提升预测精度。结合MATLAB实现,适用于金融、气象等领域,具有较强非线性拟合能力,实验结果表明该方法显著优于传统模型。(238字)
|
5月前
|
算法 数据安全/隐私保护
基于Logistic-Map混沌序列的数字信息加解密算法matlab仿真,支持对文字,灰度图,彩色图,语音进行加解密
本项目实现了一种基于Logistic Map混沌序列的数字信息加解密算法,使用MATLAB2022A开发并包含GUI操作界面。支持对文字、灰度图像、彩色图像和语音信号进行加密与解密处理。核心程序通过调整Logistic Map的参数生成伪随机密钥序列,确保加密的安全性。混沌系统的不可预测性和对初值的敏感依赖性是该算法的核心优势。示例展示了彩色图像、灰度图像、语音信号及文字信息的加解密效果,运行结果清晰准确,且完整程序输出无水印。
基于Logistic-Map混沌序列的数字信息加解密算法matlab仿真,支持对文字,灰度图,彩色图,语音进行加解密
|
5月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。
|
5月前
|
算法 数据安全/隐私保护
基于混沌序列和小波变换层次化编码的遥感图像加密算法matlab仿真
本项目实现了一种基于小波变换层次化编码的遥感图像加密算法,并通过MATLAB2022A进行仿真测试。算法对遥感图像进行小波变换后,利用Logistic混沌映射分别对LL、LH、HL和HH子带加密,完成图像的置乱与扩散处理。核心程序展示了图像灰度化、加密及直方图分析过程,最终验证加密图像的相关性、熵和解密后图像质量等性能指标。通过实验结果(附图展示),证明了该算法在图像安全性与可恢复性方面的有效性。
|
5月前
|
机器学习/深度学习 数据采集 算法
基于GWO灰狼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于Matlab 2022a/2024b实现,结合灰狼优化(GWO)算法与双向长短期记忆网络(BiLSTM),用于序列预测任务。核心代码包含数据预处理、种群初始化、适应度计算及参数优化等步骤,完整版附带中文注释与操作视频。BiLSTM通过前向与后向处理捕捉序列上下文信息,GWO优化其参数以提升预测性能。效果图展示训练过程与预测结果,适用于气象、交通等领域。LSTM结构含输入门、遗忘门与输出门,解决传统RNN梯度问题,而BiLSTM进一步增强上下文理解能力。
|
8月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
241 10
 算法系列之数据结构-二叉树
|
8月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于模糊神经网络的金融序列预测算法matlab仿真
本程序为基于模糊神经网络的金融序列预测算法MATLAB仿真,适用于非线性、不确定性金融数据预测。通过MAD、RSI、KD等指标实现序列预测与收益分析,运行环境为MATLAB2022A,完整程序无水印。算法结合模糊逻辑与神经网络技术,包含输入层、模糊化层、规则层等结构,可有效处理金融市场中的复杂关系,助力投资者制定交易策略。
|
10月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
361 3

热门文章

最新文章