又树 t-ary tree) 又树:Wv∈VT,d()r 秦正则 regular又树:WvEV(T,d()=r 完全 omplete正则叉树:树叶V, L()=h(T) 有序r叉树,有序正则叉树,有序完全正则r 叉树 《集合论与图论》第21讲
《集合论与图论》第21讲 6 r叉树(t-ary tree) r叉树: ∀v∈V(T), d+(v)≤r 正则(regular)r叉树: ∀v∈V(T), d+(v)=r 完全(complete)正则r叉树: ∀树叶v, L(v)=h(T) 有序r叉树,有序正则r叉树,有序完全正则r 叉树
定理1413 定理1413:设正则(2)叉树T有个分支 点和t个树叶,则(-1)j=t1 证明:当把一个树叶变为一个分支点时, 增加(-1)个树叶,所以t(r-1)+b 当t=1时,=0,所以b=1.所以七(1+1.# 证法2:数学归纳法 《集合论与图论》第21讲
《集合论与图论》第21讲 7 定理14.13 定理14.13: 设正则r(≥2)叉树T有i个分支 点和t个树叶, 则(r-1)i=t-1. 证明: 当把一个树叶变为一个分支点时, 增加(r-1)个树叶, 所以 t=(r-1)i+b. 当t=1时, i=0, 所以b=1. 所以t=(r-1)i+1. # 证法2: 数学归纳法
根子树( noted subtree 根子树:T是根树,VEVT,由本身及其 所有后代导出的子图T 左子树右子树:二叉树中分支点的左右 两个儿子导出的根子树 《集合论与图论》第21讲
《集合论与图论》第21讲 8 根子树(rooted subtree) 根子树: T是根树, v∈V(T), 由v本身及其 所有后代导出的子图Tv 左子树,右子树: 二叉树中分支点的左右 两个儿子导出的根子树
根树的周游(traces) 根树的周游:列出根树的所有顶点,每个 顶点恰好出现一次 中序行遍:左子树,根,右子树 前序行遍:根,左子树,右子树 后序行遍左子树,右子树,根bc 例:中序: dbigjehacf e 前序: abdegijhcf 后序: dijighebfca 《集合论与图论》第21讲
《集合论与图论》第21讲 9 根树的周游(travesal) 根树的周游: 列出根树的所有顶点, 每个 顶点恰好出现一次 中序行遍: 左子树, 根, 右子树 前序行遍: 根, 左子树, 右子树 后序行遍: 左子树, 右子树, 根 例: 中序: dbigjehacf 前序: abdegijhcf 后序: dijghebfca a b d e g c f h i j
四则运算式与二叉树 (a*(bC)*de)(+g)÷(h*(+) e 《集合论与图论》第21讲
《集合论与图论》第21讲 10 四则运算式与二叉树 ((a∗(b+c))∗d-e)÷(f+g)÷(h∗(i+j)) ÷ ÷ ∗ ∗ ∗ - + + a + b c d e f g h i j