一、高级数据结构和算法：树的基本概念

1 树的基本概念

1.1 什么是树

树(Tree）是由n(n≥0)个有限节点组成一个具有层次关系的集合，n=0时称为空树。

在任意一棵非空树中：
（1）有且仅有一个特定的称为根（root）的结点。
（2）当n>1时，其余结点可分为m（m>0)个互不相交的有限集T1,T2,…,Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree)

1.2 树的构成

1.2.1 节点

• 分类

注：结点的度，即是指结点拥有子结点的数量。

• 关系
  （1）双亲节点或父节点(Parent)：若一个节点含有子节点，则这个节点称为其子节点的父节点。
  （2）孩子节点或子节点(Child)：一个节点含有的子树的根节点称为该节点的子节点。
  （3）兄弟节点(Sibling)：具有相同父节点的节点互称为兄弟节点。
  （4）节点的祖先：从根到该节点所经分支上的所有节点；
  （5）节点的子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
  

1.2.2 度

节点的度数：节点孩子的个数
树的度：树中节点的度最大值。

1.2.3 层次

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

1.2.4 深度与高度

节点的高度：节点到最远叶子节点的最长路径上边的数量。叶子节点高度为0。
节点的深度：节点到根节点的路径上边的数量。所有根节点深度为0。
树的高度：树的高度等于根节点的高度，等于最远叶子节点的深度。
树的深度：树的深度等于树的高度。
树的宽度：两个最长路径的叶子节点之间节点数。

1.3 树的分类

树按照子节点的数量分为二叉树和多叉树。

二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),每个节点最多有2个子节点,分别称为根结点的左子树和右子树。

多叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空树)。每个节点有多个子节点。

树按照子树是否有序分为有序树和无序树：

有序树：节点各子树从左到右有次序（不能互换）。
无序树：节点各子树从左到右无次序（能互换）。

1.4 特殊的树

满二叉树(Full Binary Tree)：二叉树中的每个结点恰好有两个孩子结点且所有叶子结点都在同一层。

完全二叉树(Complete Binary Tree)： 每层结点都完全填满，在最后一层上如果不是满的，则只缺少右边的若干结点。

1.5 二叉树的性质

1.5.1 通用性质

（1）在非空二叉树上，第i层至多有$2^{i-1}$个结点。
（2）深度为k的二叉树至多有$2^k-1$个结点；
（3）对任何一个二叉树，若其叶子结点数为$n_0$，度为2的节点数为$n_2$，则$n_0$=$n_2$+1；

1.5.2 满二叉树的性质

深度为k的满二叉树且有$2^k-1$个结点。

1.5.3 完全二叉树的性质

（1）n个结点的完全二叉树的深度为$k=[lo{g}_{2}n]+1$,这里[ ]符号表示向下取整
（2）若对一棵有n个结点的完全二叉树的结点按层（从第1层到第$[lo{g}_{2}n]+1$层)序自左至右进行编号,则对于编号为i（1<= i <=n)的结点：
a）如果i = 1，则结点 i 是二叉树的根，无双亲结点；如果i > 1，则其双亲结点编号是 [i/2]。
b）如果2i > n：则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i。
c）如果2i+1 > n：则结点i无右孩子；否则，其右孩子结点编号是2i+1。