资源描述：
《离散数学 第2版 教学课件 作者 王元元 离散第24讲 根树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机专业基础课程授课人：王元元单位：计算机理论教研室理工大学指挥自动化学院PowerPointTemplate_Sub1二分图2平面图3树2第24讲根树根树《离散数学》第24讲Page147to153根树(rootedtree)定义（归纳定义）：树T称为根树，如果(1)T为一孤立结点v0。v0称为T的树根。(2)T1,T2,…,Tk为以v1,v2,…,vk为树根的根树，T由T1,T2,…,Tk及与v1,v2,…,vk相邻的结点v0所组成。v0称为T的树根。例:v0v1v2v3v4v5v6v7v8v9v10v11v124第24讲根树有
2、关术语定义：在根树的定义中(1)v1,v2,…,vk称为v0的儿子，v0称为它们的父亲。vi,vj同为一顶点v的儿子时，称它们为兄弟。(2)当vi为vi+1(i=1,2,…,l-1)的父亲时，v1是vl的祖先，vl为v1的子孙。(3)根树T自身及以它的树根的子孙为根的根树(T的子图)，均称为T的子树，后者又称为T的真子树。5第24讲根树有关术语v0v1v2v3v4v5v6v7v1v2的父亲V0的儿子v1的兄弟v7的祖先v1的子孙T的子树6第24讲根树根树的一些性质（1）根树的每个结点都是一棵子树的树根（2）除了树根，根树中每结点均为某
3、一结点的儿子；除了树叶，根树中每一结点均为某些结点的父亲（3）树根到叶有唯一的通路，这样的通路中最长一条的长度称为树高约定在根树的图示中，树根总画在最上方，父亲总比儿子高，兄弟位于同一水平线7第24讲根树例：树高为4的根树。v0v1v2v3v4v5v6v7v8v9v10v11v12子树子树的子树根树示例8第24讲根树根树的应用例：甲乙两人进行乒乓球赛，规定一方连胜两局或胜局首先达到3局者为胜方。问甲乙至少、至多要进行多少局比赛。解：用一棵根树来描述比赛的各种可能进程：分支结点——一局比赛关联的两边——胜负状况红边表示甲胜黑边表示乙胜结
4、论：至少2局，至多5局9第24讲根树根树的应用假定有重量相同的7枚硬币和一枚重量较轻的假币。如果用一架天平来找出这枚假币，需要多少次称量？给出称量策略。{1,2,3,4}vs.{5,6,7,8}{1,2}vs.{3,4}{1}vs.{2}{1}{2}{3}{4}{3}vs.{4}{5,6}vs.{7,8}{5}vs.{6}{5}{6}{7}{8}{7}vs.{8}10第24讲根树根树的应用{1,2,3}vs.{6,7,8}{1}vs.{3}{6}vs.{8}{4}vs.{5}{4}{1}{2}{3}{5}{6}{7}{8}11第24讲
5、根树完全二元树(binarytree)定义：除了树叶外，每个结点都有两个儿子的根树称为完全二元树。12第24讲根树完全二元树的性质完全二元树具有以下性质1、顶点个数必为奇数2、叶的数目le和顶点数目n满足le=(n+1)/23、树高h满足于13第24讲根树完全n元树类似于完全二元树，相应地还可定义完全三元树、完全四元树、……、完全n元树例：某人给四个朋友寄出一封连环信，要求收到信的每个人再把它寄给另外4个人。有些人按要求做了，但是其他人则没有寄出信。若没有人收到超过一封的信，且在100个人读过信但是不寄出它之后连环信就终止，则包括第一
6、个人在内，共有多少人看过信？有多少人寄出过信？14第24讲根树二元树(quasibinarytree)定义：每个结点都至多有两个儿子的根树称为二元树类似地，每个结点都至多有n个儿子的根树称为n元树15第24讲根树有序树和位置树定义：对各分支结点的诸儿子规定了次序的n元树称为n元有序树。对各分支结点的已排序的诸儿子规定了在图示中的位置，那么该n元有序树又称n元位置树。2元位置树各分支结点的左右儿子分别称作左儿子和右儿子。16第24讲根树n元有序树bcdefghkjiabcdefghijka17第24讲根树n元位置树bcdefghijka
7、bcdefghijka18第24讲根树二元位置树7981063425798106342519第24讲根树二元位置树的遍历算法系统地访问二元位置树每个结点的过程称为遍历算法二元位置树的遍历算法有先根算法（前序遍历）中根算法（中序遍历）后根算法（后序遍历）20第24讲根树先根算法（1）访问二元树T的树根（2）如果T有左儿子，以先根算法遍历T的左子树（3）如果T有右儿子，以先根算法遍历T的右子树procedurepreorder(T:二元位置树){r:=T的根;访问r;if(r有左儿子sl)preorder(以sl为根的左子树Tsl);if
8、(r有右儿子sr)preorder(以sr为根的右子树Tsr);}7981063425752498163021第24讲根树中根算法（1）如果T有左儿子，以中根算法遍历T的左子树（2）访问二元树T的树根（3）如果T有右儿子
