树的定义
由唯一的根和若干互不相交的子树，每一颗子树又是一棵树。
相关概念
- 结点的度：拥有子树的个数
- 树的度：树中各节点度的最大值
- 双亲节点：
- 祖先节点：他上边所有的节点都是祖先节点
- 森林：把树的根去掉，剩下的树就构成了森林
树的存储结构
树的存储有两种方式：顺序存储、链式存储
顺序存储：一般使用称双亲存储，一组数组就可以搞定
如知道了节点 i，那么 tree[i] 就是 i 的双亲节点
链式存储包括
孩子存储结构.
| 左孩子指针 | 数据 | 右孩子指针 |
|---|---|---|
| lchild | data | rchilid |
数据结构如下：
type BTNode struct {
data int
lchild *BTNode
rchilid *BTNode
}
孩子兄弟存储结构。
二叉树
在普通树上再加两个条件，就构成了完全二叉树。
- 每个节点最多有两个子树
- 子树有左右之分，不能颠倒
二叉树又分为满二叉树，完全二叉树，完全二叉树是由满二叉树由右到左，从下到上排着删得到的。不能跳着删除
二叉树主要性质
- 非空二叉树的叶子结点数，等于双分支结点数+1；
- 在二叉树的第 i 层上，最多有 2i-1个结点。
- 对于
k层深的树，最多有 2k -1 个节点
对于完全二叉树的第 i 结点来说：
-
i 的双亲节点为 【i/2】向下取整
-
如果
n>=2i那么i的左孩子的编号为2i，如果n<2i则无左结点 -
如果
n>=2i+1,则右节点为2i+1，如果n<2i+1则无右节点
二叉树的遍历
- 先序遍历
type treeNode struct {
data int
lchild *treeNode
rchild *treeNode
}
// 先序遍历
func preorder(treenode *treeNode) {
if treenode != nil {
Visit(treenode)
preorder(treenode.lchild)
preorder(treenode.rchild)
}
}
- 总序遍历
- 后序遍历
- 层次遍历
二叉树的层次遍历
func Level(node *BTNode) {
que := make([]*BTNode, 20) //20长的循环队列
front, rear := 0, 0 //初始化队列，当front=rear表示队为空
//rear+1=front 表示队列已经满了。
if node != nil {
rear = (rear + 1) % 20 // 根节点入队
que[rear] = node
for front != rear { // 如果不是空队
front = (front + 1) % 20
q := que[front] // 跟节点出队
Visit(q)
if q.lchilid != nil { // 如果有左节点就是入队
rear = (rear + 1) % 20
que[rear] = q.lchilid
}
if q.rchilid != nil { // 如果有右节点就入队
rear = (rear + 1) % 20
que[rear] = q
}
}
}
}
常见问题
如何求一颗二叉树的深度
二叉树的深度，就是左右子树中，深度最大的，然后再加一； 所以步骤是，先求左子树，再求右子树，最后求 max{左，右}+1
森林还有树
森林还有树之间的转换，孩子兄弟链表的存储方式，具体还是看书吧。
赫夫曼树 （最小代价树）
赫夫曼树又叫最优二叉树，它的特点是带权路径最短。
赫夫曼树的构造过程
- 先从所有的节点中，找出两个权值最小的节点
- 将这两个节点构成一个新的树，然后，然后根节点权值就是左右之和
- 把这个节点放到之前的节点中去
- 以此类推着写
赫夫曼树的特点：
- 权值越大，和根节点的距离越近
- 树中没有度为 1 的节点，这类树叫做严格二叉树
- 树的带权路径长度最短