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

【思路】

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

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

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

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

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

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

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

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

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

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

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

测试用例：

【先序 中序 求 后序】

输入：

先序序列：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);  
/*---------------------------------------
*   日期：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
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);  
/*---------------------------------------
*   日期：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
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. }  
时间： 2024-11-16 02:01:57

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

二叉树系列（二）：已知中序遍历序列和后序遍历序列，求先序遍历序列

前面已经介绍过三种遍历方法的规则,为了大家看着方便,这里我们在重新介绍一遍:   1.先序遍历   (1)访问根结点:   (2)先序遍历左子树:   (3)先序遍历右子树.   2.中序遍历   (1)中序遍历左子树:   (2)访问根结点:   (3)中序遍历右子树.   3.后序遍历   (1)后序遍历左子树:   (2)后序遍历右子树:   (3)访问根结点.   知道了二叉树的三种遍历规则,只要有中序遍历序列和前后任一种遍历序列,我们就可以求出第三种遍历序列,今天我们研究的是已知中序和

已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为?

问题描述 已知一棵树的前序序列为ABCDEF,后序序列为CEDFBA,则对该树进行层次遍历得到的序列为? 遇见已知先序后序这类问题如何解决?感觉没有中序很难0.0求大神~! 解决方案 http://www.docin.com/p-633991719.html abcdfe 解决方案二: 这道题和一般题,有一点不一样,一般来说必须要有中序遍历+前序遍历或者后序遍历,这样才能确定唯一的根和,左右子树的未知, 但是这道题直接给的前后序列.....所以无法确定左右子树,,,,,我也很想知道分析方法..

[算法系列之三十一]最近公共祖先（LCA）

[简介] 对于有根树T的两个结点u.v,最近公共祖先LCA(T,u,v)表示一个结点x,满足x是u.v的祖先且x的深度尽可能大. 另一种理解方式是把T理解为一个无向无环图,而LCA(T,u,v)即u到v的最短路上深度最小的点. 例如,对于下面的树,结点4和结点6的最近公共祖先LCA(T,4,6)为结点2. 求树中两个结点的最低公共祖先是面试中经常出现的一个问题.一般的做法,可能是针对是否为二叉查找树分情况讨论. LCA问题的扩展主要在于结点是否只包含父结点指针,对于同一棵树是否进行多次LCA查询

[算法系列之三十]Dijkstra单源最短路径算法

单源最短路径问题 给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数.另外,还给定 V 中的一个顶点,称为源.现在我们要计算从源到所有其他各顶点的最短路径长度.这里的长度是指路上各边权之和.这个问题通常称为单源最短路径问题. 前面Bellman-Ford最短路径算法讲了单源最短路径的Bellman-Ford算法(动态规划算法).这里介绍另外一个更常见的算法Dijkstra算法. Dijkstra算法和 最小生成树Prim算法最小生成树算法非常类似,大家可以先熟悉下个算法.两个算法

[算法系列之三十三]杨氏矩阵

即对于矩阵Table有Table[i][j] ≤Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j],我们也称这样的矩阵为杨氏矩阵. 给出判定某个数是否存在该矩阵中的高效算法.   分析: 为了便于复杂度分析,我们暂时假定该矩阵为大小n*n.如下图所示为一个杨氏矩阵. 二分搜索解法: 许多人都观察到了矩阵在二维上都是有序的,所以使用在每一行(或者每一列)使用二分搜索是很自然的想法.由于每一行二分搜索需要O(lgn)时间,搜索n行需要O(nlogn)的时间.

[算法系列之三十二]1的数目

题目 Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. For example: Given n = 13, Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13. 思路一 这个问题看上去并不是一个困难的问题,

二叉树前序、中序、后序遍历相互求法

今天来总结下二叉树前序.中序.后序遍历相互求法,即如果知道两个的遍历,如何求第三种遍历方法,比较笨的方法是画出来二叉树,然后根据各种遍历不同的特性来求,也可以编程求出,下面我们分别说明. 首先,我们看看前序.中序.后序遍历的特性:  前序遍历:      1.访问根节点      2.前序遍历左子树      3.前序遍历右子树  中序遍历:      1.中序遍历左子树      2.访问根节点      3.中序遍历右子树  后序遍历:      1.后序遍历左子树      2.后序遍历右

C++中的树、二叉树、二叉树遍历、二叉树前序、中序、后序遍历相互求法

本博文来总结下树.二叉树以及二叉树前序.中序.后序遍历相互求法,即如果知道两个的遍历,如何求第三种遍历方法,比较笨的方法是画出来二叉树,然后根据各种遍历不同的特性来求,也可以编程求出,下面我们分别说明. 1.什么是树?什么是二叉树? 树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合. 二叉树是指结点的度不超过2的有序树. (结点的度:树中的一个结点拥有的子树数目.) 2.二叉树的前序.中序.后序遍历的特性  二叉树前序遍历特性:   (1).访问根节点  (2).前序遍

STL学习系列之三：操作list容器

学习完了STL系列之二,自己写了个程序练手!程序采用的还是系列之二文章的架构.学习了STL之一和之二,对于STL的基本原理算有个个基本的了解.其实关于这几种容器,以前也都接触过,不过是在java上,当时学习时也是囫囵吞枣!现在感觉那真是学习之大忌,还是一步一个脚印为好.速度可以放慢点,那要扎实! 注意:程序在vc6下调试通过,对于不清楚如何在vc下运行STL者,可以读STL系列之一. //TjuAiLab //Author:zhangbufeng //Time:2005.8.23 22:00 #