数据结构---树

1 名词解释

• 度：节点的度就是其子节点数，树的度就是树中节点最大的度
• 深度：指树的层数，根节点是第一层

2 存储结构

• 双亲表示法：节点中存储数据位和父亲指针，找父母好找，但找儿子很难
• 孩子表示法：节点中存储数据位和孩子指针，孩子个数不定，该怎么办？
• • 第一种方案：设置树的度个位置，如果没有这么多孩子即留空[空间利用率低]
  • 第二种方案：第一个位置存孩子个数，即节点的度[维护成本，运算成本上升]
  • 第三种方案：顺序存储结构放入一个数组，但是数组每个元素不只是数据本身，而是数据本身以及一个链表，链表后续元素为所有子节点的下标。比较抽象以后将这种数组中每个元素是链表的结构起名为旗子。

3 二叉树

3.1 部分分类

• 斜树：只有左（右）子树
• 满二叉树：分支节点都有两个孩子，且所有叶子都在一层
• 完全二叉树：从左到右的填充的树，完全不一定满，满了一定完全了

3.2 性质

• 1 第i层有2^(i-1)个节点；深度为k的二叉树至多有2^k-1个节点；一共n个节点构成的二叉树深度为[log2n]+1（中括号为向下取整）
• 2 叶节点数 - 1 = 度为2的节点数
• 3 完全二叉树从左到右的依次编号，则任意节点的标号z，左孩子(若有)标号2z，右孩子标号2z+1

3.3 存储结构

• 1 一维数组存储：把所有的二叉树看做完全二叉树，按序存入数组，空缺的填空
• 2 链表存储(二叉链表)：常见的方式，左右孩子指针+数据

3.4 遍历二叉树

• 1 广度优先遍历：按照完全二叉树的从左到右从上到下的顺序遍历
• 2 深度优先遍历：前序 中序 后序
  • 如果已知前序和中序遍历的顺序，怎么推断二叉树的实际结构？
  • 需要知道前序是先打印再到左，一直左，直到不能再左了，此时再右，然后继续左...有种感觉就是重力是向↙的，能左就左。从前序结果能确定第一个节点一定是根节点。
  • 而中序则是先找到最左下的那个点,到最底层了才开始打印，从左下开始，^形遍历向上，直到根节点，然后到根节点右孩子的最左下，继续照着这个原则来，有种感觉就是先找到最左下的点再开始^,^后回到父节点的另一个孩子的最左下。有个重要的性质就是这个节点的左孩子们一定比这个节点先遍历到，而右孩子则之后遍历到。所以中序的结果能看出根节点的所有左孩子节点们，和右孩子节点们。

3.5 树 森林<-->二叉树

• 树->二叉树：树中节点的孩子们保留第一个，其他的作为该独苗的右孩子一直往右排；即第一个孩子成为左孩子(长子)，其他儿子作为长子的右孩子和右孩子的右孩子一直往下。长子挂左，兄弟挂右。
• 二叉树->树：这种二叉树一定是根节点只有左孩子。将每个节点与其左孩子的所有右侧孩子相连，然后去掉原来向右的所有线就行了，调整下位置。还是利用了长子挂左，兄弟挂右
• 森林->二叉树：每个树转成二叉树，此时的二叉树都是只有左孩子。将第二个转好的二叉树挂到第一个的根节点的右孩子，第三个挂第二个右...
• 二叉树->森林：根节点一直向右，拆下各个树，然后每个按照二叉树->树的方式转换即可。

3.6 赫夫曼树

每个元素有一定的比重，比如abcdef字母出现频率是5 15 40 30 10，则赫夫曼树生成方式为：拿出最小的5 10，组成一个^，左侧放5，右侧10，然后父亲给个代号x，x=5+10=15，将15替换5和10放入这个队列。继续刚才的操作，最后就形成了赫夫曼树。该树只有叶节点存数据，避免了前缀和别人前缀重复

3.6.1 赫夫曼编码

将左设为0，右设为1，每个节点从根节点数下来的编码，就是自己的赫夫曼编码。