tree.md

数据结构

树

1. 相关术语

1. 节点的度

   一个节点含有的子树的个数成为该节点的度

2. 叶节点

   度为0的节点

3. 双亲节点或父节点

   若一个节点含有子节点，则这个节点称为其子节点的父节点

4. 树的度

   一棵树中，最大的节点的度称为树的度

5. 节点的层次

   从根开始定义起，根为1层，根的子节点为2层，以此类推

6. 树的高度（深度）

   树中节点的最大层次

7. 森林

   由m（m>=0）棵互不相交的树的集合称为森林

2. 一些计算问题

1. 度的计算

   树的节点数 = 总的度数 + 1

   例如：设树T的度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1，则T中的叶子数为？

    1. 树的总节点数 = 1*4 + 2*2 + 3*1 + 4*1 + 1 = 16
    2. 树中的父节点数 = 4 + 2 + 1 + 1 = 8
    3. 叶子节点数 = 16 - 8 = 8
   

3. 树的遍历

1. 先序遍历

2. 中序遍历

3. 后序遍历

4. 二叉树的性质

5. 特殊的树

1. 哈夫曼树

   节点的度只有两种，一种是度为0的叶子节点，一种是度为2的内部节点。

   设哈夫曼树的叶子结点总数为m，则结点总数为多少?

    1. 设父节点为n，则节点总数 = m + n
    2. 从度的角度来算，有 2n + 1 = m + n，则n = m - 1
    3. 节点总数 = 2m - 1