树和二叉树

树和二叉树的一些基本术语：

【树的定义】

树（Tree）：n（n≥0）个结点构成的有限集合。当n=0时，称为“空树”；对于任一棵“非空树”（n>0），它具备以下性质：

• 树中有一个称为“根（Root）”的特殊结点，用r表示；
• 其余结点可分为m（m≥0）个“互不相交”的有限集T_1，T_2，..._，T_m，其中每一个集合本身又是一棵树，称为原来树的“子树（SubTree）”。

特点：

• 子树是不相交的；
• 除了根结点外，每个结点有且仅有一个父节点；
• 一棵N个结点的树有N-1条边。  

【一些基本术语】

• 结点的度（Degree）：结点的子树个数；
• 树的度：树的所有结点中最大的度数；
• 叶结点（Leaf）：度为0的结点；
• 父结点（Parent）：有子树的结点是其子树的根节点的父结点；
• 子结点/孩子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；
• 兄弟结点（Sibling）：具有同一个父结点的各结点彼此是兄弟结点；
• 路径和路径长度：从结点n₁到n_k的路径为一个结点序列n₁，n₂，...，n_k。n_i是n_i+1的父结点。路径所包含边的个数为路径的长度；
• 祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点；
• 子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙；
• 结点的层次（Level）：规定根结点在1层，其他任一结点的层数是其父结点的层数加1；
• 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度；

【二叉树（Binary Tree）的定义】

二叉树T：一个有穷的结点集合。这个集合可以为空；若不为空，则它是由根结点和称为其左子树T_L和右子树T_R的两个不相交的二叉树组成。二叉树的子树有左右顺序之分。

【特殊的二叉树】

• 斜二叉树（Skewed Binary Tree）

    

• 满二叉树（Full Binary Tree）/ 完美二叉树（Perfect Binary Tree）：除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树。

    

• 完全二叉树（Complete Binary Tree）：有n个结点的二叉树，对树中结点从上至下、从左到右顺序进行编号，编号为i（1≤i≤n）结点与满二叉树中编号为i结点在二叉树中的位置相同。

            

     完全二叉树的顺序存储结构中，按从上至下、从左到右顺序存储n个结点的完全二叉树的结点父子关系：

1. 根结点的序号为1；
2. 非根结点（序号i>1）的父结点的序号是：i / 2；
3. 结点（序号为i）的左孩子结点的序号是：2 * i，若2*i > n，则没有左孩子；
4. 结点（序号为i）的右孩子结点的序号是：2 * i + 1，若2*i+1 > n，则没有右孩子；

       

【二叉树的几个性质】

1. 一个二叉树第i层的最大结点数为：2^i-1，i≥1；
2. 深度为k的二叉树有最大结点总数为：2^k-1，k≥1；
3. 对任何非空二叉树T，若n₀表示叶结点的个数，n₂是度为2的非叶结点个数，那么两者满足关系：n₀=n₂+1；

    假设：叶结点个数为n₀；度为1的结点个数为n₁；度为2的结点个数为n₂。

    则二叉树的总边数N=2*n₂+n₁；总结点数N′=n₀+n₁+n₂；

    因N+1=N′，所以2*n₂+n₁+1=n₀+n₁+n₂；得n₀=n₂+1。