数据结构--树

《数据结构--树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3.1基本术语3.2二元树3.3树3.4森林与二元树间的转换3.5树的应用第三章树（Tree）线性表——元素之间的线性关系树——元素之间的层次关系3.1基本术语[定义]一1、一个结点x组成的集{x}是一株树，这个结点x也是这株树的根。2、假设x是一个结点，T1，T2，…，Tk是k株互不相交的树，我们可以构造一株新树：令x为根，并有k条边由x指向树T1，T2，…，Tk。这些边也叫做分支，T1，T2，…，Tk称作根x的树之子树（SubTree）。树是n（≥0）个结点的有限集。在任意一棵非空树中：1、有且仅有特定的称为根（Root）的结点；2、当n＞1时，其余

2、结点可分为m（＞0）个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。[定义]二3.1基本术语[定义三]T=（D，R）D：具有相同类型的数据元素的集合。R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H}，H是如下的二元关系：1、在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；2、若D-{root}≠￠，则存在D-{root}的一个划分D1，D2，…，Dm（m＞0），对任意j≠k（1≤j，k≤m）有Dj∩Dk=￠，且对任意的i（1≤i≤m），唯一存在数据元素xi

3、∈Di，有∈H;3、对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1，H2，…，Hm（m＞0）,对任意j≠k（1≤j，k≤m）有Hj∩Hk≠￠,且对任意的i（1≤i≤m），Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定义的树，称为根root的子树。3.1基本术语ABCDEFGHIJKLM图一第1层第2层第3层第4层第5层ABCDEFGHIJKLM图二树高为5常用术语：结点度叶（终端结点）非终端结点分支路长父亲双亲儿子兄弟子孙祖先层结点的高树的高（深度）有序树&无序树3.1基本

4、术语ABCACB≠森林forest：是n≥0株互不相交的树的集合。3.2二元树(binarytree)[定义一]二元树是有限个结点的集合，这个集合或者是空集，或者是由一个根结点和两株互不相交的二元树组成，其中一株叫根的做左子树，另一棵叫做根的右子树。3.2.1二元树的定义和基本性质3.2.1二元树的定义和基本性质[定义二]BinaryTree=(D,R)D：指数据对象，是由相同类型的数据元素组成的集合。R：为数据元素间的关系：若D＝¢，则R=¢，称Binarytree为空树；若D≠￠；则R={H}，H是如下二元关系：⑴在D中存在唯一的称为根的数据元素ro

5、ot，它在关系H下无前驱；⑵若D-{root}≠￠，则存在D-{root}={Dl，Dr}，且Dl∩Dr=¢；⑶若Dl≠￠，则Dl中存在唯一的元素xl，∈H，且存在Dl上的关系Hl∈H；若Dr≠￠，则Dr中存在唯一的元素xr，∈H，且存在Dr上的关系Hr∈H；H={，，Hl，Hr}；⑷（Dl，{Hl}）是符合本定义的二元树，称为根的左子树；（Dr，{Hr}）是符合本定义的二元树，称为根的右子树；3.2.1二元树的定义和基本性质二元树的性质：性质1：在二元树中第i层的结点数最多为2i-

6、1（i≥1）。性质2：高度为k的二元树其结点总数最多为2k－1（k≥1）性质3：对任意的非空二元树T，如果叶结点的个数为n0，而其度为2的结点数为n2，则：n0=n2+1[定义]深度为k且有2k－1个结点的二元树称为满二元树。层序编号：对满二元树的结点进行连续编号。从根结点开始，从上而下，自左至右。[定义]深度为k的，由n个结点的二元树，当且仅当其每个结点都与深度为k的满二元树中编号从1至n的结点一一对应，称之为完全二元树。3.2.1二元树的定义和基本性质二元树的性质(续)：性质4具有n个结点的完全二元树的深度为log2n+1。性质5如果对一棵有n个结点

7、的二元树的结点按层序编号，则对任一结点i有：⑴如果i=1，则结点i是二元树的根，无双亲；如果i＞1，则其双亲结点是i/2；⑵如果2i＞n，则结点i无左孩子结点，否则其左孩子结点是2i；⑶如果2i+1＞n，则结点i无右孩子结点，否则其右孩子结点是2i+1。3.2.1二元树的定义和基本性质二元树的遍历DLR遍历：根据原则，按照一定的顺序访问二元树中的每一个结点，使每个结点只能被访问一次。根（D）、左孩子（L）和右孩子（R）三个结点可能出现的顺序有：①DLR②DRL③LDR④LRD⑤RLD⑥RDL原则：左孩子结点一定要在右孩子结点之前访问。要讨论的三种操作分别

8、为：①先根顺序DLR，②中根顺序LDR，③后根顺序LRD二元树的遍历①先根顺序遍