资源描述：
《树的存贮和集合运算.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、第五章树树的基本概念树的存贮结构树表示的集合运算树的遍历树的线性表示二叉树及遍历二叉树的顺序存贮穿线树和穿线排序树的基本概念06A树的基本概念根结点:树根分支结点:树中的每个分支叶子结点:树中的每个叶子树的定义:树是由一个结点或多个结点组成的有限集T有一个特定的结点称之为根结点其余的结点分成m(m>=0)个互不相交的有限集t0,t1,…tm-1.每个集合都是一棵树,称之为根结点的子树树的基本概念ABCDEFGHT={A,B,C,……H}根为A,有T0,T1,T2三棵子树T0={B,E,F}T00={E}T01={F}T1={C}无子树T2={D,G,H}T20={G,H}T200={H}
2、树的特征树至少有一个结点有且仅有一个结点没有前趋结点(根结点)除根结点外,其余所有结点有且仅有一个前趋结点包括根结点在内,每个结点可以有多个后继结点ABCDEFGHT=(D,R)D:为数据元素的集合R:为结点之间关系的集合D={A,B,C,…H}R={,,,,,,}基本术语结点的次数(度):一个结点的子树的个数树的次数(度):树中各结点的次数的最大值ABCDEFGH基本术语m次完全树:若树T是一棵m次树,并且T中非叶子结点的次数都为mABCDEFD基本术语父结点子结点兄弟结点结点的层次:一棵树的根结点所在的层次为0其他
3、结点所在的层次等于它 的父结点所在层次加1树的深度:树中结点的最大层次森林:多个不相交的树的集合ABCDEFGH基本术语路径路径长度祖先后代ABCDEFGH基本术语有序树对给定的m次树中,给树中的每个结点的每棵子树规定好序号树中的子树的相对次序不能变换从左到右用整数0,1,…m-1给结点的各棵子树规定序号假设结点所缺的子树总是最右面的主语谓语宾语我们唱国歌句子我们唱国歌/**+52-ABCD(A+B)*5/(2*(C-D))树的存贮结构树的标准形式树的逆形式树的扩充标准形式datapointersdata:存放结点的值…...pointers:结点的指针部分…….树的标准形式data:结
4、点的值pointer:指向子结点有m个字段,依次存放子结点所在地址若某结点没有序号为i的子结点,则在序号为i的字段中置为NULLdatapointerdatachild0child1……childm-1树的标准形式ABCDEFGHIJ三次树m=3树的标准形式ABC^^^D^E^^^F^^^G^^^H^^^I^^J^^^root1树的标准形式structnode{chardata;structnode*child[3];};typedefstructnodeNODE;NODE*root1;root1:指向树的根结点的指针树的逆形式存贮data:结点的值parent:指向父结点存放父结点所在
5、地址对根结点,置NULLdataparent树的逆形式存贮structr_node{chardata;structr_node*parent;};typedefstructr_nodeR_NODE;R_NODE*root2;root2:指向树的根结点的指针树的逆形式存贮ABCDEFGHIJ树的逆形式存贮A^BCDEFGHIJroot2树的扩充标准形式data:结点的值poniter:指向子结点,具有m个分量parent:指向父结点,只有1个分量datapointerparentdatachild0child1……childm-1parent树的扩充标准形式ABCDEFGHIJ树的扩充标准
6、形式A^BC^^^D^E^^^F^^^G^^^H^^^I^^J^^^root3树的扩充标准形式structe_node{chardata;structe_node*child[3];structe_node*parent;}typedefstructe_node,E_NODE;E_NODE*root3;用树表示集合假设:集合的元素由数0,1,2,….,n-1组成所表示的集合都是不相交的并集:UNION(Si,Sj）查寻:FIND(i)用树表示集合S0={0,6,7,8}S1={1,4,9}S2={2,3,5}UNION(s0,s1)={0,6,7,8,1,4,9}FIND(5)=s206
7、78145235s0s1s2求并集用树表示两个集合将其中的一棵树作为另一棵树的子树新得的树表示两个集合的并集将一棵树的根结点的parent指向另一棵树的根结点06781450678145235S0S1S2namepoint集合的数据表示形式对每个集合的名字用指针指向表示该集合的树的根结点…...每个根结点有一个指针指向集合的名字…...求并集用表示集合的树根来标识集合用0,1,…..,n-1对结点进行编号作为结点值用一个整数数组来存
