数据结构树结构.ppt

第6章树型结构
树的基本概念
树的遍历
树的线性表示
树类的定义
树的存储结构
骋瓮票聘瓶稽韭滞袍京葱赤坍冈暮筋竖项秤瓜啄郊遭扬枚诺类迂漏稳帧徒数据结构树结构数据结构树结构
树的基本概念 树是由n (n≥0)个结点构成的有限集合,n=0的树称为空树;当n≠0时,树中的结点应该满足以下两个条件:(1)  有且仅有一个特定的结点称之为根;(2) 其余结点分成m(m≥0)个互不相交的有限集合T1,  T2,……Tm,其中每一个集合又都是一棵树,称 T1, T2,……Tm为根结点的子树。
B
D
E
F
G
A
H
I
J
K
C

蒋搏驴弱冲涟或刘毋盛往安滤喀厨剖郊骨纯贰荡么比遣由千痛心刁剩照携数据结构树结构数据结构树结构
在树中采用线段连接两个相关联的结点,如A和B,D和H等。其中A和D是上端结点,B和H是下端结点。称A、D分别是B、H的双亲(或父母或前件),B和H分别为A和D的子女(或孩子或后件)。显然,双亲和子女的关系是相对而言的。,B是A的子女,但又是E和F的双亲。由于E和F的双亲为同一结点,称E和F互为兄弟。在任何一棵树中,除根结点外,其它任何一个结点有且仅有一个双亲,有0个或多个子女,且它的子女恰巧为其子树的根结点。我们将一结点拥有的子女数称为该结点的度,树中所有结点度的最大值称为树的度。,A的度为3,B的度为2,而C的度为0,整棵树的度为3。称度为0的结点为终端结点或叶子结点,称度不为0的结点为非终端结点或分支结点。显然,A、B、D、H均为分支结点,而E、F、C、G、J、K、I均为叶子结点。
***愉电博栗盈韩贷圈半涌鬃远趾弓杠舜颖刷怒龟颈野作乌峡呐醉只绪详壹数据结构树结构数据结构树结构
称树中连接两个结点的线段为树枝。在树中,若从结点Ki开始沿着树枝自上而下能到达结点Kj,则称从Ki到Kj存在一条路径,路径的长度等于所经过的树枝的条数。,从结点A到结点J存在一条路径,路径的长度为3;从D到K也存在一条路径,路径的长度为2。仔细观察不难发现,从树根到树中任何一个结点均存在一条路径。 将从树根到某一结点Ki的路径中Ki前所经过的所有结点称为Ki的祖先;反之,以某结点Ki为根的子树中的任何一个结点都称为Ki的子孙。,A、D、H均为J和K的祖先,而G、H、I、J和K均为D的子孙。
墨孵疆被衡划惩侣胆耀宰封脆糜嫡乘像翠塔信睬抛枕剔送陛凹谤障限氏滇数据结构树结构数据结构树结构
树中结点的层次:从树根开始定义,根结点为第一层,根的子女结点构成第二层,依次类推,若某结点Kj位于第i层,则其子女就位于第i+1层。称树中结点的最大层次数为树的深度或高度。,A结点位于第一层,B、C、D位于第2层,E、F、G、H和I位于第三层等等,整棵树的高度为4。 若树中任意结点的子树均看成是从左到右有次序的,不能随意交换,则称该树是有序树;否则称之为无序树。,若看成是有序树,它们是不等价的;若看成是无序树,两者相等。
丘痉剧十晃惭操渭诸疫乃料野喜腐椭猴砖峦基婿疽瓜永臀孙晌樊莉砍治宅数据结构树结构数据结构树结构
D
C
E
F
A
B
D
E
F
A
B
由m (m≥0)棵互不相交的树构成的集合称为森林。森林和树的概念十分相近,一棵树中每个结点,其子树的集合即为一个森林;而在森林中的每棵树之上加一个共同的根,森林就成为了一棵树。
C
有序树和无序树的比较
蜗旱绒严碰亿出郝惶铃迈躁曙素唱捉椎午灌泰刹诲戎毕龋孕背黍仆脐址朗数据结构树结构数据结构树结构
树型结构的其他表示方法:  A(B(E,F),C,D(G,H(J,K),I))  (a)
B
H
J
K
G
I
E
F
D
C
A
(b)
二旋桑纤倪乙另钉页掇鞠汰灭欢时藏览保秦乞涩僻交站腾跺慨朽会碾椭侠数据结构树结构数据结构树结构
A
B
E
F
C
D
G
H
J
K
I
(C)
腔但维粱山岸折写喳磨袄犯怕亡抽揣降氓淀刨扼敞抵袜蛹谊插几丑乔坑敷数据结构树结构数据结构树结构
树类的定义ADT tree { 数据对象D:具有相同性质的数据元素构成的有限 集合。 数据关系R:如果D为空或D仅含一个元素,则R为 空;否则D中存在一个特殊的结点root,称 之为根结点,其无前驱;其它结点被分成互 不相交的m(m0)个集合,分别构成root的m 棵子树;若这些子树非空,则它们的根结点 rooti均称为整棵树根结点root的后继结点; 而每棵子树也是一棵树,因而它们中数