树结构

一棵树是由n(n > 0) 个元素组成的有限组合,其中

  1. 每一个元素被称为一个节点(node);

  2. 有一个特定的节点,被称为根节点树根(root);

  3. 除根节点外,其余节点能分成m (m >= 0) 个互相不相交的有限集合。其中每个子集又都是一棵树,这些子集被称为子树;

  4. 树是递归定义的;

  5. 一棵树至少有一个节点,这个节点就是根节点;

  6. 一个节点的子树个数,称为这个根节点的度,度为0的节点称为叶节点,树中各节点的度的最大值称为这棵树的度(一棵树的子树的数目);

  7. 一棵树中所有的节点的层次的最大值称为树的深度(树有几层);

二叉树

定义:

树的每个节点最多有两个子节点,每个节点的子节点分别称为左孩子、右孩子,它的两颗子树分别称为左子树和右子树。

特点

  1. 在二叉树的 第i层 上最多有 $2^{i-1}(i \geqslant 1)$ 个节点

  2. 深度为k的二叉树最多有 $2^{k-1}(k \geqslant 1)$ 个节点

  3. 满二叉树:除最后一层外,每一层上的所有节点都有两个子节点,在满二叉树中,每一层上的节点数都达到最大值;

  4. 完全二叉树:除最后一层外,每一层上的节点数都达到最大值,在最后一层只缺少右边的若干节点。

五种形态

  1. 空二叉树

  2. 仅有根节点的二叉树

  3. 右子树为空的二叉树

  4. 左右子树均非空的二叉树

  5. 左子树为空的二叉树

二叉树的遍历

一个简单的树

先序遍历

执行过程:

  1. 访问根节点;

  2. 遍历左子树

  3. 遍历右子树

如上图,先序遍历的遍历过程是:

1-2-4-7-5-3-6-8-9

根左右

中序遍历

执行过程:

  1. 遍历左子树

  2. 访问根节点

  3. 遍历右子树

如上图,中序遍历的遍历过程是:

7-4-2-5-1-3-8-6-9

左根右

后序遍历

执行过程:

  1. 遍历左子树

  2. 遍历右子树

  3. 访问根节点

如上图,中序遍历的遍历过程是:

7-4-5-2-8-9-6-3-1

左右根

二叉树的建立

特点

  1. 节点间关系蕴含在其储存位置中

  2. 仅适用于存满二叉树和完全二叉树

  3. 浪费空间

建立

创建结构体,储存树的各个节点。

1
2
3
4
5
struct node{
char value;
int lchild, rchild;
//lchild rchild 可以使用指针存储
}

两个例子

输入先序遍历序列建立二叉树,输出后序遍历结果

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
//输入先序遍历序列建立二叉树,输出后序遍历结果
//空节点用period间隔
#include <iostream>
#include <cstdio>
using namespace std;

struct node{
char value;
int lchild,rchild;
}data[101];



int root;//根节点
int cnt;//各节点序号
char ch;//输入字符
const char EMPTY = '.';

//建立二叉树
int buildTree(int bt){
ch = getchar();
if(ch == EMPTY){
bt = 0;
return bt;
}
else{
bt = ++cnt;
data[bt].value = ch;
data[bt].lchild = data[bt].rchild = 0;
data[bt].lchild = buildTree(bt);
data[bt].rchild = buildTree(bt);
}
return bt;
}

//后序遍历
void postorder(int bt){
if(bt){
postorder(data[bt].lchild);
postorder(data[bt].rchild);
cout<<data[bt].value;
}
}

int main(){
root = 0;
cnt = 0;
root = buildTree(0);
postorder(root);

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
//输入一串二叉树,用先序遍历的格式输出,空节点用*表示
#include <iostream>
#include <cstdio>
using namespace std;

struct node{
char parent;
int lchild,rchild;
}data[101];
//此处使用结构体数组下标作为各个节点的值


int root;//根节点
int cnt;//各节点序号
char ch;//输入字符
const char EMPTY = '*';

//后序遍历
void preorder(int root){
if(root!=0){
cout<<(char)(root-1+'a');
preorder(data[root].lchild);
preorder(data[root].rchild);
}
}

int main(){
int n;
cin>>n;
for(int i = 1;i<=n;i++){
char a,b,c;
cin>>a>>b>>c;
if(b!=EMPTY){
data[b-'a'+1].parent=a-'a'+ 1;
data[a-'a'+1].lchild=b-'a'+1;
}
if(c!=EMPTY){
data[c-'a'+1].parent=a-'a'+1;
data[a-'a'+1].rchild=c-'a'+1;
}
}

int root;

for(int i=1;i<=n;i++){
if((data[i].parent==0)&&(data[i].lchild||data[i].rchild)){
root=i;
break;
}
}

preorder(root);
cout<<endl;

return 0;
}

未完待续……

参考资料

二叉树的详细实现 (C++) - WindSun

C/C++ 二叉树 - Void_Caller