数据结构复习随机

树

二叉树

1. 二叉树每一层最多的节点数为

   2^n-1^

2. 满二叉树

   一颗树的层数为k那么他的总的节点是

   2^k-1^

3. 完全二叉树

   编号与满二叉树的编号相等

   先左后右

4. 任何一棵二叉树，度为2的节点数总是比叶子节点数少1

5. 分支节点是非叶子节点

6. 对于满二叉树来说
   满二叉树的一个重要性质是叶节点的数量（m）总是比分枝节点的数量（k）多1

7. 完全二叉树当中

   左节点是2i

   右节点是2i+1

8. 含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为 n+1

9. 将一颗树转化为二叉树，根结点没有右子树。

10. 二叉树有5种形态

哈夫曼树

1. 对于一棵有n个叶子节点的哈夫曼树，它的节点总数是2n-1。

2. 哈夫曼树的构建过程是基于权值的：权值较小的节点离根节点较远，权值较大的节点离根节点较近。

3. 从上往下

   左为0，右边为1

4. 将一棵树T转换为一颗二叉树T2，则T的先序遍历是T2的先序

5. 将一棵树T转换为一颗二叉树T2，则T的后序遍历是T2的中序