二叉树的简单应用_二叉树的实际生活应用及案例

数据结构 二叉树

问题描述

1. 查找自己家族的族谱，至少上溯至祖爷爷辈；

2. 族谱二叉树的建立（树的深度要>=4）；

3. 三种不同遍历算法遍历此二叉树；

4. 统计二叉树的深度，输出叶子结点的信息。

问题分析
本次作业是构建一个二叉树，储存本家族的族谱信息，实际就是二叉树的简单应用，包括构建二叉树，二叉树的遍历，求解二叉树的深度，打印叶子节点。整个程序不算复杂，但是调试起来有很多细节需要注意。话不多说，直接贴代码

#include<stdio.h>

#include<stdlib.h>

typedef struct BiTNode
//节点结构
{

	char data;//数据域

	struct BiTNode *lchild, *rchild;//左孩子 右孩子

}BiTNode, *BiTree;

void PreOrderTraverse(BiTree T)//二叉树的先序遍历

{

	if (T == NULL)

		return;

	printf("%c ", T->data);

	PreOrderTraverse(T->lchild);

	PreOrderTraverse(T->rchild);

}

void InOrderTraverse(BiTree T)//二叉树的中序遍历

{

	if (T == NULL)

		return;

	InOrderTraverse(T->lchild);

	printf("%c ", T->data);

	InOrderTraverse(T->rchild);

}

void PostOrderTraverse(BiTree T)//后序遍历

{

	if (T == NULL)

		return;

	PostOrderTraverse(T->lchild);

	PostOrderTraverse(T->rchild);

	printf("%c ", T->data);

}


int countDepth(BiTNode *T)//输出二叉树深度

{

	if (T == NULL)

		return 0;

	else if (T->lchild == NULL && T->rchild == NULL)

		return 1;

	else

	{

		int depth1 = countDepth(T->lchild) + 1;

		int depth2 = countDepth(T->rchild) + 1;

		return depth1 > depth2 ? depth1 : depth2;

	}

}


void Value(BiTree T)//打印叶子节点
{
	if (T != NULL)
	{
		if (T->lchild == NULL && T->rchild == NULL)
			printf("%c", T->data);
		Value(T->lchild);
		Value(T->rchild);
	}
}

void CreateBiTree(BiTree *T)//构建二叉树

{

	char ch;

	scanf_s("%c", &ch);

	if (ch == '#')

		*T = NULL;

	else

	{

		*T = (BiTree)malloc(sizeof(BiTNode));

		if (!*T)

			exit(-1);

		(*T)->data = ch;

		CreateBiTree(&(*T)->lchild);

		CreateBiTree(&(*T)->rchild);

	}

}

int main()

{

	BiTree T;
	printf("先序输入族谱(以##结束）:");
	CreateBiTree(&T);
	getchar();
	printf("先序输出族谱为：");
	PreOrderTraverse(T);
	getchar();
	printf("中序输出族谱为：");
	InOrderTraverse(T);
	getchar();
	printf("后序输出族谱为：");
	PostOrderTraverse(T);
	getchar();
	printf("叶子节点为：");
	Value(T);
	getchar();
	printf("这棵树的深度:%d\n", countDepth(T));
	getchar();
	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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

输出结果

我选择的二叉树是
先序遍历ABDGCEHIFJK
中序遍历DGBAHEICJFK
后序遍历GDBHIEJKFCA
叶子节点GHIJK
深度4
整个程序到这里就结束了，有几个容易出错的地方：
首先要对每一种遍历方式足够了解，才能在输入的时候输入正确的二叉树，然后程序输出时多次使用到getchar()函数，是防止程序运行时一闪而过，看不到输出