给出中序&后序序列建树；给出先序&中序序列建树

2022-10-23 22:51:36

已知中序&后序建立二叉树：

SDUT 1489

Description

已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历

Input

输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的中序遍历序列，第二个字符串表示二叉树的后序遍历序列。

Output

输出二叉树的先序遍历序列

Sample Input

2

dbgeafc

dgebfca

lnixu

linux

Sample Output

abdegcf

xnliu

代码实现：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 #include <map>

 #include<string.h>

 #include<stack>

 #include<set>

 #include <queue>

 using namespace std;

 struct Tree

 {

     char a;

     Tree * l;

     Tree *r;

 };

 //已知中序与后序递归建树：：

 Tree * ipCreatTree(char *instar,char *inend ,char *poststar,char*postend)  //instar 中序首地址 inend 中序尾地址 poststar后序首地址 postend后序尾地址

 {

     Tree *root = (Tree*)malloc(sizeof(Tree));

     root->a = *postend;

     root->l = NULL;

     root->r = NULL;

     if(instar==inend&&poststar==postend) return root;

     char *inp = instar;

     while((*inp != root->a)&&(inend-inp>=)) ++inp;

     int leftLength = inp - instar;

     char *leftInorderEnd = instar+leftLength-;

     if(leftLength>)

         root->l = ipCreatTree(instar,leftInorderEnd,poststar,poststar+leftLength-);

     if(leftLength<inend-instar)

         root->r = ipCreatTree(leftInorderEnd+,inend,poststar+leftLength,postend-);

     return root;

 }

 void Preorder(Tree *r)

 {

     if(r == NULL)

         return;

     else

     {

         printf("%c",r->a);

         Preorder(r->l);

         Preorder(r->r);

     }

 }

 int main()

 {

     int t;

     char  inorder[];

     char postorder[];

     Tree  *root;

     scanf("%d",&t);

     getchar();

     while(t--)

     {

         scanf("%s%s",inorder,postorder);

         int inlen = strlen(inorder);

         int postlen = strlen(postorder);

         root=ipCreatTree(inorder,inorder+inlen-,postorder,postorder+postlen-);

         Preorder(root);

         printf("\n");

     }

     return ;

 }

已知先序&中序建立二叉树：

SDUT 3343

Description

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

Input

输入数据有多组，每组数据第一行输入 1 个正整数 N(1 <= N <= 50) 为树中结点总数，随后 2 行先后给出先序和中序遍历序列，均是长度为 N 的不包含重复英文字母 ( 区分大小写 ) 的字符串。

Output

输出一个整数，即该二叉树的高度。

Sample Input

9

ABDFGHIEC

FDHGIBEAC

Sample Output

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 #include <map>

 #include<string.h>

 #include<stack>

 #include<set>

 #include <queue>

 using namespace std;

 struct Tree

 {

     char a;

     Tree * l;

     Tree *r;

 };

 //已知先序与中序递归建树：：

 Tree * piCreatTree(char *instar,char *inend ,char *prestar,char*preend) //instar 中序首地址 inend 中序尾地址 poststar先序首地址 postend先序尾地址

 {

     Tree *root = (Tree*)malloc(sizeof(Tree));

     root->a = *prestar;

     root->l = NULL;

     root->r = NULL;

     if(instar==inend&&prestar==preend) return root;

     char *inp = instar;

     while((*inp != root->a)&&(inend-inp>=)) ++inp;

     int leftLength = inp - instar;

     char *leftInorderEnd = instar+leftLength-;

     if(leftLength>)

         root->l = piCreatTree(instar,leftInorderEnd,prestar+,prestar+leftLength);

     if(leftLength<inend-instar)

         root->r = piCreatTree(leftInorderEnd+,inend,prestar+leftLength+,preend);

     return root;

 }

 int Depth(Tree *r)

 {

     int hl,hr;

     if(r==NULL) return  ;

     hl = Depth(r->l);

     hr = Depth(r->r);

     if(hl>=hr) return hl+;

     else return hr+;

 }

 int main()

 {

     int t;

     char  preorder[];

     char   inorder[];

     Tree  *root;

     while(~scanf("%d",&t))

     {

         getchar();

         scanf("%s%s",preorder,inorder);

         int inlen = strlen(inorder);

         int prelen = strlen(preorder);

         root=piCreatTree(inorder,inorder+inlen-,preorder,preorder+prelen-);

         printf("%d\n",Depth(root));

     }

     return ;

 }

本文为个人随笔,如有不当之处,望各位大佬多多指教.
若能为各位博友提供小小帮助,不胜荣幸.

码农公寓

相关文章