树型结构树的基本概念学习教案

1、会计学1树型结构树型结构(jigu) 树的基本概念树的基本概念第一页，共41页。BDEFGAHIJKC第1页/共41页第二页，共41页。第2页/共41页第三页，共41页。第3页/共41页第四页，共41页。第4页/共41页第五页，共41页。DCEFABDEFABC第5页/共41页第六页，共41页。BHJKGIEFDCA(b)图6.1的嵌套集合(jh)表示法第6页/共41页第七页，共41页。ABEFCDGHJKI (C)凹入表示法第7页/共41页第八页，共41页。 rooti rooti均称为整棵树根结点均称为整棵树根结点rootroot的的后继结点；后继结点；而每棵子树也是一棵树，因而它们而每棵

2、子树也是一棵树，因而它们中数据元中数据元素间的关系也同样满足素间的关系也同样满足R R的定义。的定义。树的基本操作如下：树的基本操作如下：（1 1）Inittree(T) Inittree(T) （2 2）Cleartree(T) Cleartree(T) 第8页/共41页第九页，共41页。第9页/共41页第十页，共41页。双亲双亲(shungqn)表示法表示法在树中，除根结点没有在树中，除根结点没有双亲双亲(shungqn)外，其外，其他每个结点的双亲他每个结点的双亲(shungqn)是唯一确定是唯一确定的。因此，根据树的这种的。因此，根据树的这种性质，存储树中结点时，性质，存储树中结点时，

3、可以包含两个信息：结点可以包含两个信息：结点的值的值data和体现结点之间和体现结点之间相互关系的属性相互关系的属性_该结点该结点的双亲的双亲(shungqn)parent。借。借助于每个结点的这两个信助于每个结点的这两个信息便可唯一地表示任何一息便可唯一地表示任何一棵树。这种表示方法称为棵树。这种表示方法称为双亲双亲(shungqn)表示法。表示法。第10页/共41页第十一页，共41页。第11页/共41页第十二页，共41页。BCDEFGAHIKJ012345678910第12页/共41页第十三页，共41页。第13页/共41页第十四页，共41页。第14页/共41页第十五页，共41页。rootd

4、atachild0child1 child2 第15页/共41页第十六页，共41页。第16页/共41页第十七页，共41页。012345678910root第17页/共41页第十八页，共41页。第18页/共41页第十九页，共41页。第19页/共41页第二十页，共41页。012345678910childnextdatafirstchildtreelist第20页/共41页第二十一页，共41页。第21页/共41页第二十二页，共41页。datafirstchildrightsiblingroot第22页/共41页第二十三页，共41页。次访问第二层上的所有结点，再以同样次访问第二层上的所有结点，再以同

5、样的方式访问第三层上的所有结点，的方式访问第三层上的所有结点，最后访问树中最低一层的所有结点。最后访问树中最低一层的所有结点。第23页/共41页第二十四页，共41页。BCDEFGAHI第24页/共41页第二十五页，共41页。第25页/共41页第二十六页，共41页。第26页/共41页第二十七页，共41页。第27页/共41页第二十八页，共41页。第28页/共41页第二十九页，共41页。第29页/共41页第三十页，共41页。其中子树的括号表示同样应该遵循以上规则。其中子树的括号表示同样应该遵循以上规则。第30页/共41页第三十一页，共41页。ABCFGHDEJI第31页/共41页第三十二页，共41页。第32页/共41页第三十三页，共41页。第33页/共41页第三十四页，共41页。第34页/共41页第三十五页，共41页。第35页/共41页第三十六页，共41页。ABCFGHDEJI第36页/共41页第三十七页，