第21讲根树 1.根树 2.根树的周游 3.最优树, Huffman算法 4.最佳前缀码 《集合论与图论》第21讲
《集合论与图论》第21讲 1 第21讲 根树 1. 根树 2. 根树的周游 3. 最优树, Huffman算法 4. 最佳前缀码
根树 (rooted tree) 有向树:基图是树的有向图 根树(rooted tree):顶点分3类的有向树 名称入度出度个数 分树根0>01 支 点内点1>0 树叶10 《集合论与图论》第21讲
《集合论与图论》第21讲 2 根树(rooted tree) 有向树: 基图是树的有向图 根树(rooted tree): 顶点分3类的有向树 树叶 内点 树根 ? ? 1 个数 1 0 1 >0 分 0 >0 支 点 名称 入度 出度
层数与树高 鲁画法:树根在最上方,省略边的方向(从上 到下) 顶点v的层数(eve):L()=从树根到v路径 长度 树高(hegh:h(T=顶点的最大层数 《集合论与图论》第21讲
《集合论与图论》第21讲 3 层数与树高 画法: 树根在最上方, 省略边的方向(从上 到下) 顶点v的层数(level): L(v)=从树根到v路径 长度 树高(height): h(T)=顶点的最大层数
儿子,父亲,兄弟 儿子:u在上方与V相邻,V是u的儿子 父亲:u在上方与V相邻,u是v的父亲 兄弟:u与v有相同父亲,u是v的兄弟 祖先:从u可达v,u是v的祖先 秦后代:从u可达v,u是v的后代 《集合论与图论》第21讲
《集合论与图论》第21讲 4 儿子,父亲,兄弟 儿子: u在上方与v相邻, v是u的儿子 父亲: u在上方与v相邻, u是v的父亲 兄弟: u与v有相同父亲, u是v的兄弟 祖先: 从u可达v, u是v的祖先 后代: 从u可达v, u是v的后代
有序树( ordered tree) 婚有序树:给相同层数的顶点标上次序的根 树 《集合论与图论》第21讲
《集合论与图论》第21讲 5 有序树(ordered tree) 有序树: 给相同层数的顶点标上次序的根 树 1 1 1 1 1 2 2 3 2 2
又树 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
