树的定义

由唯一的根和若干互不相交的子树，每一颗子树又是一棵树。

相关概念

• 结点的度：拥有子树的个数
• 树的度：树中各节点度的最大值
• 双亲节点：
• 祖先节点：他上边所有的节点都是祖先节点
• 森林：把树的根去掉，剩下的树就构成了森林

树的存储结构

树的存储有两种方式：顺序存储、链式存储

顺序存储：一般使用称双亲存储，一组数组就可以搞定

如知道了节点 i，那么 tree[i] 就是 i 的双亲节点

链式存储包括

孩子存储结构.

数据结构如下：

type BTNode struct {
	data    int
	lchild  *BTNode
	rchilid *BTNode
}

孩子兄弟存储结构。

二叉树

在普通树上再加两个条件，就构成了完全二叉树。

• 每个节点最多有两个子树
• 子树有左右之分，不能颠倒

二叉树又分为满二叉树，完全二叉树，完全二叉树是由满二叉树由右到左，从下到上排着删得到的。不能跳着删除

二叉树主要性质

• 非空二叉树的叶子结点数，等于双分支结点数+1；
• 在二叉树的第 i 层上，最多有 2^i-1个结点。
• 对于 k 层深的树，最多有 2^k -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 的节点，这类树叫做严格二叉树
• 树的带权路径长度最短