要点 层次关系
1.树的定义:
2.树的基本术语:度(子树的个数，而不是离散数学中的度) 祖先 层数(规定根节点的层数为1), 宽度
一.存储结构
1.双亲表示法 顺序表 (有点像并查集的存储方式)
2.孩子表示法 链表 n个节点有n个孩子链表 n个头指针又构成一个线性表
3.孩子兄弟表示法(又称二叉链表表示法)
二.二叉树
1.基本性质:(注意区别度的含义)
① (设
，讨论树的分枝数(n-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;
