1.二叉树的创建、先中后遍历、各个节点度的个数、深度
程序代码:
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 typedef char datatype;
5 typedef struct node
6 {
7 datatype data;
8 struct node *lchild;
9 struct node *rchild;
10 }*Btree;
11 //创建节点
12 Btree create_node()
13 {
14 Btree s=(Btree)malloc(sizeof(struct node));
15 if(NULL==s)
16 return NULL;
17 s->data='\0';
18 s->lchild=s->rchild=NULL;
19 return s;
20 }
21 //创建树
22 Btree create_tree()
23 {
24 datatype element;
25 printf("please enter element:");
26 scanf(" %c",&element);
27 if(element=='#')
28 return NULL;
29 //创建节点
30 Btree tree=create_node();
31 tree->data=element;
32 //递归创建节点左孩子
33 puts("左");
34 tree->lchild=create_tree();
35 //递归创建节点右孩子
36 puts("右");
37 tree->rchild=create_tree();
38 return tree;
39 }
40 //先序遍历
41 void output_first(Btree tree)
42 {
43 if(NULL==tree)
44 return;
45 printf("%c",tree->data);
46 output_first(tree->lchild);
47 output_first(tree->rchild);
48 }
49 //中序遍历
50 void output_mid(Btree tree)
51 {
52 if(NULL==tree)
53 return;
54 output_mid(tree->lchild);
55 printf("%c",tree->data);
56 output_mid(tree->rchild);
57 }
58 //后序遍历
59 void output_last(Btree tree)
60 {
61 if(NULL==tree)
62 return;
63 output_last(tree->lchild);
64 output_last(tree->rchild);
65 printf("%c",tree->data);
66 }
67 //计算二叉树节点个数
68 void Count(Btree tree,int *n0,int *n1,int *n2)
69 {
70 if(NULL==tree)
71 return;
72 if(tree->lchild==NULL&&tree->rchild==NULL)
73 ++*n0;
74 else if(tree->lchild!=NULL&&tree->rchild!=NULL)
75 ++*n2;
76 else
77 ++*n1;
78 Count(tree->lchild,n0,n1,n2);
79 Count(tree->rchild,n0,n1,n2);
80 }
81 //计算深度
82 int high(Btree tree)
83 {
84 if(NULL==tree)
85 return 0;
86 int left=1+high(tree->lchild);
87 int right=1+high(tree->rchild);
88 return left>right?left:right;
89 }
90 int main(int argc, const char *argv[])
91 {
92 //创建树
93 Btree tree=create_tree();
94 //先序遍历
95 output_first(tree);
96 puts("");
97 //中序遍历
98 output_mid(tree);
99 puts("");
100 //后序遍历
101 output_last(tree);
102 puts("");
103 //计算二叉树节点个数
104 int n0=0,n1=0,n2=0;
105 Count(tree,&n0,&n1,&n2);
106 printf("n0=%d n1=%d n2=%d n=%d\n",n0,n1,n2,n0+n1+n2);
107 //计算深度
108 int high_tree=high(tree);
109 printf("%d\n",high_tree);
110 return 0;
111 }
运行结果: