二叉树的链式存储结构
MyCode:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
int CreateBiTree(BiTree &T){
ElemType ch;
ElemType t;
scanf("%d", &ch);
t = getchar();
if (ch == -1){ //输入-1表示叶子结点
T = NULL;
}
else{
T = (BiTree)malloc(sizeof(BiTNode));
if (!T ) exit(-1);
T->data = ch;
printf("输入%d的左子结点: ", ch);
CreateBiTree(T->lchild);
printf("输入%d的右子结点: ", ch);
CreateBiTree(T->rchild);
}
return 1;
}
//先序遍历二叉树
void TraverseBiTree(BiTree T){
if (T == NULL) return;
printf("%d ", T->data);
TraverseBiTree(T->lchild);
TraverseBiTree(T->rchild);
}
//中序遍历二叉树
void InOrderBiTree(BiTree T){
if (T == NULL) return ;
InOrderBiTree(T->lchild);
printf("%d ", T->data);
InOrderBiTree(T->rchild);
}
//后序遍历二叉树
void PostOrderBiTree(BiTree T){
if (T == NULL) return ;
PostOrderBiTree(T->lchild);
PostOrderBiTree(T->rchild);
printf("%d ", T->data);
}
//二叉树的深度
int TreeDepth(BiTree T){
int depth = 0;
if (T){
int leftdepth = TreeDepth(T->lchild);
int rightdepth = TreeDepth(T->rchild);
depth = leftdepth >= rightdepth ? leftdepth+1 : rightdepth+1;
}
return depth;
}
//求二叉树叶子结点个数
int LeafCount(BiTree T, int &num){
if (T){
if (T->lchild == NULL && T->rchild == NULL )
num++;
LeafCount(T->lchild, num);
LeafCount(T->rchild, num);
}
return num;
}
int main(){
BiTree T;
int depth, num = 0;
printf("请输入第一个结点的值，-1表示没有叶节点：\n");
CreateBiTree(T);
printf("先序遍历二叉树:\n");
TraverseBiTree(T);
printf("\n");
printf("中序遍历二叉树:\n");
InOrderBiTree(T);
printf("\n");
printf("后序遍历二叉树\n");
PostOrderBiTree(T);
printf("\n");
depth = TreeDepth(T);
printf("树的深度为：%d\n", depth);
LeafCount(T, num);
printf("树的叶子结点个数为：%d\n", num);
return 0;
}
运行结果:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25请输入第一个结点的值，-1表示没有叶节点：
1
输入1的左子结点: 2
输入2的左子结点: 3
输入3的左子结点: -1
输入3的右子结点: -1
输入2的右子结点: 4
输入4的左子结点: 5
输入5的左子结点: -1
输入5的右子结点: 7
输入7的左子结点: -1
输入7的右子结点: -1
输入4的右子结点: 6
输入6的左子结点: -1
输入6的右子结点: -1
输入1的右子结点: -1
先序遍历二叉树:
1 2 3 4 5 7 6
中序遍历二叉树:
3 2 5 7 4 6 1
后序遍历二叉树
3 7 5 6 4 2 1
树的深度为：5
树的叶子结点个数为：3
Hit any key to close this window...
