精华内容
下载资源
问答
  • 下面三种序列可以唯一的构造唯一的一棵二叉树: 前序序列和中序序列构造二叉树 后序序列和中序序列构造二叉树 层次遍历序列和中序遍历序列构造二叉树 #include<stdio.h> #include<stdlib.h> #...

    下面三种序列可以唯一的构造唯一的一棵二叉树:

    前序序列和中序序列构造二叉树  

    后序序列和中序序列构造二叉树

    层次遍历序列和中序遍历序列构造二叉树  

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    #define MaxSize 10
    typedef struct BTNode{
    	char data;
    	struct BTNode *lchild,*rchild;
    }BTNode,*BiTree;
    
    //根据前序序列,中序序列建造一棵二叉树
    //参数含义:pre[]前序序列  in[]中序序列
    //			L1  R1用于指定pre[]的搜索区域
    //			L2  R2用于指定in[]的搜索区域 
    BiTree createBiTree(char pre[],char in[],int L1,int R1,int L2,int R2){
    	if(L1>R1){
    		return NULL;//递归出口 
    	}
    	BTNode *s =(BTNode*)malloc(sizeof(BTNode));
    	s->lchild =NULL;
    	s->rchild =NULL;
    	s->data=pre[L1];
    	int i;
    	//根据中序序列的特性,元素左边的元素属于该节点的左孩子序列,右边则是右孩子序列 
    	for(i=L2;i<=R2;i++){
    		if(pre[L1]==in[i]) break;//在中序序列找到该元素 
    	}
    	s->lchild=createBiTree(pre,in,L1+1,L1+i-L2,L2,i-1);//递归 
    	s->rchild=createBiTree(pre,in,L1+i-L2+1,R1,i+1,R2); 
    	
    	return s;
    }
    //根据后序中序建立二叉树 
    BiTree createBiTree2(char post[],char in[],int L1,int R1,int L2,int R2){
    	if(L1>R1){
    		return NULL;//递归出口 
    	}
    	BTNode *s =(BTNode*)malloc(sizeof(BTNode));
    	s->lchild =NULL;
    	s->rchild =NULL;                   
    	s->data=post[R1];//后序序列最后一个节点为根节点 
    	int i;
    	//根据中序序列的特性,元素左边的元素属于该节点的左孩子序列,右边则是右孩子序列 
    	for(i=L2;i<=R2;i++){
    		if(post[R1]==in[i]) break;//在中序序列找到该元素 
    	}
    	//递归 面试官:为什么要减去L2? 答:递归传下去的是整个数组,需要根据参数找到递归出口,-L2是缩小查找范围 
    	s->lchild=createBiTree2(post,in,L1,L1+i-L2-1,L2,i-1);
    	s->rchild=createBiTree2(post,in,L1+i-L2,R1-1,i+1,R2); 
    	
    	return s;
    }
    //该函数用于在中序序列中找到key,返回其位置 
    //参数含义:in[]:中序序列  key:所要查找元素 L,R:查找范围 
    int serach(char in[],char key,int L,int R){
    	for(int i=L;i<=R;i++){
    		if(in[i]==key) return i;
    	}
    	return -1;
    }
    
    //因为在中序序列元素的左面的元素在层次遍历序列中并不连续,所以需要用子序列函数将并不连续的序列连续起来
    //为什么要连续起来?因为需要连续起来才能和中序序列构造出二叉树
    //思路:在中序序列里查找到一个范围,从这个范围里遍历元素,在层次遍历序列里找该元素 
    //参数含义:sublevel[]:存放子序列数组  level[]:层次遍历序列  in[]:中序序列 n:level层次序列长度 L,R:查找范围 
    void getSubLevel(char sublevel[],char level[],char in[],int n,int L,int R){
    	int k=0;
    	for(int i=0;i<n;i++){
    		if(serach(in,level[i],L,R)!=-1)
    		   sublevel[k++]=level[i]; 
    	}
    }
    //由中序序列和层次遍历序列构造二叉树 
    BiTree createBiTree3(char level[],char in[],int n,int L,int R){
    	if(L>R) return NULL;
    	BTNode *s =(BTNode*)malloc(sizeof(BTNode));
    	s->lchild =NULL;
    	s->rchild =NULL;                   
    	s->data=level[0];
    	int i=serach(in,level[0],L,R);
    	//找到i便可以确定左右子树答大小 
    	int LN=i-L; char LLevel[LN];
    	int RN=R-i; char RLevel[RN];
    	getSubLevel(LLevel,level,in,n,L,i-1);//得到子序列 
    	getSubLevel(RLevel,level,in,n,i+1,R);
    	
    	s->lchild=createBiTree3(LLevel,in,LN,L,i-1);//用子序列递归 
    	s->rchild=createBiTree3(RLevel,in,RN,i+1,R); 
    	return s;
    }
    void visit(BiTree T) {
    	printf("%c  ",T->data);
    }
    //前序遍历 
    void PreOrder(BiTree T){
    	if(T!=NULL){
    		visit(T);//根 
    		PreOrder(T->lchild);//左 
    		PreOrder(T->rchild);//右 
    	}
    } 
    //中序遍历 
    void InOrder(BiTree T){
    	if(T!=NULL){
    		InOrder(T->lchild);
    		visit(T);
    		InOrder(T->rchild);
    	}
    }
    //后序遍历 
    void PostOrder(BiTree T){
    	if(T!=NULL){
    		PostOrder(T->lchild);
    		PostOrder(T->rchild);
    		visit(T);
    	}
    } 
    //层次遍历 
    void level(BiTree T){
    	if(T!=NULL){
    		int front=0;
    		int rear=0;
    		BiTree queue[MaxSize];
    		BiTree p;
    		p=T;
    		rear=(rear+1)%MaxSize;
    		queue[rear]=p;
    		while(rear!=front){
    			front=(front+1)%MaxSize;
    			p=queue[front];
    			visit(p); 
    			if(p->lchild!=NULL){
    				rear=(rear+1)%MaxSize;
    				queue[rear]=p->lchild; 
    			} 
    			if(p->rchild!=NULL){
    				rear=(rear+1)%MaxSize;
    				queue[rear]=p->rchild;
    			}
    			
    		}
    	}
    }
    int main(){
    	char c[]="ABDECFGH";//前序序列 
    	char d[]="DBEACGFH";//中序序列 
    	char p[]="DEBGHFCA";//后序序列 
    	char l[]="ABCDEFGH";//层次遍历序列 
    	BTNode *r=createBiTree(c,d,0,7,0,7);
    	BTNode *r2=createBiTree2(p,d,0,7,0,7);
    	BTNode *r3=createBiTree3(l,d,8,0,7); 
    	printf("前序序列为:"); 
    	PreOrder(r);
    	printf("\n");
    	printf("后序序列为:");
    	PostOrder(r2);
    	printf("\n");
    	printf("中序序列为:"); 
    	InOrder(r3);
    	printf("\n");
    	printf("层次遍历为:");
        level(r3); 
    	printf("\n");
    	
    } 

    代码运行截图:

    展开全文
  • 由中根序列和后根序列重建二叉树

    千次阅读 2017-04-30 23:22:14
    本题输入一棵二叉树的中根序列和后根序列,要求在内存中重建...用不同的整数来唯一标识二叉树的每一个结点,下面二叉树根序列是9 5 32 67后根序列9 32 67 5前根序列5 9 67 32输入两行。第一行是二叉树的中根序列

    http://dsalgo.openjudge.cn/binarytree/4/

    总时间限制: 500ms 内存限制: 65535kB

    描述
    本题输入一棵二叉树的中根序列和后根序列,要求在内存中重建二叉树,最后输出这棵二叉树的前根序列。

    用不同的整数来唯一标识二叉树的每一个结点,下面的二叉树

    这里写图片描述

    中根序列是9 5 32 67

    后根序列9 32 67 5

    前根序列5 9 67 32

    输入

    两行。第一行是二叉树的中根序列,第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0~65535。暂不必考虑不合理的输入数据。

    输出
    一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。

    样例输入
    9 5 32 67
    9 32 67 5
    样例输出
    5 9 67 32

    
    
    #include <iostream>
    using namespace std;
    #define MAX 63556
    int zhong[MAX];
    int hou[MAX];
    
    int find_root(int back, int rootn){//在后序中找到树中的左半边子树的root
    
        // rootn是树的root
        // back是树的右半边子树的节点个数
    
        return hou[rootn-back-1];
    }
    
    void build_tree(int begin, int num, int root, int rootn){
        //cout<<begin<<" "<<num<<" "<<root<<endl;
    
        // begin: 子树前序和后序打头的序号,两者相同
        // num:  子树的长度
        // root: 子树的根
        // rootn:  子树的根在后序当中的序号
    
        cout<<root<<" ";
        if (num<=1){return;}
    
        int j=1;
        int temp=begin;
        while(zhong[temp]!=root){ temp++; j++;}
        j--;
        int r=num-1-j;
        if (r<0) return;
    
        // temp是中序当中的root位置
        // j是root前面的个数
        //r是剩下的个数
    
        int a = find_root(r,rootn);
        // 在后序中找到左半边的root=a
    
        build_tree(begin,j,a,rootn-r-1);
        // 对左半边的进行递归
    
        if (r>0){
    
            a= hou[rootn-1];
            // 找到右半边的root
    
            build_tree(temp+1,r,a,rootn-1);}
           // 对右半边的进行递归
    
    }

    这里写图片描述

    
    int main(){
    
    
        int i=0;
        while(cin>>zhong[i++]){
            if (cin.get()!=' ') break;
        }
        //cin是跳过“空白”的;但是cin完一个数之后,“光标”还是在“空白”前面,cin.get()可以取到这个空白*
        i=0;
        while(cin>>hou[i++]){
            if (cin.get()!=' ') break;
        }
    
        // i等于数字的个数
        build_tree(0,i,hou[i-1],i-1);
        cout<<endl;
            return 0;
    }
    
    展开全文
  • 问题:已知二叉树的后根序列和中根序列,请构造此二叉树。  分析:对于提供了后根序列和中根序列的一棵二叉树,其结构信息是完备的。考虑后根序列a(1)->a(n),中根序列b(1)->b(n)。我们知道中根序列b(1)->b(n)包含...
     问题:已知二叉树的后根序列和中根序列,请构造此二叉树。

     分析:对于提供了后根序列和中根序列的一棵二叉树,其结构信息是完备的。考虑后根序列a(1)->a(n),中根序列b(1)->b(n)。我们知道中根序列b(1)->b(n)包含一颗完整的二叉树,那么中根序列里面肯定有一个元素b(i)是该二叉树的根。而根据中根序列的定义,b(i)前面的元素构成的一个序列b(1)->b(i-1)是该二叉树左子树的中根序列,b(i)后面的元素构成的序列b(i+1)->b(n)是该二叉树的右子树的中根序列。则由b(x)->b(y)产生一棵二叉树的过程可以递归的表述为:
                                                1.
    找到b(x)->b(y)中的某个元素b(i)作为该树的根
                                                2.
    b(x)->b(i-1)产生一棵二叉树作为该树的左子树
                                                3.
    b(i+1)->b(y)产生一棵二叉树作为该树的右子树
    现在问题归结到寻找根节点b(i),这时候就需要用到后根序列a(1)->a(n),由后根序列的定义可知,对任何一颗树(包括后根序列本身表达的那棵树和该树的所有子树),其根节点一定出现在它包含的其他节点之后,那么只要找到b(x)->b(y)中最后在后根序列里出现的元素,就是我们要的b(i),具体步骤如下:
                                                1.
    设置循环,从a(1)->a(n)依次取出a(j)
                                                2.
    对每一个a(j),找到它在b(1)->b(n)中对应的序号j',b(j')=a(j)
                                                3.
    x<j'<y,则跳出循环,b(j')即为b(i)

     

    实例(百练—2015研究生上机测试)

    描述:输入一棵二叉树的中根序列和后根序列,要求在内存中重建二叉树,最后输出这颗二叉树的先根序列。

    用不同的整数来唯一标识二叉树的每一个结点,下面的二叉树

                      5

                 /         \

              9            67

                         /

                     32

    中根:9 5 32 67

    后根:9 32 67 5

    先根:5 9 67 32


    输入:两行,第一行是二叉树的中根序列,第二行是后根序列。每个数字表示的结点之间用空格分隔。结点数字范围0~65535

    输出:二叉树的先根序列。每个数字表示的结点之间用空格分隔。

    样例输入:

    9 5 32 67

    9 32 67 5

    样例输出:

    5 9 67 32

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    using namespace std;
    
    vector<int> BinTree;    //存储输入的中根序列和后根序列
    int Btree[65536];       //二叉树的顺序存储
    
    void travel(int x,int y,int r,int index){
        Btree[index]=BinTree[r];                //顺序存储重建的二叉树
        if(x==y)
            return;
    
        int j,left,right;
        for(j=x;j<=y;j++)
            if(BinTree[j]==BinTree[r])          //寻找根节点
                break;
    
        if(x<j){
            left=r-y+j-1;                       //左子树根节点
            printf(" %d",BinTree[left]);        //输出二叉树的先根序列
            travel(x,j-1,left,index<<1);        //构造左子树
        }
        if(j<y){
            right=r-1;                          //右子树根节点
            printf(" %d",BinTree[right]);       //输出二叉树的先根序列
            travel(j+1,y,right,(index<<1)+1);   //构造右子树
        }
    }
    
    int main(){
        freopen("in.txt","r",stdin);    //调试
    
        int a,n=0;
        while(scanf("%d",&a)!=EOF){
            BinTree.push_back(a);
            n++;
        }
    
        memset(Btree,-1,sizeof(Btree)); //顺序存储数组的初始化
        printf("%d",BinTree[n-1]);      //输出二叉树的先根序列
        travel(0,(n>>1)-1,n-1,1);
    
        fclose(stdin);
        return 0;
    }
    

    展开全文
  • 反过来,如果给定二叉树的中根序列和后根序列,或者给定中根序列和前根序列,可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列,要求在内存中重建二叉树,最后输出这棵二叉树的前根序列。 用不同的整数来...

    题目内容:

    我们知道如何按照三种深度优先次序来周游一棵二叉树,来得到中根序列、前根序列和后根序列。反过来,如果给定二叉树的中根序列和后根序列,或者给定中根序列和前根序列,可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列,要求在内存中重建二叉树,最后输出这棵二叉树的前根序列。

    用不同的整数来唯一标识二叉树的每一个结点,下面的二叉树

     

    中根序列是9 5 32 67

    后根序列9 32 67 5

    前根序列5 9 67 32

     

     

     

    输入格式:

    两行。第一行是二叉树的中根序列,第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0~65535。暂不必考虑不合理的输入数据。

     

    输出格式:

    一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。

     

    输入样例:

    9 5 32 67
    9 32 67 5

     

    输出样例:

    5 9 67 32

     

    时间限制:500ms内存限制:32000kb
     1 #include <iostream>
     2 #include <string.h>
     3 #include <algorithm>
     4 #include <stack>
     5 #include <string>
     6 #include <math.h>
     7 #include <queue>
     8 #include <stdio.h>
     9 #include <string.h>
    10 #include <vector>
    11 #include <fstream>
    12 #include <set>
    13 
    14 using namespace std;
    15 int mid[65536], back[65536];
    16 int count0 = 0;//计结点个数数
    17 bool flag;//是否是第一次输出
    18 
    19 void init() {
    20     int i = 0;
    21     scanf("%d", &mid[++i]);
    22     while (getchar() != '\n')//当读入一个换行符就说明一行读完
    23         scanf("%d", &mid[++i]);
    24     count0 = i;
    25     for (int i = 1; i <= count0; i++)
    26         scanf("%d", &back[i]);
    27 }
    28 
    29 void front(int mids, int mide, int backs, int backe) {
    30     if (mids > mide )return;
    31     if (flag) {
    32         printf("%d", back[backe]);
    33         flag = false;
    34     }
    35     else
    36         printf(" %d", back[backe]);
    37     int spot = find(mid+mids,mid+mide+1, back[backe])-mid;
    38     int lft = spot - mids;
    39     front(mids, spot - 1, backs, backs + lft - 1);//递归输出左子树的根节点
    40     front(spot + 1, mide, backs + lft, backe-1);//递归输出右子树的根节点
    41 }
    42 
    43 int main()
    44 {
    45     flag = true;
    46     init();
    47     front(1, count0, 1, count0);
    48     return 0;
    49 }
    View Code

    今天做题太玄学了

    这题一开始想着这个OJ的数据按以往经验非常水所以直接递归吧

    居然TLE

    然后换栈

    依然TLE??

    最后发现好像是输入里有问题,但我至今还没明白为啥,就是将本来后序数组也用getchar判断输入的,改成了数元素个数输入,然后就过了

    难道是题目数据里面最后没有换行符???

    今天貌似只要做题就不顺,不如回家打游戏吧

    转载于:https://www.cnblogs.com/yalphait/p/9898335.html

    展开全文
  • 无论是按照什么顺序去遍历二叉树,要学会分解,而不是直接想要把整个二叉树的遍历序列写出来,首先,我们可以将这棵二叉树分解这样的三棵小树,后文提到这几棵小树以1树、2树、3树命名 接下来,我们写一下这...
  • 二叉树的后序序列为EDBFGCA,中序序列为DEBAFCG,通过这两个序列可以得出: A是结点,DEB是A结点的左子树,FCG是A结点的右子树。 如下图: step2:看A结点的左子树DEB 该左子树DEB的后序序列为:EDB,中序...
  • 一棵二叉树的先序遍历序列为EFHIGJK,中序遍历序列为HFIEJKG,则该二叉树根结点的右孩子为 A. H B. E C. F D. G
  • * 序列二叉树(先序例) * 1、假设序列结果字符串str,初始化str""; * 2、先序遍历二叉树,如果遇到空节点,在str后面加上“#!” * “#”不是节点空,“!”表示一个节点值的结束。不加结 ...
  • 我一开始做这些题目的时候也都是得试个几遍,但是后来随着做题数量的慢慢增加,我发现之前的“试几遍”其实是没有参悟二叉树递归的本质,以及各种遍历序列的特点,那么下面我和大家来看看先序遍历序列+中序遍历序列...
  • 我们知道,对称线索二叉树的意义在于,中序... 要找到先根序列中的后继结点,可以直接根周游已经构造好的对称序二叉树,得到这颗二叉树先根序列,再搜索后继结点即可。那么,如何根周游对称序二叉树? ...
  • 2. 下面代码中需要注意一点,在createTree()函数中使用指针作为函数返回值,并且这个指针又是在函数内定义,这样是有风险的,因为函数结束时这个指针内存就被释放了(这里程序能AC通过只是碰巧而已)
  • 后续遍历=左子树,右子树,,中序遍历=左子树,,右子树已知二叉树后序遍历序列是DBCEFGHA,中序遍历序列EDCBAHFG,它的前序遍历的序列是?由后序遍历序列是DBCEFGHA,可以看出整棵树的节点是A,再看中序遍历序列...
  • 当一棵二叉树前序序列和中序序列分别为HGEDBFCA和EGBDHFAC时,其后序序列为什么?当一棵二叉树前序序列和中序序列分别为HGEDBFCA和EGBDHFAC时,其后序序列为什么?虽然我已知道答案为EBDGACFH,请求详细算法,c语言...
  • 二叉树序列构造

    2020-05-01 10:34:59
    1、从前序与中序遍历序列构造二叉树leetcode105 先序遍历的顺序是 root -> left -> right,中序:left -> root -> right,这就能方便的从开始构造一棵树。 首先,preorder 中的第一个元素一定是树...
  • 验证二叉树的前序序列序列二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如#。 例如,上面的二叉树可以...
  • 已知二叉树后序遍历序列是DBCEFGHA,中序遍历序列EDCBAHFG,它的前序遍历的序列是?画出二叉树. 后续遍历的顺序是左右,中序遍历的顺序是左右 这点应该懂吧 由后续访问序列可以看出最后一个被访问的必定是这个...
  • 根据前序序列可知,a肯定是节点。再在中序序列中找到a,发现a左侧是dgb,右侧是echf,则dgb应该是a的左孩子,echf是a的右孩子。 接着只要递归的判断左右孩子的后序序列就可以了。比如dgb是左孩子的中序序列,则...
  • 通过递归的方法根据前序序列构建二叉树、根据后序序列构建二叉树、根据前序+中序序列构建二叉树、根据中序+后序序列构建二叉树。 一、二叉树结点定义以及一些基本函数定义 ①二叉树结点: // 二叉树结点结构体 ...
  • 331、验证二叉树的前序序列序列二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。 例如,上面的二叉树可以...
  • 1.重建二叉树 输入某二叉树的前序遍历和中序遍历的结果,请...中序遍历中,节点会被放在中间遍历,节点左边左子树,右边右子树。 如上,从这张图,我们能够获知,给点两个数组(前序,中序), 节点的存在
  • 下面两行先后给出先序和中序遍历序列,均是长度N的不包含重复英文字母(区别大小写)的字符串。 9 ABDFGHIEC FDHGIBEAC 输出样例: 5 解题思路: 已知先序序列和中序序列确定树的结构: 建立一个树根节点,...
  • 给定二叉树的2个遍历序列(如先根+中先根+后,中+后等),是否能够根据这2个遍历序列唯一确定二叉树? 2结论 这三种组合并不是都能唯一确定二叉树的,其中先根+后就不能唯一确定一棵二叉树,中+先根...
  • 这里讲两种序列化方式,一种是以先序排列方式进行序列化和反序列化,另一种是以水平方式进行序列化和反序列化。这里每个元素以"!"来隔开。 先序排列方式: 每个叶子结点的左右孩子以"#"的...
  • 二叉树序列

    2016-06-24 15:46:58
    首先我们介绍二叉树先序序列化的方式,假设序列化的结果字符串str,初始时str等于空字符串。先序遍历二叉树,如果遇到空节点,就在str的末尾加上“#!...给定树的结点root,请返回二叉树序列化后的字
  • LeetCode 二叉树序列化与反序列

    千次阅读 2019-03-07 20:15:16
    序列化是将一个数据结构或者对象转换连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。 请设计一个算法来实现...
  • 使用深度优先搜索的思路,解决《297. 二叉树序列化与反序列化》问题
  • //退出循环时ia[l1]在中序序列的下标 llen = i - l2 , rlen = r2 - i ; BiTree t = ( BiTree ) malloc ( sizeof ( BiTNode ) ) ; t -> data = a [ l1 ] ; t -> lchild = creat2 ( a , b , l1 + 1 , ...

空空如也

空空如也

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

下面二叉树的先根序列为