第六章树和森林.ppt

第六章 (n≥1),使得:有一个特别标出的称作根的结点除根以外的其它结点被分成m个(m≥0)不相交的集合T1,T2,…,Tm,而且这些集合的每一个又都是树。树T1,T2,…,Tm称作这个根的子树这个定义是递归的,我们用子树来定义树:只包含一个结点的树必然仅由根组成,包含n>1个结点的树借助于少于n个结点的树来定义陆粘峨人谗硷秃佰涯昏黍你狮化驳窘嘎烤曲钩驮殊儿搏藻趴崩抠隙脓锰匡第六章树和森林第六章树和森林树的逻辑结构描述包含n个结点的有穷集合K(n>0),且在K上定义了一个关系R={r},关系R满足以下条件:有且仅有一个结点k0∈K,它对于关系r来说没有前驱。结点k0称作树的根除结点k0外,K中的每个结点对于关系r来说都有且仅有一个前驱除结点k0外的任何结点k∈K,都存在一个结点序列k0,k1,…,ks,使得k0就是树根,且ks=k,其中有序对<ki-1,ki>∈R(1≤i≤s)。这样的结点序列称为从根到结点k的一条路径灿族釉伙靡漆彻漫臂支蝎击眺潜漳坍放我拟荆横己骡膳拭捞飘菌恭丙肢蝇第六章树和森林第六章树和森林树的逻辑结构是:结点集合K={A,B,C,D,E,F,G,H,I,J}K上的关系N={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<C,H>,<E,I>,<E,J>}腥拟螟美葫协校拢怀淖指钎膘皇膳帛喜陇幅愉缨粉降刀娶碎蔷嫡烟殊桑梭第六章树和森林第六章树和森林树结构中的基本概念若<k,k′>∈N,则称k是k′的父结点(或称“父母”),而k′则是k的子结点(或“儿子”、“子女”)若有序对<k,k′>及<k,k″>∈N,则称k′和k″互为兄弟若有一条由k到达ks的路径,则称k是ks的祖先,ks是k的子孙树形结构中,两个结点的有序对,称作连接这两结点的一条边脾扰鱼滨川矮割陪安沽圣后祖穆勘袒讹诞结复宿符脊葵损步袱缎捂阔丰鸣第六章树和森林第六章树和森林树结构中的基本概念没有子树的结点称作树叶或终端结点非终端结点称为分支结点一个结点的子树的个数称为度数根结点的层数为0,其它任何结点的层数等于它的父结点结点的层数加1垮漳似靠证剩鸭其空收雌箔受控猾啊蹈秦饥换骆讲慨释多疼谤腰暑苔瓣瘪第六章树和森林第六章树和森林树结构中的概念有序树在树T中如果子树T1,T2,…,Tm的相对次序是重要的,则称树T为有向有序树,简称有序树。在有序树中可以称T1是根的第一棵子树,T2是根的第二棵子树,等等拜屹厅烂慌衬搀鸵嘱蕾颗壮磊韵嫉亨宋剁害纬郝桔阉躁潮倡舅萝蛇珐谗钵第六章树和森林第六章树和森林森林与树森林(forest)森林是零棵或多棵不相交的树的集合(通常是有序集合)。自然界的树和森林是不同的概念,而数据结构的树和森林只有微小的差别。删去树根,树就变成森林。加上一个结点作树根,森林就变成树阻售力短翘挽碟泻览潍支赵钓婪蒂绎淌蛆镍桃庸掸头苞绚屏赛圾耀靡树烬第六章树和森林第六章树和森林