树状结构

定义：树状结构是一个或多个节点的有限集合，它满足：

n有一个特定的点称为根节点（root），

n其余的节点分成n³0个独立的集合T1, …, Tn，每个集合也都是一个树状结构。我们讲T1, …, Tn为根节点的子树（subtree）。

节点与边：节点代表某项资料，而边是指由一节点到另一节点的分支。

祖先(ancestor)即点与子孙(descendant)节点：如图，A是所有节点的祖先，所有节点是A的子孙；而F是K与L的祖先，K与L是F的子孙。

父节点(parent node)与子节点(children node)：如图，B直接连到E与F且只差一个阶度，则B为E与F的父节点，E与F为B的子节点。

兄弟节点(sibling node)：拥有同一父节点的子节点。如：E与F。

叶节点(leaf node)或终点节点(terminal node)：没有子节点的节点。如：J、K等。

非叶节点(non-leaf node)或非终点节点(non-terminal node)：有子节点的节点。 如：A、B、F等等。

根节点(root node)：没有父节点的节点，为树的源头。 如：A。

分支度(degree)：指一个节点有几个子节点。 如：A为3、B为2、C为1、M为0。

阶度(level)：为树中的第几代，而根节点为第一代，阶度为1。

高度(height)：指一节点往下走到叶节点的最长路径。 如：A为3、F为1、L为0。

深度(depth)：指从根节点到某一节点的最长路径。如：C为1、M为3。

树林(forest)：由多个互斥树(disjoint tree)所组成。 如图将A移去便成为树林。

二元树(Binary tree)

二元树里每一节点的最大分支度为2。 如下右(a)、(b)、(c)。

图(a)称做左斜树(left skew tree)，每一节点的右子树皆为为集合。

图(c)称为满枝二元树(fully binary tree)，含有节点数共为2k-1。

图(b)称为完整二元树(complete binary tree)，节点排列顺序同满枝二元树，但节点数小于2k-1 。

二元哪种的第i阶最多有2i-1个节点。

如果有一n个节点的完整二元树，以循序的方式编号，如上图(c)。 则任何一个节点i，1 ≤i≤n，具有以下的特性：

若i= 1，则i为根节点，没有父节点。 而i≠ 1，其父节点为ëi/2û(表小于i/2的最大整数)。

若2i≤n，则i的左子节点在2i。 但若2i>n，则i没有左子节点。

若2i+1 ≤n，则i的右子节点在2i+1。 但若2i+1 >n，则i没有右子节点。

节点i在第［log2 ］＋1阶。