例:有向树和根树 定义86.3设T为一棵非平凡的根树,u、v是T中两点。若u到v有有向路,则称u是v 的祖先,v是u的后代;若u到v有有向边,则称u是v的父亲,v是u的儿子。若u和v 有同一个父亲,则称u和v是兄弟 定义86.4 (1)若将根树T中层数相同的顶点都标定次序(比如从左到右),则称T为有序树。 (2)若T的每个顶点至多有r个儿子,则称T为r叉树;又若r叉树是有序的,则称它为r 叉有序树。 (3)若T的每个非叶子顶点都恰好有r个儿子,则称T为r叉正则树;又若T是有序的,则 称它为r叉正则有序树 (4)若T为r叉正则树,且每个树叶的层数都等于树高,则称T为r叉完全正则树;又若T 是有序的,则称它为r叉完全正则有序树。 定义86.5设T为一棵根树,ν是T中一个顶点。称v及其后代的导出子图为T的以v为根 的根子树。2叉正则有序树的每个非叶子顶点的两个儿子导出的根子数分别称为左子树和右 子树。 二、2叉树与淘汰赛 定理86.,1有m个分支点的t叉正则树T的阶为v=m+1。 证明:因为T中除了树根外,其余点都是儿子,而T中m个分支点共有tm个儿子。故 v=m+1 推论86.1有m个分支点的t叉正则树T有(-1)m+1个叶子。 证明:因T中除了分支点便是叶子,故由上述定理,T共有(1m+1)m=(1-1)m+1个叶子。 推论862有m个分支点的2叉正则树T有2m+1个顶点,其中有m+1个叶子。 定理862设T是高为h的v阶2叉树,则h+1≤v≤2+-1 证明:设T中第i层的顶点有n个(0≤≤h),则∑n=,又1≤n≤2,故 h+l=1≤、n=v≤>2 定理83设T是高为h的v阶2叉树,则h2/eg2(*1 证明:由上一定理,v21-1,即2≥+1.从而b2l+ 例86.1假设某台计算机有一条加法指令,每次执行该指令可计算3个数之和。如果要计算 1111 例：有向树和根树 定义 8.6.3 设 T 为一棵非平凡的根树，u、v 是 T 中两点。若 u 到 v 有有向路，则称 u 是 v 的祖先，v 是 u 的后代；若 u 到 v 有有向边，则称 u 是 v 的父亲，v 是 u 的儿子。若 u 和 v 有同一个父亲，则称 u 和 v 是兄弟。 定义 8.6.4 (1) 若将根树 T 中层数相同的顶点都标定次序（比如从左到右），则称 T 为有序树。 (2) 若 T 的每个顶点至多有 r 个儿子，则称 T 为 r 叉树；又若 r 叉树是有序的，则称它为 r 叉有序树。 (3) 若 T 的每个非叶子顶点都恰好有 r 个儿子，则称 T 为 r 叉正则树；又若 T 是有序的，则 称它为 r 叉正则有序树。 (4) 若 T 为 r 叉正则树，且每个树叶的层数都等于树高，则称 T 为 r 叉完全正则树；又若 T 是有序的，则称它为 r 叉完全正则有序树。 定义 8.6.5 设 T 为一棵根树，v 是 T 中一个顶点。称 v 及其后代的导出子图为 T 的以 v 为根 的根子树。2 叉正则有序树的每个非叶子顶点的两个儿子导出的根子数分别称为左子树和右 子树。 二、2 叉树与淘汰赛 定理 8.6.1 有 m 个分支点的 t 叉正则树 T 的阶为ν = tm + 1。 证明：因为 T 中除了树根外，其余点都是儿子，而 T 中 m 个分支点共有 t⋅m 个儿子。故 ν = + tm 1。 推论 8.6.1 有 m 个分支点的 t 叉正则树 T 有(t−1)m+1 个叶子。 证明：因 T 中除了分支点便是叶子，故由上述定理，T 共有(t⋅m+1)−m= (t−1)m+1 个叶子。 推论 8.6.2 有 m 个分支点的 2 叉正则树 T 有 2m+1 个顶点，其中有 m+1 个叶子。 定理 8.6.2 设 T 是高为 h 的ν 阶 2 叉树，则 1 1 21 h h ν + + ≤≤ − 。 证明：设 T 中第 i 层的顶点有 ni 个（0 ≤ i h ≤ ），则 0 h i i n ν = ∑ = ，又1 2i i ≤ n ≤ ，故 1 00 0 1 1 22 1 hh h i h i ii i h n ν + == = += ≤ = ≤ = − ∑∑ ∑ 。 定理 8.6.3 设 T 是高为 h 的ν 阶 2 叉树，则 2 1 log ( ) 2 h ⎡ ν + ⎤ ≥ ⎢ ⎥ ⎢ ⎥ 。 证明：由上一定理， 1 2 1 h ν + ≤ − ， 即 1 2 2 h ν + ≥ 。从而 2 1 log ( ) 2 h ⎡ ν + ⎤ ≥ ⎢ ⎥ ⎢ ⎥ 。 例 8.6.1 假设某台计算机有一条加法指令，每次执行该指令可计算 3 个数之和。如果要计算