二叉树的链式存储结构_二叉树的链式存储结构表示

7.1 二叉树的链式存储结构

7.1.2 二叉树简介

1. 介绍

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

如下图，就是一个二叉树：

2. 二叉树中常用的专业术语

①结点：包含一个数据元素及若干指向子树分支的信息。

②结点的度：一个结点拥有子树的数目称为节点的度。

③叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。

④分支节点：也称为非终端结点，度不为零的结点称为非终端结点。

⑤树的度：树中所有结点的度的最大值。

⑥结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子结点位于第L+1层。

⑦树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。

⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。

⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。

⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成。

-------选自百度百科

注意区分树的深度和度。

3. 特点

二叉树特点：

• 每个结点最多有两颗子树。
• 左子树和右子树有顺序。
• 即使某一个结点只有一颗子树，也要分左右子树

二叉树五种基本形态：

• 空二叉树
• 只有一个根结点
• 根结点只有左子树
• 根结点只有右子树
• 根节点既有左子树，又有右子树

4. 特殊二叉树

(1) 斜树

• 左斜树:所有结点只有左子树
• 右斜树:所有结点只有右子树

(2) 满二叉树

在二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层，这样的二叉树称为满二叉树。

如下图：

(3) 完全二叉树

定义：一棵深度为k的有n个结点的二叉树 ，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

简单理解你可以给树结点从上到下，从左到右编号这些编号是连续的，如下图：

这就是一颗完全二叉树。

不完全的二叉树如下图：

序号为5的结点处不存在，但是之后有结点，序号不连续。

5. 二叉树性质

性质1：二叉树的第i层上至多有2^i-1（i≥1）个结点。

性质2：深度为h的二叉树中至多含有2h-1个结点。

性质3：若在任意一棵二叉树中，有n₀个叶子结点，有n₂个度为2的节点，则必有n₀=n₂+1。

性质4：具有n个节点的满二叉树深为log₂(n+1)。

性质5：若对一棵有n个结点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

​ 当i=1时，该结点为根，它无双亲结点。
​
​ 当i>1时，该结点的双亲结点的编号为i/2。
​
​ 若2i≤n，则有编号为2i的左结点，否则没有左结点。
​
​ 若2i+1≤n，则有编号为2i+1的右结点，否则没有右结点。

7.1.3 二叉树链式存储结构定义

二叉树每个结点包含两个孩子，所以为一个结点设计两个指针域和一个数据域，两个指针域分别指向两个孩子结点。

代码如下：

//树结点结构
typedef struct BiTNode{
    TElemType data;     //定义数据
    struct BiTNode *lchild,*rchild;     //左右子树
}BiTNode,*BiTree;
1
2
3
4
5

7.1.4 二叉树链式结构上的主要操作

这里只展示出几种主要操作，一些附带的次要操作，会在完整代码中给出。

7.1.5 构造和销毁二叉树

1. 构造二叉树

代码如下：

/*用于构造二叉树*/
int treeIndex=1;
typedef char String[24];    //0号单元存放长度
String str;

//构造树,按照前序遍历，#表示空树
void CreateBiTree(BiTree *T){
    TElemType ch;

    ch=str[treeIndex++];

    if(ch=='#'){
        *T=NULL;
    }else{
        *T=(BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data=ch;      //生成根结点
        CreateBiTree(&(*T)->lchild);    //构造左子树
        CreateBiTree(&(*T)->rchild);    //构造右子树
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

在这段代码中，使用了一个变量treeIndex来记录当前读取到的字符串中的位置，从而实现对字符串的逐个读取。同时，也定义了一个类型别名String，表示字符串类型，其中0号单元存放长度。

在函数CreateBiTree中，首先读取当前位置的字符ch，如果为’#'，则表示当前子树为空，直接将指针T指向空值NULL；否则，为当前结点分配内存空间，并将字符ch存储在结点的data中。接着，递归调用CreateBiTree函数，将左子树和右子树构造出来，并分别赋值给当前节点的左右子结点指针lchild和rchild。

需要注意的是，在这段代码中，使用了一个二级指针BiTree *T来表示当前结点指针的地址，而不是直接使用指针BiTree T。这是因为在递归过程中，需要对结点指针进行修改，而直接传递指针本身无法修改指针指向的地址，因此需要传递指针的地址，以便修改结点指针的值。

2. 销毁二叉树

代码如下：

//销毁二叉树
void DestroyBiTree(BiTree *T){
    if(*T){
        if((*T)->lchild)    //有左孩子
            DestroyBiTree(&(*T)->lchild);   //销毁左孩子的子树
        if((*T)->rchild)    //有右孩子
            DestroyBiTree(&(*T)->rchild);   //销毁右孩子子树
        free(*T);       //释放根结点
        *T=NULL;
    }
}
1
2
3
4
5
6
7
8
9
10
11

7.1.6 二叉树遍历的几种方式

这部分光靠文字说明是很难理解的，将采用图解的形式进行解释。遍历这部分总体采用的是递归的思路，如果对递归不太熟悉，建议先去查看递归函数的有关内容，这边不会对递归函数进行介绍。

1. 前序遍历

前序遍历从根结点开始，先遍历左子树，再遍历右子树。

图解：

代码如下：

//前序遍历
void PreOrderTraverse(BiTree T){
    if(T==NULL)
        return;
    printf("%c",T->data);
    PreOrderTraverse(T->lchild);    //先序遍历左子树
    PreOrderTraverse(T->rchild);    //最后先序遍历右子树
}
1
2
3
4
5
6
7
8

2. 中序遍历

中序遍历和前序遍历只是代码顺序上的区别，变成了先遍历左子树，然后打印结点，最后遍历右子树。

图解：

代码如下：

//中序遍历
void InOrderTraverse(BiTree T){
    if(T==NULL)
        return;
    InOrderTraverse(T->lchild);
    printf("%c",T->data);
    InOrderTraverse(T->rchild);
}
1
2
3
4
5
6
7
8

3. 后序遍历

后序遍历则是先遍历左子树，再遍历右子树，最后打印结点。

图解：

代码如下：

//后序遍历
void PostOrderTraverse(BiTree T){
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c",T->data);
}
1
2
3
4
5
6
7
8

7.1.7 返回树深度

设置两个计数器i，j，一个记录左边子树最大层，另一个记录右边，最终返回最大的那个值，就是树的深度。

代码如下：

//返回树的深度
int BiTreeDepth(BiTree T){
    int i,j;
    if(!T)
        return 0;
    if(T->lchild)
        i=BiTreeDepth(T->lchild);
    else
        i=0;
    if(T->rchild)
        j=BiTreeDepth(T->rchild);
    else
        j=0;
    
    return i>j?i+1:j+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

7.1.8 测试代码和完整代码

测试代码

int main(){
	int i;
	BiTree T;
	TElemType e1;
	InitBiTree(&T);

	
	StrAssign(str,"ABDH###E##CFI###G#j##"); 

	CreateBiTree(&T);

	printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
	e1=Root(T);
	printf("二叉树的根为: %c\n",e1);

	printf("\n前序遍历二叉树:");
	PreOrderTraverse(T);
	printf("\n中序遍历二叉树:");
	InOrderTraverse(T);
	printf("\n后序遍历二叉树:");
	PostOrderTraverse(T);
	ClearBiTree(&T);
	printf("\n清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
	i=Root(T);
	if(!i)
		printf("树空，无根\n");
	
	system("pause");
	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

运行结果

构造空二叉树后,树空否？0(1:是 0:否) 树的深度=4
二叉树的根为: A

前序遍历二叉树:ABDHECFIGj
中序遍历二叉树:HDBEAIFCGj
后序遍历二叉树:HDEBIFjGCA
清除二叉树后,树空否？1(1:是 0:否) 树的深度=0
请按任意键继续. . .
1
2
3
4
5
6
7
8

完整代码

下面附上完整代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100

typedef int Status;

/*用于构造二叉树*/
int treeIndex=1;
typedef char String[24];    //0号单元存放长度
String str;

Status StrAssign(String T,char *chars){ 
	int i;
	if(strlen(chars)>MAXSIZE)
		return ERROR;
	else
	{
		T[0]=strlen(chars);
		for(i=1;i<=T[0];i++)
			T[i]=*(chars+i-1);
		return OK;
	}
}

typedef char TElemType;
TElemType Nil=' '; /* 字符型以空格符为空 */

Status visit(TElemType e){
	printf("%c ",e);
	return OK;
}

//树结点结构
typedef struct BiTNode{
    TElemType data;     //定义数据
    struct BiTNode *lchild,*rchild;     //左右子树
}BiTNode,*BiTree;


//构造空二叉树T
Status InitBiTree(BiTree *T){
    *T=NULL;
    return OK;
}


//销毁二叉树
void DestroyBiTree(BiTree *T){
    if(*T){
        if((*T)->lchild)    //有左孩子
            DestroyBiTree(&(*T)->lchild);   //销毁左孩子的子树
        if((*T)->rchild)    //有右孩子
            DestroyBiTree(&(*T)->rchild);   //销毁右孩子子树
        free(*T);       //释放根结点
        *T=NULL;
    }
}

#define ClearBiTree DestroyBiTree

//构造树,按照前序遍历，#表示空树
void CreateBiTree(BiTree *T){
    TElemType ch;

    ch=str[treeIndex++];

    if(ch=='#'){
        *T=NULL;
    }else{
        *T=(BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data=ch;      //生成根结点
        CreateBiTree(&(*T)->lchild);    //构造左子树
        CreateBiTree(&(*T)->rchild);    //构造右子树
    }

}



//判断树是否为空
Status BiTreeEmpty(BiTree T){
    if(T)
        return FALSE;
    else
        return TRUE;
}

//返回树的深度
int BiTreeDepth(BiTree T){
    int i,j;
    if(!T)
        return 0;
    if(T->lchild)
        i=BiTreeDepth(T->lchild);
    else
        i=0;
    if(T->rchild)
        j=BiTreeDepth(T->rchild);
    else
        j=0;
    
    return i>j?i+1:j+1;
}

//返回T的根
TElemType Root(BiTree T){ 
	if(BiTreeEmpty(T))
		return Nil;
	else
		return T->data;
}

//返回p结点返回值
TElemType Value(BiTree p){
	return p->data;
}

//为结点赋值
void Assign(BiTree p,TElemType value){
	p->data=value;
}

//前序遍历
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 main(){
	int i;
	BiTree T;
	TElemType e1;
	InitBiTree(&T);

	
	StrAssign(str,"ABDH###E##CFI###G#j##"); 

	CreateBiTree(&T);

	printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
	e1=Root(T);
	printf("二叉树的根为: %c\n",e1);

	printf("\n前序遍历二叉树:");
	PreOrderTraverse(T);
	printf("\n中序遍历二叉树:");
	InOrderTraverse(T);
	printf("\n后序遍历二叉树:");
	PostOrderTraverse(T);
	ClearBiTree(&T);
	printf("\n清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
	i=Root(T);
	if(!i)
		printf("树空，无根\n");
	
	system("pause");
	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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

上述代码中有"ABDH###E##CFI###G#j##"，这个是用来构造二叉树用的，#代表空，那边不存在结点。

注意需要表示出每个结点的左右孩子结点，若没有就用#代替

7.1.9 二叉树的链式存储结构的优缺点

优点：

1. 相比于数组实现，链式结构的内存空间可以更加灵活地分配，避免了固定大小的限制；
2. 插入和删除结点的操作效率较高，因为只需要调整相应结点的指针即可；
3. 可以方便地遍历整棵二叉树，包括前序遍历、中序遍历、后序遍历。

缺点：

1. 相比于数组实现，链式结构的随机访问效率较低，因为要从根节点开始逐层遍历才能找到目标结点；
2. 由于每个结点需要额外存储两个指针，链式结构需要更多的内存空间；
3. 对于大规模的二叉树，链式结构可能会导致指针的层数过多，从而影响程序的运行效率。