数据结构——二叉树操作

Description

根据给定的字符串生成二叉树并前序、中序、后序此二叉树。

Input

给定一字符串，其中#表示空。

例：上图输入为

HDB#A##C##G#FE###

Output

分别输出此二叉树前序、中序和后序。

Sample Input

HDB#A##C##G#FE###

Sample Output

HDBACGFE
BADCHGEF
ABCDEFGH

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<iostream>
 5 using namespace std;
 6 typedef struct BiTNode //定义结构体
 7 {
 8     char data; //数据
 9     struct BiTNode *lchild,*rchild; //左右子树域
10 } BiTNode,*BiTree;
11 
12 int CreateBiTree(BiTree &T)//建树
13 {
14     char data;
15     scanf("%c",&data);
16     if(data=='#') //遇到 # 的时候，就代表没有左孩子或者右孩子了
17     {
18         T=NULL;
19     }
20     else
21     {
22         T=(BiTree)malloc(sizeof(BiTNode));//开配空间
23         T->data=data;//存入数据
24         CreateBiTree(T->lchild);//去遍历左孩子
25         CreateBiTree(T->rchild);//去遍历右孩子
26     }
27     return 0;
28 }
29 void Visit(BiTree T)
30 {
31     if(T->data!='#')
32         printf("%c",T->data);
33 }
34 void Preorder(BiTree T)//前序遍历 根左右
35 {
36     if(T!=NULL)
37     {
38         Visit(T);
39         Preorder(T->lchild);
40         Preorder(T->rchild);
41     }
42 }
43 void Inorder(BiTree T)//中序遍历 左根右
44 {
45     if(T!=NULL)
46     {
47         Inorder(T->lchild);
48         Visit(T);
49         Inorder(T->rchild);
50     }
51 }
52 void Postorder(BiTree T)//后序遍历 左右根
53 {
54     if(T!=NULL)
55     {
56         Postorder(T->lchild);
57         Postorder(T->rchild);
58         Visit(T);
59     }
60 }
61 int main()
62 {
63     BiTree T;
64     CreateBiTree(T);//建树
65     Preorder(T);//前序
66     printf("
");
67     Inorder(T);//中序
68     printf("
");
69     Postorder(T);//后序
70     printf("
");
71     return 0;
72 }

中序遍历二叉树

Description

给定一颗二叉树，要求输出二叉树的深度以及中序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。

Input

输入数据分为多组，第一行是测试数据的组数n，下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数，数据为0代表当前结点为空，数据为-1代表二叉树数据输入结束，-1不作处理。二叉树的构造按照层次顺序（即第1层1个整数，第2层2个，第3层4个，第4层有8个......，如果某个结点不存在以0代替）

Output

输出每棵二叉树的深度以及中序遍历二叉树得到的序列。

Sample Input

2
1 -1
1 2 0 3 4 -1

Sample Output

1 1
3 3 2 4 1

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<iostream>
 5 using namespace std;
 6 typedef struct BiTNode //定义结构体
 7 {
 8     int data; //数据
 9     struct BiTNode *lchild,*rchild; //左右子树域
10 } BiTNode,*BiTree;
11 int q[2013];
12 int CreateBiTree(BiTree &T,int p)//建树
13 {
14     if(q[p]==0) //遇到 # 的时候，就代表没有左孩子或者右孩子了
15     {
16         T=NULL;
17     }
18     else
19     {
20         T=(BiTree)malloc(sizeof(BiTNode));//开配空间
21         T->data=q[p];//存入数据
22         CreateBiTree(T->lchild,2*p);//去遍历左孩子
23         CreateBiTree(T->rchild,2*p+1);//去遍历右孩子
24     }
25     return 0;
26 }
27 void Inorder(BiTree T)//中序遍历 左根右
28 {
29     if(T==NULL)
30     {
31         return ;
32     }
33     Inorder(T->lchild);
34     printf(" %d",T->data);
35     Inorder(T->rchild);
36 }
37 
38 int TreeDeep(BiTree T)
39 {
40     int deep = 0;
41     if(T)
42     {
43         int leftdeep = TreeDeep(T->lchild);
44         int rightdeep = TreeDeep(T->rchild);
45         deep = leftdeep>=rightdeep?leftdeep+1:rightdeep+1;
46     }
47     return deep;
48 }
49 
50 int main()
51 {
52     int t,i,n,deep;
53     BiTree T;
54     scanf("%d",&t);
55     while(t--)
56     {
57         i=1;
58         while(1)
59         {
60             scanf("%d",&n);
61             if(n==-1)
62             {
63                 break;
64             }
65             else
66             {
67                 q[i++]=n;
68             }
69         }
70         i--;
71         CreateBiTree(T,1);//建树
72         deep=TreeDeep(T);
73         printf("%d",deep);
74         Inorder(T);//中序
75         printf("
");
76     }
77     return 0;
78 }