第2章非线性数据结构树和图

《第2章非线性数据结构树和图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章非线性数据结构树和图西安交通大学计教中心ctec.xjtu.edu.cn树形结构树形结构是以分支关系来定义的层次结构。在客观世界中树形结构广泛存在，并应用于：人类社会的族谱、家谱、行政区域划分管理；各种社会组织机构；在计算机领域中，用树表示源程序的语法结构；在OS中，文件系统、目录等组织结构也是用树来表示的。2树的逻辑结构树是一种数据结构，可用二元组表示为：Tree=（D，R）其中：D是具有相同特性的数据元素的集合；R是数据元素间逻辑关系的集合，且满足：在D中存在唯一的称为根的数据元素，没

2、有前趋；D中其余数据元素都有且只有一个前趋；D中所有元素，或有若干个互不相同的后继（子树），或无后继（叶结点）；则称Tree为树。3树的递归定义:树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足：1）其中有一个特定的元素称为T的根root。2）除根以外的集合可被划分为m个不相交的子集T1，T2，…，Tm，其中每个子集都是树。它们称为根root的子树。GACFDEB树的一般形式4树结构举例C1（章）BOOK1.1(节)1.2C1C2C3C22.11.1

3、1.22.12.22.32.112.122.22.1.12.1.22.3C3书目录目录树树结构5与树相关的术语•结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。•结点的度：结点拥有的非空子树的个数。•树的度：树中所有结点的度的最大值。•叶子结点：度为0的结点。•分支结点：至少有一个非空子树的结点。•孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。6•兄弟结点：具有相同父结点的结点互为兄弟结点。•结点的层次：根结点的层次

4、为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。•树的深度：树中结点所在的最大层次。•有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。•森林：由零棵或有限棵互不相交的树组成的集合。7二叉树的定义二叉树是另一种树形结构：Binary_Tree=(D,R)其中:D是具有相同性质的数据元素的集合;R是在D上某个两元关系的集合,且满足:D中存在唯一称为根的数据元素,没有前趋;D中其余元素都有且仅有一个前趋;每个结点至多只有两个子树;D中元素,或有两

5、个互不相交后继,或无后继;左、右子树分别又是一棵二叉树。8二叉树的五种基本形态（a）（b）（c）（d）（e）O空结点O单个结点OO右子树为空的二叉树OO左子树为空的二叉树左、右子树非空的二叉树OOO9二叉树与树的区别表达形式（对3个结点）普通树二叉树（a）（b）（c）（d）（e）OOOOOO有两种不同形式（a）（b）OOOOOOOOOOOOOOO有五种不同形式10二叉树与树的区别（二）观念二叉树的子树有顺序关系，分左子树和右子树，而树则无此区分；二叉树的分支度一定为0、1或2，而树的度可大于2。1

6、1特殊二叉树满二叉树完全二叉树平衡二叉树二叉排序树12满二叉树当二叉树每个分支结点的度都是2，且所有叶子结点都在同一层上，则称其为满二叉树。若k为二叉树T的深度，且T中共有2k-1个结点（k1），则称T为满二叉树。（a）满二叉树（b）非满二叉树OOOOOOOOOOOOO13完全二叉树从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被称为完全二叉树。（a）完全二叉树（b）非完全二叉树OOOOOOOOOOO叶结点只可能出现在层次最大的两层上。14平衡二叉树二叉树上任一结点的左子树深

7、度减去右子树深度的差值，称为该结点的平衡因子。任意结点左、右子树的深度之差的绝对值1，这样的树称为平衡二叉树。OOOOOOOOOOOOOOOO（a）平衡二叉树（b）非平衡二叉树15二叉排序树定义二叉排序树或者是空二叉树；或者是：左子树上所有结点的值均小于根结点的值；右子树上所有结点的值均大于等于根结点的值；左、右子树本身又是一棵二叉排序树。10571114181515141851012137（a）二叉排序树（b）非二叉排序树16二叉树的性质一二叉树的第i层上至多有2i-1个结点（i1）。利用归

8、纳法证明：i=1时，只有一个结点，对的；假设对所有的j，1ji，命题成立，即在第j层上，至多有2j-1个结点。由归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点的度至多为2，故第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2×2i-2=2i-1。17二叉树的性质二深度为h的二叉树上至多含2h-1个结点(h≥1)。i=1h（第i层上的最大结点数）hi=1=2i-1=2h-1证明：由性质一可见，深度为h的二叉树的最大结点数为：18包含n(n>0)个结点