大话数据结构 树

发表于 更新于 阅读次数：
本文字数： 6.3k 阅读时长 ≈ 6 分钟

微信图片_20220310235141

《大话数据结构》 阅读整理

树

树的定义

n(n>=0)个结点的有限集

有且仅有一个特定的称为根的结点

当n > 1时 其余结点可分为m(m>0)个互不相交的有限集T1,T2,T3…Tm
其中每一个集合本身又是一棵树 并且称为根的子树

性质

n>0时根结点是唯一的 不可能存在多个根结点

m>0时 子树的个数没有限制 但一定是互不相交的

结点的分类

  • 结点的度

结点拥有的子树数

  • 叶结点/终端结点

度为0的结点

  • 分支结点/非终端结点/内部结点(除根结点外)

度不为0的结点

  • 树的度

树内各结点的度的最大值

结点的关系

  • 结点的孩子/孩子的双亲

结点的子树的根

  • 兄弟结点

同一双亲的孩子之间

  • 结点的祖先

从根到该结点所经分支上的所有结点

  • 结点的子孙

以某一结点为根的子树中的任一结点

  • 结点的层次

从根开始定义起 根为第一层 根的孩子为第二层

  • 堂兄弟

双亲在同一层的结点

  • 树的深度/高度

树中结点的最大层次

  • 有序树

将树中结点的各子树看成从左至右是有次序的 不能互换的

  • 无序树

将树中结点的各子树看成从左至右是有次序的 能互换的

  • 森林

m(m>=0)棵树互不相交的树的集合

对树中每个结点而言 子树的集合

线性结构与树结构的对比

线性结构

  • 第一个数据元素

无前驱

  • 最后一个数据元素

无后继

  • 中间元素

一个前驱一个后继

树结构

  • 根结点
    无双亲 唯一

  • 叶结点

无孩子 可以多个

  • 中间结点

一个双亲 多个孩子

数的存储结构

双亲表示法

每个结点中 附设一个指示器指示其双亲结点在数组中的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//树结构数据类型
typedef int TElemType;

//双亲表示法 
//结点结构
typedef struct PTNode {
	//结点数据
	TElemType data;
	//双亲位置
	int parent;
}PTNode;


//树结构
typedef struct {
	//结点数组
	PTNode nodes[MAX_TREE_SIZE];
	//根的位置和结点数
	int r, n;
}PTree;

孩子表示法

把每个孩子结点排列起来 以单链表做存储结构 则n个结点有n个孩子链表 如果是叶子结点则此链表为空 然后n个头指针又组成一个线性表 采用顺序存储结构 存放进一个一维数组

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
//孩子结点
typedef struct CTNode {

	//孩子结点数据
	int child;

	//指针域
	struct CTNode* next;

}*ChildPtr;

//表头结构
typedef struct {

	//表头数据域
	TElemType data;

	//孩子指针域
	ChildPtr firstchild;

}CTBox;

//树结构
typedef struct {

	//结点数组
	CTBox nodes[MAX_TREE_SIZE];

	//根的位置和结点数
	int r, n;

}CTree;
  • 多重链表表示法

每个结点有多个指针域 其中每个指针指向一课子树的根结点

孩子兄弟表示法

任意一棵树 他的结点的第一个孩子如果存在就是唯一的 他的右兄弟如果存在也是唯一的 因此设置两个指针 分别指向该结点的第一个孩子和此结点的右兄弟

1
2
3
4
5
6
7
8
9
//孩子兄弟表示法
typedef struct CSNode {

	//数据域
	TElemType data;

	//孩子结点指针域 和 兄弟结点指针域
	struct CSNode* firstchild, * rightsib;
}CSNode, *CSTree;

二叉树的定义

n(n>=0)个结点的有限集合 该集合或者为空集(称为空二叉树) 或者由一个根结点和两课互不相交的 分别称为根结点的左子树和右子树的二叉树组成

二叉树的特点

每个结点最多有两棵子树 所以二叉树中不存在度大于2的结点

左子树和右子树是有顺序的 次序不能任意颠倒

即使树中某结点只有一棵子树 也要区分它是左子树还是右子树

二叉树的五种基本形态

空二叉树

只有一个根结点

根结点只有左子树

根结点只有右子树

根结点即有左子树又有右子树

特殊的二叉树

斜树

  • 左斜树

所有结点都只有左子树的二叉树

  • 右斜树

所有结点都只有右子树的二叉树

满二叉树

有一棵二叉树 如果所有分支结点都存在左子树和右子树 并且所有叶子都在同一层上

  • 满二叉树的特点

叶子只能出现在最下一层

非叶子结点的度一定是2

在同样深度的二叉树中 满二叉树的结点个数最多 叶子树最多

完全二叉树

对一棵具有n个结点的二叉树按层序编号 如果编号为i(1 <= i <= n) 的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同

  • 二叉树的特点

叶子结点只能出现在最下两层

最下层的叶子一定集中在左部连续位置

倒数第二层 若有叶子结点 一定都在右部连续位置

如果节点度为1 则该结点只有左孩子 既不存在只有右子树的情况

同样结点数的二叉树 完全二叉树深度最小

二叉树的性质

  • 性质1

在二叉树的第i层至多有 2 ^ (i - 1)个结点(i >= 1)

  • 性质2

深度为k的二叉树至多有2^k - 1个结点(k >= 1)

  • 性质3

对任何一棵二叉树T 如果其终端结点数为N0 度为2的结点数为N2 则N0 = N2 + 1

  • 性质4

具有n个结点的完全二叉树的深度为(log2 n) + 1

  • 性质5

如果一棵树有n个结点的完全二叉树的结点按层序编号 对任一结点j(1 <= i <= n)

二叉树的存储结构

二叉树的顺序存储结构

就是将树的结点按照根结点层次的向下 然后层次按照从左至右依次存入到数组当中

二叉链表

每个结点最多有两个孩子 所以设计一个数据域和两个指针域

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef int TElemType;


//树的链式存储
typedef struct BiTNode {

	//结点数据
	TElemType data;

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

}BiTNode,*BiTree;

遍历二叉树

二叉树遍历原理

从根结点出发 按照某种次序依次访问二叉树中的所有结点 使得每个结点被访问一次且仅被访问一次

二叉树遍历方法

二叉树遍历

  • 前序遍历

若二叉树为空 则空操作返回 否则先访问根结点 然后前序遍历左子树 在前序遍历右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//前序遍历
void PreOrderTraverse(BiTree T) {

	//检验树是否为空
	if (NULL == T) {
		return;
	}

	//显示当前结点
	printf("%d", T->data);

	//递归 遍历左子树
	PreOrderTraverse(T->lchild);

	//递归 遍历右子树
	PreOrderTraverse(T->rchild);

}

A->B->D->G->H->C->E->I->F

  • 中序遍历

若二叉树为空 则空操作返回 否则从根结点开始(注意并不是先访问根结点)中序遍历根结点的左子树 然后是访问根结点 最后中序遍历右子树

G->D->H->B->A->E->I->C->F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//中序遍历
void InOrderTraverse(BiTree T) {

	//检验树是否为空
	if (NULL == T) {
		return;
	}

	//递归 遍历左子树
	InOrderTraverse(T->lchild);

	//显示结点数据
	printf("%d", T->data);

	//递归 遍历右子树
	InOrderTraverse(T->rchild);

}
  • 后序遍历

若二叉树为空 则空操作返回 否则从左到右先叶子后结点的方式遍历访问左右子树 最后是访问根结点

G->H->D->B->I->E->F->C->A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//后序遍历
void PostOrderTraverse(BiTree T) {

	//检验树是否为空
	if (NULL == T) {
		return;
	}

	//递归 遍历左子树
	PostOrderTraverse(T->lchild);

	//递归 遍历右子树
	PostOrderTraverse(T->rchild);

	//显示结点数据
	printf("%d", T->data);

}
  • 层次遍历
    若二叉树为空 则空操作返回 否则从树的第一层 也就是根结点开始访问 从上而下逐层遍历 在同一层中 按从左到右的顺序对结点逐个访问

A->B->C->D->E->F->G->H->I

推导遍历结果

根据前序遍历 中序遍历 后序遍历原则推导即可

已知前序遍历和后序遍历 是不能确定一棵二叉树的

二叉树的建立

先将二叉树的每个结点的空指针引入一个虚结点 其值为一个特定的值

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
char str[100];

int index = 0;

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

	//假设字符
	TElemType ch;

	//输入的数据
	scanf("%d", ch);

	//字符数组
	ch = str[index++];

	//假设输入为#时为空结点
	if (ch == '#') {
		*T = NULL;
	}
	else {

		//为结点开辟内存空间
		*T = (BiTree)malloc(sizeof(T));

		//终止程序
		if (!*T) {
			exit(OVERFLOW);
		}

		//将字符数据存入结点数据域
		(*T)->data = ch;

		//递归 创建左孩子
		CreateBiTree(&(*T)->lchild);

		//递归 创建右孩子
		CreateBiTree(&(*T)->rchild);

	}
}

线索二叉树

线索二叉树的原理

指向前驱和后继的指针称为线索

线索表

加上线索的二叉链表

线索二叉树

与之对应的数即是线索二叉树

线索化

对二叉树以某种次序遍历使其变为线索二叉树的过程

线索化的过程就是在遍历的过程中修改空指针的过程

给结点添加两个标识

  • ltag

为0时指向该结点的左孩子

为1时指向该结点的前驱

  • rtag

为0时指向该结点的右孩子

为1时指向该结点的后继

线索二叉树的实现

线索二叉树结构

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
# define OK 1
# define ERROR 0

typedef int Status;

//变量转换
typedef char TElemType;

//Link = 0 表示指向左右孩子指针 Thread = 1表示指向前驱或后继线索
typedef enum{Link,Thread} PointerTag;

//二叉线索存储结点结构
typedef struct BiThrNode {

	//数据域
	TElemType data;

	//结点数据 左右孩子指针
	struct BiThrNode* lchild, * rchild;

	//左标志
	PointerTag LTag;

	//右标志
	PointerTag RTag;

}BiThrNode,*BiThrTree;

从头结点开始遍历

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
//全局变量 始终指向刚刚访问过的结点
BiThrTree pre;

//中序遍历进行中序线索化 从头结点开始
void InThreading(BiThrTree p) {

	//p结点不为空
	if (p) {

		//递归遍历左子结点
		InThreading(p->lchild);

		//p的左下一结点不为空 就是 没有左孩子
		if (!p->lchild) {
			//将标识设置为 Thread
			p->LTag = Thread;

			//将p的左孩子指向前驱
			p->lchild = pre;
		}

		//p的右下一结点不为空 就是 没有右孩子
		if (!pre->rchild) {
			//将标识设置为Thread
			pre->RTag = Thread;

			//将p的右孩子指向后继
			pre->rchild = p;
		}

		//让全局变量pre 始终指向p
		pre = p;
		
		//递归遍历右孩子
		InThreading(p->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
//中序线索二叉树遍历 从最后结点开始
Status InOrderTraverse_Thr(BiThrTree T) {

	//定义结点p
	BiThrTree p;

	//将结点p指向头结点的左孩子
	p = T->lchild;

	//左孩子不是头结点即可
	while (p != T) {

		//左孩子的有前驱
		while(p->LTag == Link){
		
			//继续寻找下一个左孩子
			p = p->lchild;
		
			//显示结点
			printf("%c", p->data);

			//p有子孩子 并且 p的右孩子后继不是头结点 
			while (p->RTag == Thread && p->rchild != T) {

				//继续寻找下一个子孩子
				p = p->rchild;

				//显示数据
				printf("%c", p->data);

			}
			//将p指回头结点
			p = p->rchild;
		}
	}

	//返回正确状态码
	return OK;
}

树 森林 二叉树 的关系

树转换为二叉树

树转二叉树（1）

树转二叉树（2）

森林转换为二叉树

森林转二叉树（1）

森林转二叉树（2）

二叉树转换为树

二叉树转树（1）

二叉树转树（2）

二叉树转换为森林

二叉树转森林（1）

二叉树转森林（2）

树与森林的遍历

树的遍历

  • 后根遍历

先依次后根遍历每棵子树 然后在访问根结点

  • 先根遍历树

先访问树的根结点 然后依次先根遍历根的每棵子树

数的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现

森林的遍历

  • 前序遍历

先访问森林中第一棵树的根结点 然后再依次先根遍历每棵子树 在依次用同样方式遍历除去第一棵树的剩余树构成的森林

  • 后序遍历

先访问森林中第一棵树 后根遍历的方式遍历每棵子树 然后在访问根结点 再依次用同样方式遍历除去第一棵树的剩余树构成的森林

哈夫曼树

哈夫曼树的定义

  • 路径长度

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径 路径上的分支目

  • 树的路径长度

从树根到每一结点的路径长度之和

  • 哈夫曼树

带权路径长度WPL最小的二叉树

结点带权 * 结点的路径长度
哈夫曼树带权

  • 求哈夫曼树

简单点说： 权值最小的依次向大的权值拼接

  • 哈夫曼编码

设需要编码的字符集为{d1,d2,…dn} 各个字符在电文中出现的次数或频率集合为{w1,w2,…wn} 以d1,d2,…dn作为叶子结点 以w1,w2…wn作为相应叶子结点的权值来构造一棵哈夫曼树 规定哈夫曼树的左分支代表0 右分支代表1 则从根节点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应符的编码

你知道的越多 你不知道的越多 嘿 我是小博 带你一起看我目之所及的世界……

-------------本文结束 感谢您的阅读-------------

本文标题:大话数据结构 树

文章作者:小博

发布时间:2022年03月11日 - 00:38

最后更新:2022年03月21日 - 17:45

原始链接:https://codexiaobo.github.io/posts/1720144195/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。