精华内容
下载资源
问答
  • 已知后序和中序,重建这颗二叉树 前序:1 2 4 8 9 5 10 3 6 7 中序: 8 4 9 2 10 5 1 6 3 7 后序:8 9 4 10 5 2 6 7 3 1 #include<iostream> using namespace std; int post[100]={8,9,4,10,5,2,6,7,3,1...

    已知后序和中序,重建这颗二叉树
    前序:1 2 4 8 9 5 10 3 6 7
    中序: 8 4 9 2 10 5 1 6 3 7
    后序:8 9 4 10 5 2 6 7 3 1
    这种还原的二叉树是链式的

    #include<iostream>
    using namespace std;
    int post[100]={8,9,4,10,5,2,6,7,3,1};
    int in[100]={8,4 ,9,2,10,5,1,6,3,7};
    struct node{
    	int date;
    	node *lchild;
    	node *rchild;
    	node()
    	{
    		lchild=rchild=NULL;
    	}
    };
    void creat(node *&root,int inl,int inr,int postl,int postr)
    {
    	
    	if(postl>postr)
    	return ;
    	
    	root=new node;
    	root->date =post[postr];
    	
    	int k;
    	for(int i=inl;i<=inr;i++)
    	{
    		if(post[postr]==in[i])
    		{
    			k=i;
    			break;
    		}
    	}
    	
    	int num;
    	num=k-inl;
    	creat(root->lchild,inl,k-1,postl,postl+num-1);
    	creat(root->rchild,k+1,inr,postl+num,postr-1);
    }
    void preorder(node *root)
    {
    	if(root)
    	{
    		cout<<root->date <<" ";
    		preorder(root->lchild );
    		preorder(root->rchild );
    		
    	}
    }
    int main()
    {
    	node *root;
    	creat(root,0,9,0,9);
    	preorder(root);
    } 
    

    这种是把二叉树还原在数组中

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5;
    int in[maxn],post[maxn],a[maxn];
    int n;
    void find(int root,int inl,int inr,int postl,int postr)
    {
    	if(postr<postl) return ;
    	int k=0;
    	for(int i=inl;i<=inr;i++)
    	{
    		if(in[i]==post[postr])
    		{
    			k=i;
    			break;
    		}
    	}
    	a[root]=in[k];
    	int len=k-inl;
    	find(root*2,inl,k-1,postl,postl+len-1);
    	find(root*2+1,k+1,inr,postl+len,postr-1);
    }
    void print()//层序输出 
    {
    	queue<int>q;
    	q.push(1);
    	while(!q.empty())
    	{
    		int t=q.front();
    		q.pop();
    		cout<<a[t]<<" ";
    		if(a[t*2]!=0) q.push(2*t);
    		if(a[2*t+1]!=0) q.push(2*t+1);
    	}
    }
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>post[i];
    	}
    	for(int i=1;i<=n;i++)
    	{
    		cin>>in[i];
    	}
    	
    	find(1,1,n,1,n);
    	print();
    }
    
    展开全文
  • 二叉树已知后序和中序遍历求前序遍历,C++编写已通过编译
  • 根据后序和中序求先序: 按照常规思路递归实现,先递归生成左子树,再递归生成右子树 class node: #定义节点结构 def __init__(self, value = None, left = None, right=None): self.value = value self.left ...

    根据后序和中序求先序:

    按照常规思路递归实现,先递归生成左子树,再递归生成右子树

    class node:                          #定义节点结构
        def __init__(self, value = None, left = None, right=None):
            self.value = value
            self.left = left
            self.right = right
    
    def GetTwoTree(str1, str2):          #str1为后序  str2为中序
        root = node(str1[-1])            #先给第一个值
        Index = str2.index(root.value)   #根在中序中的索引
    
        leftstr2 = str2[: Index]         #中序中的左半部分
        maxindex = -1
        for i in leftstr2:               # 分离后序序列
            tmpindex = str1.index(i)
            if maxindex < tmpindex:
                maxindex = tmpindex
        if len(leftstr2) == 1:           #如果只有一个元素
            root.left = node(leftstr2)   #直接赋值
        elif len(leftstr2) == 0:         #如果没有元素 
            root.left = None             #空
        else:                            #否则递归
            root.left = GetTwoTree(str1[:maxindex+1], leftstr2)   #递归构造左子树
    
        rightstr2 = str2[Index+1:]          #中序中的右半部分
        if len(rightstr2) == 1:
            root.right = node(rightstr2)
        elif len(rightstr2) == 0:
            root.right = None
        else:
            root.right = GetTwoTree(str1[maxindex+1:-1], rightstr2)   #递归构造右子树
        return root
    
    def preTraverse(root):  #递归先序遍历
        if root != None:
            print(root.value)
            preTraverse(root.left)
            preTraverse(root.right)
    
    if __name__ == '__main__':
        str1 = 'FCDBGEA'                     #str1为后序结果  str2为中序结果
        str2 = 'CFBDAEG'
        root = GetTwoTree(str1, str2)        #构造二叉树
        preTraverse(root)                    #遍历输出
    

    补充:

    根据完全二叉树的层次遍历序列顺序构造二叉树
    class node:
        def __init__(self, value = None, left = None, right = None):
            self.value = value
            self.left = left
            self.right = right
    
    Quepre = [0,1,2,3,4,5,6]
    
    Que = [0]               #保证原序列从1开始编号
    for i in Quepre:
        Que.append(node(i))
    for i in range(1, len(Que)//2):
        Que[i].left = Que[i*2]
        Que[i].right = Que[i*2+1]
    
    def preTraverse(root):  # 递归先序遍历
        if root != None:
            print(root.value)
            preTraverse(root.left)
            preTraverse(root.right)
    
    preTraverse(Que[1])
    

     

    展开全文
  • 已知前序和中序输出后序 分析:因为前序(根左右)最先出现的总是根结点,所以令root为前序中当前的根结点下标(并且同时把一棵树分为左子树右子树)。start为当前需要打印的子树在中序中的最左边的下标,end为...

    已知前序和中序输出后序

     分析:因为前序(根左右)最先出现的总是根结点,所以令root为前序中当前的根结点下标(并且同时把一棵树分为左子树和右子树)。start为当前需要打印的子树在中序中的最左边的下标,end为当前需要打印的子树在中序中最右边的下标。递归打印这棵树的后序,递归出口为start > end。i为root所表示的值在中序中的下标,所以i即是分隔中序中对应root结点的左子树和右子树的下标。
    先打印左子树,后打印右子树,最后输出当前根结点pre[root]的值。
    输出的后序应该为:3, 4, 2, 6, 5, 1(左右根)

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 1010;
    //已知前序和中序输出后序
    //前序:1,2,3,4,5,6
    //中序:3,2,4,1,6,5
    int pre[] = {1, 2, 3, 4, 5, 6};
    int in[] = {3, 2, 4, 1, 6, 5};
    vector<int>v;
    void post(int root,int l,int r)//root为前序中根节点位置,l,r为中序起点和终点位置
    {
        if(l>r) return;
        int root1=l; //找出根结点在中序中的位置
        while(in[root1]!=pre[root]){
            root1++;
        }
        //由于后序遍历顺序为左右根,因此先依次左右遍历,后存根,
    
        //遍历左子树,左子树根节点在前序中位置,root+1
        //post(root-(r-root1+1),l,root1-1);
        post(root+1,l,root1-1);
        //遍历右子树,右子树根节点在前序中位置,root+(左子树节点数+1)
        post(root+root1-l+1,root1+1,r);
    
        v.push_back(pre[root]);
    
    }
    int main() {
        post(0,0,5);
        for(auto&it:v){
            cout << it << " ";
        }
        return 0;
    }
    

    已知后序和中序输出前序

    分析:因为后序的最后一个总是根结点,令i在中序中找到该根结点,则i把中序分为两部分,左边是左子树,右边是右子树。因为是输出先序(根左右),所以先打印出当前根结点,然后打印左子树,再打印右子树。左子树在后序中的根结点为root – (end – i + 1),即为当前根结点-(右子树的个数+1)。左子树在中序中的起始点start为start,末尾end点为i – 1.右子树的根结点为当前根结点的前一个结点root – 1,右子树的起始点start为i+1,末尾end点为end。
    输出的前序应该为:1, 2, 3, 4, 5, 6(根左右)

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 1010;
    //已知后序和中序输出前序
    //后序:3,4,2,6,5,1
    //中序:3,2,4,1,6,5
    int post[] = {3, 4, 2, 6, 5, 1};
    int in[] = {3, 2, 4, 1, 6, 5};
    vector<int>p;
    void pre(int root,int l,int r)//root为后序中根节点位置,l,r为中序起点和终点位置
    {
        if(l>r) return;
        int root1=l; //找出根结点在中序中的位置
        while(in[root1]!=post[root]){
            root1++;
        }
        //由于前序遍历顺序为根左右,因此先存根,再依次左右遍历
        p.push_back(post[root]);
        //遍历左子树,左子树根节点在后序中位置,root-(右子树结点数+1)
        pre(root-(r-root1+1),l,root1-1);
        //遍历右子树,右子树根节点在后序中位置,root-1,
        pre(root-1,root1+1,r);
    
    }
    int main() {
        pre(5,0,5);
        for(auto&it:p){
            cout << it << " ";
        }
        return 0;
    }
    

     

    展开全文
  • 随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。 输出:先序遍历结果 #include&lt;bits/stdc++.h&gt; using namespace std; const int...

    输入:第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。

    输出:先序遍历结果

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+5;
    int pre[31],l=0;
    void change(int mid[],int next[],int length){
        if(length){
            int index=0;
            int temp=next[length-1];
            pre[l++]=temp;
            while(index<length){
                if(mid[index]==temp)
                    break;
                index++;
            }
            change(mid,next,index);
            change(mid+index+1,next+index,length-index-1);
        }
    }
    int main (){
        int n,i;
        int mid[31],next[31];
        cin>>n;
        for(i=0;i<n;i++)
            cin>>next[i];//后序
        for(i=0;i<n;i++)
            cin>>mid[i];//中序
        change(mid,next,n);
        for(i=0; i<n; i++)
            cout<<" "<<pre[i];
        return 0;
    }
    
    
    

     

    展开全文
  • /*根据二叉树的前序序列和中序序列建立该二叉树。这个过程是 *一个递归过程,其基本思想是:先跟据前序序列的第一个元素建立 *根节点,然后在中序序列中... *(由后序和中序建立二叉树的思想与上面类似)  */ #inc
  • 已知二叉树后序遍历序列是DBCEFGHA,中序遍历序列EDCBAHFG,它的前序遍历的序列是?麻烦再画下这二叉树. 后续遍历的顺序是左右根,中序遍历的顺序是左根右这点应该懂吧由后续访问序列可以看出最后一个被访问的必定是...
  • #include&lt;iostream&gt;#include&lt;string&gt;#include&lt;fstream&gt;using namespace std;const int capacity=100;typedef struct TreeNode{ char data; struct TreeNode *l;...v...
  • 1020. Tree Traversals (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard ...Suppose that all the keys in a binary tree are distinct positive integers....
  •  两行,每行一个字符串,分别表示中序和后序排列 输出格式  一个字符串,表示所求先序排列 样例输入  BEADC  EBDCA 样例输出 ABECD 解题思路 关于这题其实解体思路很多,但是目前我发现最简单的只有一种。 先从...
  • 后序遍历的最后一个节点一定是根节点 (先设 last = n-1) ,所以在中序遍历中等于根节点的元素左右两侧分别是左子树右子树,last–,再递归建右子树左子树. 层序遍历就是借助队列来输出,先进先出. 一开始理解怎么...
  • Construct Binary Tree from Inorder and Postorder Traversal一、问题描述给定树的中序遍历和后序遍历,构造二叉树。假定树中不存在重复项中序 = [9,3,15,20,7]后序 = [9,15,7,20,3]返回下列二叉树: 3 / \ 9 20...
  •  已知后序和中序求层序 思路:  注意建树时候的参数即可,观察1020与1086题的建树的写法 中序的参数类都是 inl到p1-1 p1+1到inr,注意总结  #include #include #include using namespace std; const ...
  • 已知后序和中序,求层序!     可以先来理解一下一个模板: 模板解决了已知先序和中序,重建二叉树的问题!遇到这种题,如果不会熟练,建议先画个图,在图中分析! //一个已知先序和中序,重建...
  • 二叉树的相互求解 已知前序中序求后序 已知后序前序求中序 已知前序后序求中序
  • 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式: 输入第一行给出一个正整数NN(\le 30≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。...
  • //中序 int flag; queue<int>q; void build(int &x,int l,int r,int ll,int rr){ if(l>r)return; x=post[r]; int index; for(int i=ll;i;i++){ if(in[i]==x){ index=i;break; } } build(t[x][0],l,l+...
  • /*************************************  *因为后序的最后一个data肯定是一个root节点,  *然后在中序中找出这个data的position, ... *以可以用被分开的后序的两部分和中序用同样  *的方法来
  • 已知二叉树的后序 中序 遍历 求层次遍历 基本上 熟练的话 15分钟-20分钟AC这类问题 #include <iostream> #include #include #include #include #include #include #include #...
  • 已知后序和中序,计算先序的(c/c++)方法实现 #include #include using namespace std; char epi[30]; char in[30]; int find(char c,char a[],int s,int e) { for(int i=s; i; i++) if(a[i]==c) return i; } void ...
  • 已知后序中序输出前序(先序) 已知后序中序输出前序(先序): 后序:3, 4, 2, 6, 5, 1(左右根) 中序:3, 2, 4, 1, 6, 5(左根右) 分析:因为后序的最后一个总是根结点,令i在中序中找到该根结点,则i把...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,114
精华内容 3,645
关键字:

已知后序和中序