精华内容
下载资源
问答
  • 2.已知先序遍历和中序遍历,可以建立二叉树。 3.已知中序遍历和后序遍历,可以建立二叉树。 4.已知先序遍历和后序遍历,无法建立二叉树。 下面来看洛谷p1030 https://www.luogu.org/problemnew/show/P1030 参考...

    1.已知先序遍历、中序遍历、后序遍历中的任意一种方式,都无法建立起二叉树。

    2.已知先序遍历和中序遍历,可以建立二叉树。

    3.已知中序遍历和后序遍历,可以建立二叉树。

    4.已知先序遍历和后序遍历,无法建立二叉树。

    下面来看洛谷p1030

    https://www.luogu.org/problemnew/show/P1030

    参考题解中的思路:

    首先定义两个字符串inorder,postorder存储中序和后序遍历结果,

    我们从后序遍历最后一个字符找到根结点,在中序遍历中由根结点分为左子树和右子树两个部分,

    根据左右子树结点的个数,在后序遍历中找到相应的左子树和右子树。

    所以我们可以重新得到左右子树的中序遍历和后序遍历,可以用递归解决此问题。

    #include<cstdio>
    #include<iostream>
    #include<string>
    using namespace std;
    void preorder(string inorder,string postorder){
    	if(!inorder.size())return;
    	char root=postorder[postorder.length()-1];
    	cout<<root;
    	int k=inorder.find(root);
    	preorder(inorder.substr(0,k),postorder.substr(0,k));//左子树 
    	preorder(inorder.substr(k+1),postorder.substr(k,postorder.length()-k-1));//右子树 
    	
    }
    int main(){
        string inorder,postorder;
        cin>>inorder>>postorder;
        preorder(inorder,postorder);
        return 0;
    }

    对于已知先序遍历和中序遍历,求后序遍历的问题,思路是一样的。

    下面附上用Python代码

    class Node:
        def __init__(self,data,left=None,right=None):
            self.data=data
            self.left=left
            self.right=right
    def build(preorder,inorder):
        if not inorder:
            return
        root = Node(preorder[0])
        index = inorder.find(preorder[0])
        root.left=build(preorder[1:index+1],inorder[0:index])
        root.right=build(preorder[index+1:],inorder[index+1:])
        return root
    
    def postorder(t):
        if t==None:
            return
        postorder(t.left)
        postorder(t.right)
        print(t.data,end='')
    preorder="ABDHIEJCFGKL"
    inorder="HDIBEJAFCKGL"
    if __name__=='__main__':
        tree=build(preorder,inorder)
        postorder(tree)

     

    展开全文
  • 题目:已知二叉树先序遍历+中序遍历 后序遍历 对于一棵二叉树,给定其先序遍历的结果序列和中序遍历的结果序列,请写出其后序遍历的结果序列。 输入样例: GDAFEMHZ(先序遍历的结果序列) ADEFGHMZ(中序...

    题目:已知二叉树先序遍历+中序遍历 求后序遍历

    对于一棵二叉树,给定其先序遍历的结果序列和中序遍历的结果序列,请写出其后序遍历的结果序列。

     

    输入样例:

    GDAFEMHZ(先序遍历的结果序列)

    ADEFGHMZ(中序遍历的结果序列)

    输出样例:

    AEFDHZMG(后序遍历的结果序列)

     

    思路分析👇

    • 因为前序遍历的首个元素即为根节点,且在中序遍历中根节点前的元素位于左子树,根节点后的元素位于右子树。
    • 利用这一性质,可以把问题看成一个递归问题
    • 递归过程是从前序遍历结果中找到中序遍历时根节点前的元素,构成了根的左子树的前序遍历结果,将二者作为参数再传入函数;再从前序遍历结果中找到中序遍历时根节点后的元素,构成了根的右子树的前序遍历结果,将二者作为参数再传入函数
    • 题目要求后序遍历的顺序输出,所以最后再输出根节点的元素值

    代码示例👇

    //author:Mitchell_Donovan
    //date:4.25
    #include<iostream>
    using namespace std;
    
    void run(string A, string B);
    
    int main() {
    	string pre;
    	cout << "请输入后序遍历结果:";
    	cin >> pre;
    	string in;
    	cout << "请输入中序遍历结果:";
    	cin >> in;
    	cout << "后序遍历结果:";
    	run(pre, in);
    }
    
    void run(string A, string B) {
    	if (B.length() == 0) {
    		return;
    	}
    	if (B.length() == 1) {
    		cout << A.front();
    		return;
    	}
    	//substr(0,x)左闭右开
    	//substr(x,y)左闭右闭
    	//substr(x)左闭右末尾
    	run(A.substr(1, B.find(A.front())), B.substr(0, B.find(A.front())));
    	run(A.substr(B.find(A.front()) + 1), B.substr(B.find(A.front()) + 1));
        //根据后序遍历的顺序,最后再输出根节点的元素值
    	cout << A.front();
    }

    输出示例👇

    补充内容

    👉substr(0,x)左闭右开
    👉substr(x,y)左闭右闭
    👉substr(x)左闭右末尾

    展开全文
  • 根据二叉树先序遍历和中序遍历构建二叉树

    万次阅读 多人点赞 2019-04-24 21:20:37
    欢迎使用 Cmd Markdown 编辑阅读器...此问题变成了根据左子树的先序和序列构建左子树的二叉树,根据右子树的先序和中序序列构建右子树的二叉树问题得以分解成子问题 ​​ 令先序序列和中序序列在数组中连续存放。...

    前方有一个人在等着你,你只管勇敢的向前走


    采用递归分治的思想,将一个大问题划分成子问题,

    对于本题,根据二叉树先序遍历和中序遍历构建二叉树,思路:

    • 我们可以求得根节点左子树的先序和中序序列,以及右子树的先序和中序序列
    • 此问题变成了根据左子树的先序和序列构建左子树的二叉树,根据右子树的先序和中序序列构建右子树的二叉树问题得以分解成子问题

    在这里插入图片描述
    ​​
    令先序序列和中序序列在数组中连续存放。

    设先序序列第一个字母的数组中的位置为Xb,最后一个字母的数组中的位置为Xe,中序序列第一个字母的位置为Zb,最后一个字母的位置为Ze

    从中序序列中,能找到一个节点将当前二叉树分为左子树与右子树,设此节点位于中序序列的k位置

    左子树节点个数num=k-Zb

    所以左子树的先序序列区间[Xb+1,Xb+num];中序区间[Zb,k-1]

    右子树的先序区间[Xb+num+1,Xe],中序区间[k+1,Ze]


    ​​在这里插入图片描述

    而递归结束的条件是什么呢?

    我们可以考虑一下临界条件,即递归的最底层,当先序序列只剩一个节点D时,需要构造该节点,可当先序序列没有了的时候,说明二叉树就到尽头了,所以当先序序列的长度小于等于0时,为递归边界。

    代码思路:

    定义一个node类型的结构体;

    struct node
    {
    	char data;
    	node * lchild;
    	node * rchild;
    };
    

    步骤一:构造一个创造节点的createNode函数,函数里的参数即为先序序列区间,中序序列区间,createNode(Xb,Xe,Zb,Ze); 返回值类型为指向 node型的指针。

    1.判断是否到达递归边界,到达边界了就返回一个 NULL,即二叉树到达叶子的子节点(叶子节点是不存在子节点的,我就是想表示该节点不存在,不需要构造,要返回上一层,返回到叶子节点)

    即判断先序区间长度是否小于等于0,即Xb是否小于等于Xe

    2.没到达边界就构造节点

    
    node *Node=new node;
    
    node->data=data;
    

    3.在中序序列中找到将中序序列分为左子树和右子树的节点位置k

    for (int i = Zb; i <Ze+1; i++)
    	{
    		if (xianxu[Xb] == zhongxu[i])
    		{
    			k = i;
    			break;
    		}
    	}
    

    4.递归

    
    Node->lchild=create(Xb,Xe,Zb,Ze);
    
    Node->rchild=create(Xb,Xe,Zb,Ze)
    

    代码

    //根据先序中序,构造后序
    #include <iostream>
    #include <string>
    using namespace std;
    struct node
    {
    	char data;
    	node * lchild;
    	node * rchild;
    };
    node *createNode(int Xb, int Xe, int Zb, int Ze,string xianxu,string zhongxu);
    void houxu(node *Node);
    
    
    int main()
    {
    	string xianxu;
    	string zhongxu;
    	while (cin >> xianxu) {
    		
    		cin >> zhongxu;
    		int Xb, Xe, Zb, Ze;//Xb表示先序开始字符位置Xe表示先序结束字符位置 Zb表示中序开始字符位置,Ze表示中序结束字符位置
    		Xb = Zb = 0;
    		Xe = xianxu.length() - 1;
    		Ze = zhongxu.length() - 1;
    		node *Node = new node;
    		Node = createNode(Xb, Xe, Zb, Ze, xianxu, zhongxu);
    		houxu(Node);
    	}
    		system("pause");
    	return 0;
    }
    node *createNode(int Xb, int Xe, int Zb, int Ze,string xianxu,string zhongxu)
    {
    	if(Xb >Xe)
    		return NULL;
    	node *Node = new node;
    	Node->data = xianxu[Xb];
    	int k=0;
    	for (int i = Zb; i <Ze+1; i++)
    	{
    		if (xianxu[Xb] == zhongxu[i])
    		{
    			k = i;
    			break;
    		}
    	}
    	Node->lchild = createNode(Xb + 1, Xb+k-Zb, Zb, k - 1, xianxu, zhongxu);
    	Node->rchild = createNode(Xb+k-Zb + 1, Xe, k + 1, Ze, xianxu, zhongxu);
    	
    	return Node;
    
    }
    void houxu(node *Node)
    {
    	if (Node == NULL)
    		return;
    	houxu(Node->lchild);
    	houxu(Node->rchild);
    	cout << Node->data;
    }
    
    展开全文
  • 程序1(通过根节点的位置判断树的左右子树是否为空)://已知二叉树中序和先序遍历求二叉树的后续遍历 #include #include #include typedef struct BiTree { char data; struct BiTree *left,*right; }...

    根据二叉树先序遍历和中序遍历的特点,采用递归的方法求解。

    程序1(通过根节点的位置判断树的左右子树是否为空):

    //已知二叉树的中序和先序遍历,求二叉树的后续遍历
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef struct BiTree 
    {
    	char data;
    	struct BiTree *left,*right;
    }BiNode;              //定义结点结构
    
    //通过前序遍历和中序遍历创建二叉树
    void InitTree(BiNode *&root,char *front,char *middle,int num)
    {
    	int i=0;
    	root->data=front[0];
    	if (num==0)
    	    return ;
    	//找到根结点位置
    	for (i=0;i<num;i++)
    	{
    		if (middle[i]==root->data)
    		   break;
    	}
    	//如果有左子树
    	if(i!=0)
    	{           
    		root->left=new BiNode();          //BiNode之后的()可省略
    		InitTree(root->left,front+1,middle,i);
    	}
    	else
    		root->left=NULL;
    	//如果有右子树
    	if(i!=num-1)        
    	{
    		root->right=new BiNode();
    		InitTree(root->right,front+i+1,middle+i+1,num-i-1);
    	}
    	else 
    		root->right=NULL;
    }
    
    //后序遍历
    void PostOrder(BiNode *root)
    {
    	if (root==NULL)
    	   return;
    	PostOrder(root->left);
    	PostOrder(root->right);
    	printf("%c ",root->data);
    }
    //main函数,测试
    int main()
    {
    	BiNode *root=new BiNode;
    	char *front="ABDECF",*mid="DBEAFC";
    	int num=strlen(front);
        InitTree(root,front,mid,num);
    	PostOrder(root);
    	system("pause");
    	return 0;
    }

    程序2(与程序1类似,需要手动输入二叉树的前序和中序,不判断左右子树是否为空,通过len的值是否小于等于0,将叶子结点的左右子树置为NULL)

    转载出处http://blog.csdn.net/Java2King/article/details/5564418:

    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <string.h>
    typedef struct node
    {
    	char ch;
    	struct node *left,*right;
    }node;                   // 定义节点的结构 
    node * creat(char *pre,char *in,int len);
    void print(node *head);
    int main()
    {
    	int len;
    	char pre[30],in[30];    // 存储先序和中序遍历的序列 
    	node *head;
    	head=(node*)malloc(sizeof(node));
    	while(scanf("%s%s",pre,in)!=EOF)
    	{ 
    		len=strlen(pre);
    		head=creat(pre,in,len);
    		print(head);
    		printf("/n");
    	}
    	system("pause");
    	return 0;
    }
    // 通过前序遍历和中序遍历创建二叉树
    node * creat(char *pre,char *in,int len)  
    {  
    	int k;
    	if(len<=0) return NULL;
    	node *head=(node*)malloc(sizeof(node));
    	head->ch=*pre;
    	char *p;
    	for(p=in;p!=NULL;p++)                  // 在中序遍历的序列中得到与先序相同的节点
    		if(*p==*pre) break;                //即找到根结点在中序遍历的位置  
    	k=p-in;
    	head->left=creat(pre+1,in,k);          //递归调用得到左子树 
    	head->right=creat(pre+k+1,p+1,len-k-1);//得到右子树 
    	return head;
    }
    
    // 打印后序遍历序列 
    void print(node *head)  
    {
    	if(head==NULL) return ;
    	print(head->left);
    	print(head->right);
    	printf("%c",head->ch);
    }

    程序3. 不建立树,仅输出后序遍历

    #include <iostream>
    #include <fstream>
    #include <string>
    using namespace std;
    
    struct TreeNode
    {
    	struct TreeNode* left;
    	struct TreeNode* right;
    	char  elem;
    };
    
    void BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
    {
    	if(length == 0)
    	{
    		return ;
    	}
    //	TreeNode* node = new TreeNode;//Noice that [new] should be written out.
    	char node_value;
    	node_value = *preorder;
    	int rootIndex = 0;
    	for(;rootIndex < length; rootIndex++)//a variation of the loop
    	{
    		if(inorder[rootIndex] == *preorder)
    			break;
    	}
    	BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);
    	BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
    	std::cout<<node_value<<std::endl;
    	return ;
    }
    
    int main(int argc, char** argv)
    {
    	char* pr="GDAFEMHZ";    
    	char* in="ADEFGHMZ"; 
    	BinaryTreeFromOrderings(in, pr, 8);
    	printf("\n");
    	system("pause");
    	return 0;
    }
    参考原网页:http://blog.csdn.net/feliciafay/article/details/6816871

    展开全文
  • 假设现在有某二叉树先序遍历和中序遍历,我们应该如何建树? 基本思路: 分别求得根节点的左子树右子树的先序遍历序列与中序遍历序列 分别以左子树右子树为新树进行第一步操作 直至没有子树为止 那么我们...
  • 已知二叉树先序遍历中序遍历求其后序遍历 (注:已知中序遍历序列剩下两种遍历序列中的一种都可以确定二叉树,即可得到另一种遍历序列, 但是已知前序遍历和后序遍历序列并不能唯一确定二叉树,例如:preorder:...
  • 上一篇写到了如何构建一棵树并打印出他的四种遍历,今天按着上一次的代码接着写已知先序遍历和中序遍历后序遍历。 只要确定了中序遍历,加上另外一种遍历,我们就可以构造出一棵树 //已知前序中序求后序遍历 ...
  • 根据先序遍历和中序遍历求解二叉树步骤: ① 确定根节点。先序遍历中的第一个节点就是二叉树的根节点,然后根据根节点数值出其在中序遍历中的位置。 ② 求解二叉树的左右子树。根据根节点在中序遍历中的位置,...
  • title: 根据先序遍历和中序遍历建立二叉树 date: 2019-07-23 22:37:34 tags: 数据结构 问题 已知一棵二叉树先序遍历以及中序遍历,重建二叉树二叉树的每一个节点有三个属性,左子节点,右子节点,以及...
  • 二叉树先序遍历中序遍历、后序遍历 #include<stdio.h> #include<stdlib.h> typedef struct Node { char data; struct Node* lchild; struct Node* rchild; }BNode, *BiTree; void create_...
  • 对于一棵二叉树已知先序遍历ACDEFHGB,中序遍历DECAHFBG,后序遍历。 解题思路 首先条件给出了先序遍历和中序遍历,那么我们利用这两种遍历特性得到一下信息: 对于先序遍历,第一个节点是根节点 对于中序...
  • 算法思想:已知先序遍历和中序遍历,如何后序遍历?(1)确定树的根结点。树根是当前树中所有元素在先序遍历中最先出现的元素,即先序遍历的第一个结点就是二叉树的根。(2)解树的子树。找到根在中序遍历的位置,...
  • package algorithm01; import java.util.Scanner;... * 给出先序遍历和中序遍历序列二叉树的后续遍历序列 * @author wxisme * */ public class ToReverse { public static void main(String[] a...
  • 给出先序遍历和中序遍历后续遍历,要求: 函数头如下: bool getPostOrder(const char* perOrder, const char* inOrder, char* postOrder); 返回值是一个布尔 代表是否有这样的二叉树 用法: char* perorder ...
  •  输入一棵二叉树先序遍历和中序遍历,输出它的后序遍历。 输入输入有多组数据(少于100组),以文件结尾结束。 每组数据仅一行,包括两个字符串,中间用空格隔开,分别表示二叉树先序序列和中序序列(字符串...
  • 已经一个二叉树先序遍历ACDEFHGB,中序遍历DECAHFBG,后序遍历? 解题参考资料: 先序遍历 (1)访问根节点(2)先序遍历左子树(3)先序遍历右子树 中序遍历 (1)中序遍历左子树(2)访问根节点(3)中序遍历右子树 后序遍历...
  • 已知先序遍历序列和中序遍历序列建立二叉树。 例如输入先序遍历序列: ABDFGC, 再输入中序遍历序列: BFDGAC,则 输出该二叉树的后序遍历序列: FGDBCA。解析:函数中的三个参数,第一个是先序,第二个是后序,第三...
  • 由于先序遍历树的规则为:根左右,因此可以得到...由先序遍历和中序遍历求解二叉树的过程,步骤如下:①确定树的根节点。树根是当前树中所有元素在先序遍历中最先出现的元素,即先序遍历的第一个结点就是二叉树的根...
  • 题目 ...根据中序和先序遍历序列重构二叉树先序遍历特点可知,先序遍历第一个数据为根节点数据,则该二叉树的根节点值为preorder[0]=3 由中序遍历特点可知,根节点左边为左子树中序遍历结果,即[9]
  • #include<iostream> #include<vector>...//先序遍历数组,中序遍历数组,当前处理的先序遍历数组的开始索引,当前处理的先序遍历数组的结束索引,当前处理的中序遍历数组的开始索引,...
  • 2018.4.18 这道题说的是利用栈来模拟...理解了这点这道题就转换成已知先序遍历+中序遍历,打印二叉树的后序遍历的问题了。 有两个思路:1.根据先序遍历和中序遍历先构建一棵二叉树,再后序遍历打印这棵树;2....
  • 已知一个二叉树前序遍历中序遍历的结果,请确定该二叉树并输出其后序遍历的结果。 例如: 先序遍历结果为:A B D E G C F H; 中序遍历结果为:D B G E A C H F; 则应该能够得出后序遍历结果为:D G E B H F ...
  • 先序遍历中第一个字母即为根节点,在中序遍历中找到根节点的位置 ②把中序遍历的字符串序列从根节点分成两部分,左侧一部分构建左子树,右侧一部分构建右子树 ③在②的基础上在先序遍历中也找到构建左右子树的...
  • 树根是当前树中所有元素在先序遍历中最先出现的元素,即先序遍历的第一个结点就是二叉树的跟 (2)解树的子树。找到根在中序遍历的位置,位置左边就是二叉树的左孩子,位置右边是二叉树的右孩子,如果跟结点左边...
  • 给定这棵二叉树的前序遍历和中序遍历其后序遍历。 下图是依据下文算法代码绘制的示意图。【输入格式】 输入包含多组测试数据。 每组数据占两行,每行包含一个大写字母构成的字符串,第一行表示二叉树的前序遍历...
  • 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树...
  • 已知一棵二叉树中序遍历和后序遍历求二叉树先序遍历 Input 输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括两个长度小于50 的字符串,第一个字符串表示二叉树中序遍历序列,第...
  • 已知某一二叉树的先序遍历为:136945827,中序遍历为:963548127,二叉树的后续遍历 #include<iostream> #include<string> using std::cout; using std::endl; using std::string; class Node { ...
  • 如题,已知先序中序/后序中序建立一棵二叉树。 我们手工建树的时候,比如一个例子:先序序列:ADECFG,中序序列:DBEAFCG。首先我们都会从先序序列中找到第一个元素A,该元素也就是这个树的根。然后再在中序序列中...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,877
精华内容 7,950
关键字:

已知先序遍历和中序遍历求二叉树