树结构

二叉树, 平衡二叉,树,森林

二叉树

二叉树最多只有二个孩子结点

1. 求每一层的结点数量,最多有 2^(k-1) 个结点,例第3层有 2^(3-1) = 4,第三层有4个结点
2. 求树所有的结点数量,最多有 2^k - 1 个结点.例树最高有3层,则 2^3 -1得7,即7个结点
3. 求叶子结点数,n0 = n2 + 1. n0代表度为0的,即是叶子结点.n2是度为2的结点.例3个2度结点,求有多少叶子结点. n0 = 3 + 1 得4个叶子结点
4. 具有n个结点的二叉链表中, 一共有2n个指针域.因为每一个结点都有二个指针域
5. 一个二叉链表中,只有n-1个孩子 ,为什么减1,因为根结点不是孩子.
6. n-1用于表示结点的左右孩子数, 其余n+1个指针域为空

二叉树的4种遍历方法

1. 先序遍历: 先根, 再左,后右
2. 中序遍历: 先左,再根, 后右
3. 后序遍历: 先右, 再右, 后根
4. 层次遍历: 从上到下,从左到右遍历

哈夫曼树

1. 哈夫曼树的结点的度数为0或2,没有度为1的结点
2. 包含n棵树的森林要经过n-1次合并才能形成哈夫曼树,共产生n-1个新结点
3. 包含n个叶子结点的哈夫曼树中有2n-1个结点,由n+n-1得来

哈夫曼编码

1. 左边标注为0, 右边标记为1
2. 权重小的排在最左边, 权重大的排在最右边
3. 哈夫曼是前缀码
4. 哈夫曼是最优前缀码

树

有多个孩子,不定的 see: https://www.bilibili.com/video/av35340449

树的3种遍历方法

1. 先根后子树遍历: 先访问根结点, 然后依次先根遍历各棵子树(子树是从左到右遍历)
2. 先子树后根遍历: 先依次后根遍历各棵子树, 然后访问根结点
3. 层次遍历: 从根到下, 从左到右遍历

满二叉树的性质

1. 树的所有结点数 = 2的树高次方 -1 即 2^k - 1. 例树高3, 求所有结点数 2^3 -1 = 7
2. n0 =（n+1）/2 (n0表示0度的叶子结点个数, n为总结点数)

完全二叉树的性质

1. 求树的高度. log2(N) + 1 (log以2为底,N为所有结点数).例 log2(7) + 1 = 2.x + 1 ~= 3

链表表示二叉树

二叉链表

1. 在n个结点的二叉链表中,有(n+1)个空指针域

三叉链表