精华内容
下载资源
问答
  • 现在有一个问题,已知二叉树的前序遍历中序遍历:PreOrder: GDAFEMHZInOrder: ADEFGHMZ我们如何还原这颗二叉树,并求出他的后序遍历?我们基于一个事实:中序遍历一定是 { 左子树中的节点集合 },root,{ 右子...

    两个遍历确定一棵树其中必须有一个是中序遍历


    现在有一个问题,已知二叉树的前序遍历和中序遍历:
    PreOrder:          GDAFEMHZ
    InOrder:            ADEFGHMZ
    我们如何还原这颗二叉树,并求出他的后序遍历?

    我们基于一个事实:中序遍历一定是 { 左子树中的节点集合 },root,{ 右子树中的节点集合 },前序遍历的作用就是找到每颗子树的root位置。

    输入:前序遍历,中序遍历
    1、寻找树的root,前序遍历的第一节点G就是root。
    2、观察前序遍历GDAFEMHZ,知道了G是root,剩下的节点必然在root的左或右子树中的节点。
    3、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树中的节点,G右侧的HMZ必然是root的右子树中的节点,root不在中序遍历的末尾或开始就说明根节点的两颗子树都不为空。
    4、观察左子树ADEF,按照前序遍历的顺序来排序为DAFE,因此左子树的根节点为D,并且A是左子树的左子树中的节点,EF是左子树的右子树中的节点。
    5、同样的道理,观察右子树节点HMZ,前序为MHZ,因此右子树的根节点为M,左子节点H,右子节点Z。

    观察发现,上面的过程是递归的。先找到当前树的根节点,然后划分为左子树,右子树,然后进入左子树重复上面的过程,然后进入右子树重复上面的过程。最后就可以还原一棵树了:


    接着借助一个二维数组,和一个height变量(记录当前所在的层数)就可以在递归的过程中按层把树存起来了。

    同理,由后序遍历,中序遍历得到前序遍历和按层输出的方法思路一样,过程如下图:

    代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    
    /*struct TreeNode
    {
    	char val;
    	TreeNode *left,*right;
    	TreeNode(char c=' '):
    		val(c),left(nullptr),right(nullptr){} 
    };*/
    
    void getPostorder(const string&,const string&,string &,int);
    void getPreorder(const string &,const string &,string &,int );
    void getLevel(const string&,const string&,int,vector<vector<char>>&,int);
    string Preorder="GDAFEMHZ";
    string Inorder="ADEFGHMZ";
    
    int main()
    {
    	string Postorder="";
    	string new_Pre="";
    	getPostorder(Preorder,Inorder,Postorder,int(Preorder.size()));
    	getPreorder(Postorder,Inorder,new_Pre,int(Inorder.size()));
    	if(Preorder==new_Pre)
    		cout<<"Pre: \n"<<new_Pre<<endl;
    	else
    		cout<<"wrong~"<<endl;
    
    	vector<vector<char>>level;
    	getLevel(Preorder,Inorder,int(Preorder.size()),level,0);
    	for(auto i:level){
    		for(auto j:i)
    			cout<<j<<" ";
    		cout<<endl;
    	}
    	return 0;
    }
    //根据先序,中序,得出后序。这里可以一并完成按层存储的过程,但是由于参数过多,方便理解将两个分为两个函数。
    void getPostorder(const string &Pre,const string &In,string &Pos,int len)
    {
    	if(len==0)
    		return;
    	char c=Pre[0];
    	//在中序遍历中找根节点
    	int root_index=0;
    	for(;root_index<len;++root_index){
    		if(In[root_index]==c)
    			break;
    	}
    	//左子树
    	getPostorder(Pre.substr(1),In,Pos,root_index);
    	//右子树
    	getPostorder(Pre.substr(root_index+1),In.substr(root_index+1),Pos,len-root_index-1);
    	Pos.insert(Pos.end(),c);
    	return;
    }
    //根据后序,中序,得出先序
    void getPreorder(const string &Post,const string &In,string &Pre,int len)
    {
    	if(len==0)
    		return;
    	char c=Post[Post.size()-1];
    	//在中序中寻找根节点
    	int root_index=0;
    	for(;root_index<len;++root_index){
    		if(In[root_index]==c)
    			break;
    	}
    	//先序,就先执行插入字符的操作
    	Pre.insert(Pre.end(),c);
    	//左子树
    	getPreorder(Post.substr(0,root_index),In,Pre,root_index);
    	//右子树
    	getPreorder(Post.substr(root_index,len-root_index-1),In.substr(root_index+1),
    		Pre,len-root_index-1);
    	return;
    }
    //根据先序,中序,按层打印出树,按后序和中序就不再重复了 
    void getLevel(const string &Pre,const string &In,int len,vector<vector<char>>&level,int height)
    {
    	if(len==0)
    		return;
    	char c=Pre[0];
    	if(height>=level.size())
    		level.emplace_back(vector<char>());
    	level[height++].emplace_back(c);
    	//在中序遍历中找根节点
    	int root_index=0;
    	for(;root_index<len;++root_index){
    		if(In[root_index]==c)
    			break;
    	}
    		//左子树
    	getLevel(Pre.substr(1),In,root_index,level,height);
    	//右子树
    	getLevel(Pre.substr(root_index+1),In.substr(root_index+1),len-root_index-1,level,height);
    	return;
    }

    展开全文
  • https://www.cnblogs.com/jiaxin359/p/9512348.html
    展开全文
  • 我们无法根据树先序遍历和树后序遍历得到二叉树的结构,或者说结构是不确定的 单向陷门函数思想 hash函数的功能就是将某个大集合映射到小集合中,例如布隆过滤器或者布谷鸟过滤器。或者我们的一些密码的存储,并...

    我们无法根据树的先序遍历和树的后序遍历得到二叉树的结构,或者说结构是不确定的

    单向陷门函数思想

    hash函数的功能就是将某个大集合映射到小集合中,例如布隆过滤器或者布谷鸟过滤器。或者我们的一些密码的存储,并不是在数据库中直接放入我们的密码,这样如果数据库被盗或者丢失会造成很严重的损失。那么数据库上存储的密码实际上是我们密码的hash映射或某种加密下的密文。
    既然是单向的就说明我们无法从以映射的集合得到原集合。同时这种压缩是有损的。
    因此一棵树也可以看做是一个哈希映射。我们将含有n个节点的二叉树映射成为串长为n的一个字符串。那么你可能说,这不是没有损失节点吗?
    千万别忘了,当二叉树用链表表示的时候,含有n个节点的二叉链表有n+1个空链域,就是二叉树中叶子节点指向的空指针。
    因此当根据某个序列还原二叉树就会有很大的不确定性。
    但是有个特殊的例子:只给出先序遍历和后序遍历无法还原出确定性的二叉树来

    根据序列分析

    我们可以看到当给定中序遍历的时候和任意后序或前序遍历时,我们可以很容易的把根节点找到。
    比如分别有前序遍历和中序遍历:12463578和26417583
    我们可以很容易的就可以根据先序遍历确定1为根节点,接着在中序遍历中找到1。1左边的就是左子树,右边的是右子树。
    递归上述过程可以很容易就得出来完整且唯一的二叉树
    ———————————————————————————————————————————————————————————————————————————————————————————————————
    但是如果我给定一个先序遍历序列和后序遍历序列:ABDE和DBEA
    我们只能知道根节点是A,而对剩下的结构无法肯定。
    因为我们观察后序遍历可以看到D是第一个被遍历的,这说明D必然为叶子节点。所以E肯定是A的有孩子
    但是对于B和D我们无法肯定,我们唯一能确定的就是B是D的父亲节点
    所以对于上述两个序列有两种可能:
    在这里插入图片描述
    ————————————————————————————————————————————————————————————

    代码实现

    定义树的结构.h文件

    #ifndef CONSTRUCT_H_
    #define CONSTRUCT_H_
    struct BTree
    {	
    	int val;
    	BTree *left;
    	BTree *right;
    	BTree(int x):val(x),left(nullptr),right(nullptr){}
    };
    #endif // CONSTRUCT_H_
    

    主体结构

    #include<iostream>
    #include"define_tree.h"
    #include<vector>
    using namespace std;
    //返回根节点在中序遍历中的位置
    int get_index(int *obj,int a,int length) {
    	for (int i = 0;i < length- 1;i++) {
    		if (obj[i]==a) {
    			return i;
    		}
    	}
    }
    //根据前序和中序还原二叉树
    BTree *build_tree_bypre(int *pre,int *mid,int length) {
    	//递归终止条件
    	if (length<=0) {
    		return 0;
    	}
    	BTree *root = new BTree(pre[0]);
    	int index = get_index(mid,root->val,length);
    	root->left=build_tree_bypre(pre+1,mid,index);
    	root->right = build_tree_bypre(pre+index+1,mid+index+1,length-index-1);
    	return root;
    }
    //根据中序和后序还原二叉树
    BTree *build_tree_bybac(int *bac, int *mid,int length) {
    	//递归终止条件
    	if (length <= 0) {
    		return 0;
    	}
    	BTree *root = new BTree(bac[length-1]);
    	int index = get_index(mid,root->val,length);
    	root->left = build_tree_bybac(bac,mid,index);
    	root->right = build_tree_bybac(bac+index,mid+index+1,length-index-1);
    	return root;
    }
    
    //中序遍历二叉树
    void mid_order(BTree *root) {
    	if (root==nullptr) {
    		return ;
    	}
    	mid_order(root->left);
    	cout << root->val << " ";
    	mid_order(root->right);
    }
    int main() {
    	int  pre[] = {4,1,3,2,6,5,7};
    	int  mid[] = {1,2,3,4,5,6,7};
    	int  back[] = {2,3,1,5,7,6,4};
    	int length = 7;
    	mid_order(build_tree_bybac(back, mid, length));
    	cout << endl;
    	mid_order(build_tree_bypre(pre, mid, length));
    	system("pause");
    	return 0;
    }
    
    
    展开全文
  • 根据先序序列确定树的根结点 根据根结点在中序序列中划分出二叉树的左、右子树中包含哪些结点,然后根据左、右子树结点在先序序列中确定子树的根结点,即返回步骤1 //初始值l1=l2=1,h1=h2=n BiTree PreInCreate(int...

    前言

    二叉树这两道题有点不太明白记录下来

    正文

    题目一

    设一颗二叉树各结点的值互不相同,其先序遍历序列和中序遍历序列分别存在两个一维数组A[1…n]和B[1…n]中,试编写算法建立该二叉树的二叉链表
    关键找到循环体:

    1. 根据先序序列确定树的根结点
    2. 根据根结点在中序序列中划分出二叉树的左、右子树中包含哪些结点,然后根据左、右子树结点在先序序列中确定子树的根结点,即返回步骤1
    //初始值l1=l2=1,h1=h2=n
    BiTree PreInCreate(int a[],int b[],int l1,int h1,int l2,int h2){
    	BiTNode *root=(BiTNode *)malloc(sizeof(BiTNode));
    	root->data=a[l1];//在先序序列中找到root 
    	for(int i=l1;b[i]!=root->data;i++);//找到root在中序序列中的位置 
    	int llen=i-l2;//划分为左右部分(不含该root) 
    	int rlen=h2-i;
    	if(len)      //递归建立左右子树 
           root->lchild=PreInCreate(a,b,l1+1,l1+llen,l2,l2+llen-1);//先序和中序遍历中的左子树界限 
        else
           root->lchild=NULL;
        if(rlen)
           root->rchild=PreInCreate(a,b,h1-rlen+1,h1,h2-rlen+1,h2);//先序和中序遍历中的右子树界限 
        else
           root->rchild=NULL;
        return root;
    }
    

    题目二

    对于一颗满二叉树(所有结点值均不同)已知先序pre,求后序序列post
    关键:满二叉树利用先序才能确定后续,其任意一个结点的左、右子树均含有相等的结点数,同时先序序列的第一个结点也是后序序列的最后一个结点
    每次递归,根结点从头(先序序列中的l1)移动到尾(后序序列中的h2),然后取中间位置half,划分为左右子树,将其从先序中移动到后序相应位置。
    左子树:pre[l1+1,l1+hlaf]转为post[l2,l2+half-1]
    右子树:pre[l1+half+1,h1]转为post[l2+half,h2-1]
    在这里插入图片描述

    BiTree PreToPost(int pre[],int l1,int h1,int post[],int l2,int h2){
    	int half;
    	if(h1>=l1){
    		post[h2]=pre[l1];
    		half=(h1-l1)/2;//取中间位置 
    		PreToPost(pre,l1+1,l1+half,post,l2,l2+half-1);//转换左子树 
    		PreToPost(pre,l1+half+1,h1,post,l2+half,h2-1);//转换右子树 
    	} 
    }
    
    展开全文
  • 先序序列和后序序列不能唯一确定一棵二叉树,因无法确定左右子树两部分。 反例:任何结点只有左子树的二叉树和任何结点只有右子的二叉树,其前序序列相同,后序序列相同,但却是两棵不同的二叉树。
  • 一、前序和后序遍历 二、题解 解题思路: 还是可以根据一般的思路,采用递归思想,对于每一个先序序列,划分出对应的根节点、左子树、右子范围即可自上而下构建出二叉树。 例如对于上例中的先序序列[1,2,4,5,3,6...
  • 二叉树的建立用了递归的...由前序和中序遍历或由中序和后序遍历序列可以唯一确定一棵二叉树,而由前序和后序遍历序列不能唯一确定一棵二叉树前序和后序在本质上都是将父节点与子结点进行分离,但并没有指明左子树和右子
  • 以前大学学数据结果的时候,我们就知道,根据一棵先序遍历中序遍历,或者后序遍历中序遍历序列,都可以唯一地确定一棵
  • 只要清楚了先序中序后序的含义 先序是中左右 中序是左中右 后序是左右中 那么我们只要在递归的: 在先序列里取第一个元素 这个元素就是根元素 然后在中序列里找到根 根的左边(左子树)作为下一次递归的(左)中序列...
  • 根据先序排序的特点我们可以知道,如果我们选中其中某一节点,它右边的节点一定是先排列完左子树,再排列右子。 那么我们能否根据这两个规律,确定唯一的二叉树? 如果确定能够构造唯一的二叉树,那么根据后序遍历...
  • (只有先序和后序是无法唯一确定一颗二叉树的)在网上查资料的时候很少看到将两个合起来写的,但其实其过程有相似性,用结构相似的代码更能体现其算法本质。书中给出了先序加中序的解法,解法的思想是递归,基本上...
  • 根据先序和中序输出后序遍历

    千次阅读 2019-01-09 20:51:23
    题目描述: 二叉树的前序、中序、后序遍历的定义: 前序遍历:对... 给定一棵二叉树的前序遍历中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。 输入描述: 两个字符串,其长...
  • //根据先序遍历结果和中序遍历结果确定唯一的二叉树,根据中序遍历结果和后序遍历结果确定唯一的二叉树 import java.util.*; public class Rebuild_Tree { public static void main(String args[]){ int pre[]=new...
  • 思考:如何才能确定一棵?... 通过先序遍历和后序遍历确定不了一个。 算法实现: (一)先序和中序重建二叉树,按层次遍历输出 #include &lt;iostream&gt; #include &lt;cstdio&gt; #i...
  • 今天看姥姥的视频, 继续深入了解二叉树的遍历 ...确定后序: pre第一个就是root 排最后, 然后根据in, 1为root, 左树是3,2,4,右6,5 pre接着暴露root是2, 根据in, 左树3,2,4 中,2是root, 3左,4右. pre接...
  • 而由先序和后序可以很容易确定根结点,因此,先序和中序或者后序和中序可以唯一确定二叉树。 此处运用递归的方法,仅以先序和中序序列为代表,给出重建二叉树的代码,供大家参考。 2.核心代码 //根据先序和中序...
  • 根据两种遍历顺序确定树结构(build-tree) 题目描述 输入 第1行:二叉树的前序遍历顺序 第2行:中序遍历顺序 输出 二叉树的后序遍历顺序 样例输入 ABCDEFGH CBEDAGHF 样例输出 CEDBHGFA   分析: 这道题最核心的...
  • 如果中只存在度为0和度为2的节点,则根据它的前序遍历和后序遍历序列,可以重构树的结构 存在1 度的节点,那么不能重构出一个唯一的 Fixed 原文 以前大学学数据结果的时候,我们就知道,根据一棵先序遍历...
  • 根据中序遍历 先序遍历构建 输出后序遍历 后序遍历为左右根 递归的返回条件中序遍历中 左子树右子 1. 过i将中序遍历中的分为左子树右子 (i为中序遍历的根节点(需要输出的结点(每棵都是自己 的根结点)...
  • 已知一棵二叉树的先序遍历序列中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后序遍历序列。 分析:先序遍历序列的第一个字符为根结点。对于中序遍历,根结点在中序遍历序列的中间,左边部分是根..
  • C++先序和中序确定二叉树

    千次阅读 2018-05-25 15:16:10
    思考:如何才能确定一棵?结论: 通过中序遍历和先序遍历可以确定一个 通过中序遍历和后续...根据先序和中序结果画算法1、通过先序遍历找到根结点A,再通过A在中序遍历的位置找出左子树,右子2、在A的左子...
  • 已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及后序遍历结果,要求输出其先序遍历结果...
  • 已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及后序遍历结果,要求输出其
  • 先序和中序遍历序列来确定一棵二叉树 【分析】 ◆根据先序遍历序列第一个结点确定根结点; ◆根据根结点在中序遍历序列中分割出左右两个子序列 ◆对左子树和右子分别递归使用相同的方法继续分解。 ...
  • #105. Construct Binary Tree from Preorder and In...因为题目中说这棵没有重复的项,因此根据这个根元素在中序遍历中的位置,可以分别确定先序和中序数组中左右子树的下标。然后再递归。 var buildTree = func...
  • /*根据二叉树的前序序列中序序列建立该二叉树。这个过程是 *一个递归过程,其基本思想是:先跟据前序序列的第一个元素建立 *根节点,然后在中序序列中找到该元素,确定根节点的左、右子的中序序列; *再再...

空空如也

空空如也

1 2 3 4 5 6
收藏数 114
精华内容 45
关键字:

根据先序和后序确定树