【二叉数学习】—— 树的介绍

树

树的概念

• 树是由n个节点（n≥0）组成的有限集合，如果n = 0，则称位空树
• 树有且仅有一个特定的称位根的节点（root）
• 树又可以分为若干的子树（根据这个特性，可以使用递归实现）

树的度

表示树中某个节点的子节点的最大个数

树的节点关系

• 父亲节点
• 兄弟节点
• 孩子节点

树的深度/高度

表示从根节点到没有孩子节点的节点的举例

树的表示方法

从父子关系出发，引申出来父节点表示法

双亲表示法

下标	Data（节点保存的数据）	parent（父节点）
0	A	-1
1	B	0（父节点对应的下标）
2	C	0
3	D	1
4	E	2
5	F	3
6	G	3
7	H	3
8	I	3
9	J	4

• 根节点的父节点不存在，因此规定根节点的父节点为”-1“
• 如果要找某个节点的父节点，则时间复杂度为O（1）
• 如果要找某个节点的字节带你，则需要遍历整个表，才能找到

因为父节点表示法没有办法快速的找到某个子节点，所以引申出子节点表示法

子节点表示法

如果使用子节点表示法表示一棵树，那么会存在一个问题：每个节点的度不一样，那怎么统一表示呢？

这时我们会想到，有**”树的度“这个概念，只需要将每个节点的度规定为树的度**就可以解决这个问题

下标	child1	child2	child3	…	childn（这个n对应的是树的度）

但是子节点表示法会将每个节点的度都会规定为整个树的度，因此会造成不必要的空间浪费，这时候我们又会改进子节点表示法

改进后的 子节点表示法（这个不是专业术语）

在子节点表示发的基础上，我们在表示子节点的链表中加入子节点的度，根据子节点的度来分配他的空间，这样就会使得空间高效利用，不会造成资源浪费

下标	degree（度）	child1	child2	child3	…	childn（这个n对应的是每个节点的度）

改进后的子节点表示法确实高效利用空间，但是因为每个节点的度各不相同，所以无法用某种格式同一表示，这样会使我们遍历、查询等操作会比较困难的进行，所以我们想到了采用 子节点表示法混合结构

子节点表示法混合结构（经常使用的表示法）

先将子节点存入一个顺序结构里，然后将每个节点的子节点以单链表的形式连起来，如图所示

就好像是一个数组中的每个元素为一个链表

• 如果要找某个节点的子节点，则在表中找到对应位置，顺着链表找就OK了
• 如果要遍历整个树，则遍历这个顺序结构就好了

这个方法不足之处是在于如果要寻找某个节点的父节点，则需要遍历整个结构，但是我们可以在此基础上加入双亲表示法在顺序结构中加入每个节点的父节点下标

兄弟节点表示法

data（数据）	firstchild（第一个子节点）	rightsib（兄弟节点）

二叉树

二叉树的概念

二叉数（Binary Tree）是n（n ≥ 0）个节点的有限集合，该集合或为空集（此时为空二叉树），或为一个根节点和两个互不相交的、分别称位根节点的左子树和右子树的二叉树组成（可以使用递归）

• 每个节点的度最大为2，因此可以度的取值可以为：0、1、2

一些特殊的二叉树

满二叉树

• 顾名思义，把所有位置都放满了
• 每个非叶子节点的度都为2
• 所有的节点都有左子树和右子树，并且所有的叶子节点都在同一层上

当所有树的深度相同时，那么满二叉树一定时节点最多的一个

完全二叉树

• 可以类比满二叉树，当满二叉树最后一层的叶子节点不全时，并且这些叶子节点是按顺序排列，那么这个树就是完全二叉树
• 满二叉树一定是完全二叉树，完全二叉树不一定时满二叉树

二叉数的表示方法

完全二叉数可以使用数组表示，因为他的节点是可以有序排列

A	B	C	D	E	F	G	H	I	J
1	2	3	4	5	6	7	8	9	10

因此 有重要推论

推论：对于位置k的节点来说

他的左子节点位置 一定为 2*k + 1，

右子节点的位置 一定为 2*(k + 1)

一般来说，只有完全二叉数使用数组表示，其他二叉数都是使用链表

data	leftchild（左子节点）	rightchild（右子节点）