要点层次关系

1.树的定义:

2.树的基本术语:度(子树的个数，而不是离散数学中的度) 祖先层数(规定根节点的层数为1), 宽度

一.存储结构

1.双亲表示法顺序表 (有点像并查集的存储方式)

2.孩子表示法链表 n个节点有n个孩子链表 n个头指针又构成一个线性表

3.孩子兄弟表示法(又称二叉链表表示法)

1.基本性质:(注意区别度的含义)

① $\text{[math]}$ (设 $n,n_0,n_1,n_2$ ，讨论树的分枝数(n-1)和每个 $n_i$ 的贡献)

② $第i层最多有2^{i-1}个节点$

③ $\text{[math]}$

④ $n个点的完全二叉树的深度为\lfloor log_2n\rfloor+1$

2.前,中序，后中序可确定一个二叉树，但前后序无法确定一个二叉树

3.二叉树的存储结构

①顺序存储结构:适合存储完全二叉树，当空树比较多的时候，相当浪费空间

②二叉链表(左右孩子) ③三叉链表(多了一个parent指针域)

4.遍历森林的方法

①树->二叉树: ①加线 ②去线 ③层次调整

②森林->二叉树: ① ② ③

③二叉树->树/森林: ①

左右儿子指针为空的时候，tag = 1 ，左孩子会指向前驱，右孩子会指向后继元素（前驱后继的含义要看你是进行什么遍历）

1. 00 100 101 110 111 这一组无法形成哈夫曼树，因为哈夫曼树的度只有0或者2.

2. 完全二叉树有100个节点，那么它有多少个叶子节点

答:50.

解：叶子节点出现在最后两层(不是只在最后一层)，所以分别算一下就好了

更好的思路：给这100个数编号,考虑最后一个节点，那他的双亲的编号应该为[100/2]=50,那编号为50的点之后应该就不会有字节点了，自然就是100 - 50 = 50 个.

3.已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度为 2 的结点，4 个度为 3 的结点。则该树中有（）个叶子结点。

答案:12 设X，节点数为X + 9 ,分枝数为X + 8 ,然后列各度贡献解方程即可.

4.在有 n 个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。

哈夫曼树只含度为0或2的节点，根据二叉树的性质1可知 n0 = n2 + 1

5.二叉树是度为 2 的树。错: 还有0,1呢

6.线索二叉树中某结点 R 没有左孩子的充要条件是? R.ltag = 1;