《《树与二叉树整》ppt课件》由会员分享，可在线阅读，更多相关《《树与二叉树整》ppt课件（138页珍藏版）》请在金锄头文库上搜索。
1、第6章 树与二叉树,树 (tree) 结构是一种多分支多层次的数据结构，由一组结点组成。由于它呈现与自然界树类似的结构形式，所以称之为树。在许多算法中，常用树型结构描述问题的求解过程或表示求解的对策等。,树的逻辑结构,6.1 树,2,树的存储结构,树是由 n (n0) 个结点组成的有限集。在任意一棵非空树 T 中：, 有且仅有一个特定的称为根 (root) 结点；, 当 n1 时，其余结点分成 m (m0) 个互不相交的有限集T1，T2，Tm，其中每一个集合本身又都是一棵树，并且称为根的子树。,3,6.1.1 树的逻辑结构,1. 树的定义,4,2. 树的基本操作,树结构中经常会用到一些基本术语
2、。例如：,结点,结点的度,叶结点,分支结点,树的度,双亲及孩子,兄弟,堂兄弟,祖先,子孙,层次,树的深度,有序树,无序树,森林,5,3. 树的基本概念,6,6.1.2 树的存储结构,假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在连续空间中的位置。,typedef struct / 双亲表示结构定义 TNode treeMAX; / 结点数组 int nodenum; / 结点数 ParentTree; / 双亲表示结构类型名,#define Max 100 typedef struct TNode / 结点结构定义 DataType data; / 数据域 in
3、t parent; / 双亲位置域 TNode;,1. 双亲表示法,7,树,数组下标,0,1,2,3,4,5,6,7,8,9,双亲存储结构,由于树中每个结点可能有多棵子树，则可以用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，此时，链表中的结点可以有如下 3 种结构格式：,8,同构结点格式,不同构结点格式,单链表存储结构,2. 孩子表示法,(1) 同构结点格式。即多重链表中的结点是同构的。,其中 d 为树的度。由于树中很多结点的度都小于 d，所以链表中有很多空链域，空间比较浪费。,9,设树的度为 k，结点数为 n。若采用同构结点格式，每个结点具有 k 个固定链域，那么共有
4、 nk 个链域。由于 n 个结点要有 ( n - 1) 个枝相连，而每枝需要 1 个链域。因此，这棵树的空链域的个树为： n ( k 1 ) +1。,由此可知，树的度越大，空链域越多。如果采用同构结点格式将造成空间的极大浪费。,(2) 不同构结点格式。即多重链表中的结点是不同构的。,其中,种存储结构避免了孩子表示法存储结构中出现的空链域，节约存储空间。但是由于每个结点的孩子链域数不同，所以在这种结构上进行的各种操作不易实现。,为结点的度，degree 域的值和,相同。这,10,(3) 单链表存储结构。即把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，则 n 个结点有 n
5、 个孩子链表（叶子结点的孩子链表为空表）。而 n 个头指针又组成一个线性表，为了便于查找，可以采用顺序存储结构。,11,树,0,1,2,3,4,5,6,7,8,9,根位置,12,树的孩子兄弟表示法又称二叉树表示法，或二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点的结构相同，都有 3 个域：数据域 data 存放树中结点的信息；孩子域 firstchild 存放该结点的第一个孩子结点（从左算起）的地址；兄弟域 nextsibling 存放该结点的下一个兄弟结点（从左向右）的地址。,13,3. 孩子兄弟表示法,树,14,二叉树 (binary tree) 是另一种树型结构，它的特点是
6、每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。,二叉树的逻辑结构,6.2 二叉树,15,二叉树的基本性质,二叉树的存储结构,二叉树是一个有限的结点的集合，该集合或者为空，或者由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,16,二叉树定义是一个递归定义，即在二叉树的定义中又用到二叉树的概念。,6.2.1 二叉树的逻辑结构,1. 二叉树的定义,性质1：在二叉树的第 i 层上至多有 2i-1 个结点（i1）。,证明：利用归纳法容易证得此性质。 i = 1 时，只有一个根结点。2i-1 = 20 = 1，命题成
7、立。 假定对所有的 j (1ji)，命题成立，即第 j 层上至多有 2 j-1 个结点。那么，可以证明 j = i 时命题也成立。 根据归纳假设，第 i-1 层上至多有 2i-2 个结点。由于二叉树的每个结点的度最多为 2，所以在第 i 层上最多的结点数为第 i-1 层上的 2 倍，即 22i-2 = 2i-1。,17,6.2.2 二叉树的基本性质,性质2：深度为 k 的二叉树至多有 2k1 个结点（k1）。,= 2k1,18,证明： 由性质1 可见，深度为 k 的二叉树的最大结点数为,性质3：对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 n2 + 1。
8、,19,证明： (1) 设 n1 为二叉树 T 中度为 1 的结点数。n 为二叉树中总结点数。因为二叉树中所有结点的度均小于或等于 2，则：n = n0 + n1 + n2 。 (2) 设 B 为二叉树 T 中的分支总数。 从入支的角度看，二叉树中除了根结点外，其余结点都有一个且仅有一个入支，则：n = B + 1。 从出支的角度看，度为 1 的结点只有一个出支，度为 2 的结点有两个出支，则：B = n1 + 2n2 故：n = n1 + 2n2 + 1；最后得到： n0 = n2 + 1。,为便于介绍下面两个二叉树性质，先了解满二叉树 (full binary tree) 和完全二叉树 (
9、complete binary tree) 的概念。,20,满二叉树的特点是：每一层上的结点数都达到最大值；满二叉树中只有度为 0 和度为 2 的结点，不存在度为 1 的结点；每一个结点均有两棵高度相同的子树，叶子结点都在树的最下面的同一层上。,满二叉树：一棵深度为 k 并且有 2k-1 个结点的二叉树，称之为满二叉树。,如果对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左至右。由此可以引出完全二叉树的定义。,完全二叉树的特点是：二叉树中的叶子结点只可能出现在二叉树中层次最大的两层上；最下一层的结点一定是从最左边开始向右放的；并且若某个结点没有左孩子，则它一定没有右孩子。,21,完
10、全二叉树：一棵深度为 k 并且有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称之为完全二叉树。,性质4：具有 n 个结点的完全二叉树的深度为 log2n + 1 （ x 表示不大于 x 的最大整数）,22,证明： 设所求完全二叉树深度为 k，则它的前 k-1 层可视为深度为 k-1 的满二叉树，共有 2k-1-1 个结点，故该完全二叉树的总结点数 n 一定满足式子：n2k-1-1。 根据性质 2，可以确定：n 2k-1 由此得到：2k-1-1n2k-1 或 2k-1 n2k 等价关系：k-1log2nk 因为 k 是整数，所以 k
11、-1 = log2n，即 k = log2n + 1,性质5：如果对一棵有 n 个结点的完全二叉树（此二叉树的深度为 log2n +1）的结点按照层次编号（从第 1 层到第 log2n +1 层，每层从左到右），那么对任一结点 i（1 i n），有,23,(1) 若 i = 1，则结点 i 是二叉树的根，没有双亲结点；若 i 1，则其双亲结点是结点 i / 2。,(2) 若 2i n，则结点 i 没有左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i。,(3) 若 2i + 1n，则结点 i 没有右孩子；否则其右孩子是结点 2i + 1。,二叉树和其他数据结构一样也分顺序存储结构和链式存
12、储结构；而链式存储结构又分二叉链表存储结构和三叉链表存储结构。,24,6.2.3 二叉树的存储结构,二叉树的顺序存储结构就是用一组地址连续的存储单元来存放一棵二叉树的所有结点元素。,# define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef DataType SqBiTreeMAX_TREE_SIZE; / 定义顺序树类型SqBiTree，约定0 号单元存储根结点 SqBiTree bt; /定义了一棵二叉树bt,25,1. 顺序存储结构,顺序存储结构仅适用于完全二叉树。如果存储一般二叉树，则会造成存储空间的浪费，这时就需要使用二叉树的链式存储结构。 二叉树的
13、链式存储结构主要是设计结点结构。根据结点结构的不同，又可以分为二叉链表存储结构和三叉链表存储结构。,26,2. 链式存储结构,(1) 二叉链表存储结构,tyepdef struct Node DataType data; structNode *lchild, *rchild; / 左右孩子指针 BiTNode *BiTree; / 二叉链表存储结构类型名,左孩子指针,右孩子指针,数据域,27,二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点包括三个域：数据域、左指针域和右指针域，称为二叉链表存储结构。,(2) 三叉链表存储结构,tyepdef str
14、uct TriTNode TElemType data; struct TriTNode *lchild, *rchild, *parent; TriTNode *TriTree; / 三叉链表存储结构类型名,左孩子指针,右孩子指针,数据域,双亲指针,28,为方便找到结点双亲，在二叉链表结构中增加一个指向其双亲结点的指针域，则表示二叉树的链表中的结点包括四个域：数据域、左指针域、右指针域和双亲指针域，称为三叉链表存储结构。,在二叉树的很多应用中，常要求在二叉树中查找某些指定的结点或对二叉树中全部结点逐一进行某种操作，这就需要依次访问二叉树中的结点，即遍历二叉树。,6.4 遍历二叉树,29,遍历
15、二叉树 (traversing binary tree) 是指按某种规律巡查二叉树，对树中的每个结点访问一次且仅访问一次。在访问每个结点时可对结点进行各种操作，如：输出结点的信息、对结点进行计数、修改结点的信息等。,遍历二叉树的操作定义,30,遍历二叉树的递归算法,遍历二叉树的非递归算法,建立二叉树的算法,二叉树的定义是递归的，一棵非空的二叉树由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。 设以 L、D、R 分别表示遍历左子树、访问根结点和遍历右子树，则可能有 DLR、LDR、LRD、DRL、RDL、RLD 六种遍历二叉树的方案。如果限定先左子树
16、后右子树，则只有前三种方案，分别称之为先根（序）遍历 DLR、中根（序）遍历 LDR 和后根（序）遍历 LRD。遍历左子树和右子树的规律和遍历整个二叉树的规律相同，因而这三种遍历都具有递归性。,31,6.3.1 遍历二叉树的操作定义,(1) 先根（序）DLR 遍历二叉树的操作定义,若二叉树为空，则空操作；否则： 访问根结点； 先序遍历左子树； 先序遍历右子树。,32,(2) 中根（序）LDR 遍历二叉树的操作定义,若二叉树为空，则空操作；否则： 中序遍历左子树； 访问根结点； 中序遍历右子树。,33,(3) 后根（序）LRD 遍历二叉树的操作定义,若二叉树为空，则空操作；否则： 后序遍历左子树； 后序遍历右子
