《数据结构二叉树和树第一节ppt课件》由会员分享，可在线阅读，更多相关《数据结构二叉树和树第一节ppt课件（12页珍藏版）》请在金锄头文库上搜索。
1、第6章 二叉树和树 6.1二叉树 6.1.1 二叉树的定义和术语6.1.2 二叉树的基本性质6.1.3 二叉树的存储结构 6.2二叉树遍历6.2.1问题的提出6.2.2遍历算法的描述6.2.2二叉树遍历应用举例6.2.4线索二叉树 6.3树和森林6.3.1 树和森林的定义6.3.2 树和森林的存储结构6.3.3 树和森林的遍历 6.4树的应用6.4.1 堆排序 6.4.2 二叉排序树 6.4.3 赫夫曼树及其应用,二叉树: 是n(n=0)个数据元素的有限集。它或为空集(n=0)，或为非空集。对于非空集有：,6.1.1二叉树的定义和基本术语,（1）有一个特定的称之为根的元素； （2）除根以外的其
2、余元素分为两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。,（1）集合为空的二叉树简称为空树 （2）二叉树中的数据元素也称为结点 （3）除了根结点外，每个结点有且仅有一个直接前驱，但有零个或多个直接后继。,注意:,注意(1)二叉树中的左子树和右子树是两棵互不相交的二叉树，二叉树上任何结点不可能同时在两棵子树中出现，或者在左子树中，或者在右子树中。(2)二叉树上每个结点至多只有两棵子树，并且，二叉树的两棵子树有左右之分，其次序不能任意颠倒。,二叉树的五种基本形态,N,空树,只含根结点,右子树为空树,左子树为空树,左右子树均不为空树,二叉树的结构定义 根结点 左子树 右
3、子树 孩子结点 双亲结点 兄弟结点 结点的祖先 结点的子孙 叶子结点（终端结点） 非叶子结点（分支结点） 结点在二叉树中的层次 二叉树的深度 结点的度 树的度 宽度 满二叉树 完全二叉树,叉 树 基 本 术 语,6.1.1二叉树的定义和基本术语,两种特殊形态的二叉树,1.满二叉树,若二叉树中所有的分支结点的度都为2，且叶子结点都在同一层次上,对一棵包含n个结点的二叉树中每个结点，都可以和满二叉树中编号为1至n的结点一一对应,2.完全二叉树,特点,（1）若某结点没有左孩子，则它一定没有右孩子；即该结点必是叶子结点。 （2）一棵深度为h的完全二叉树中，前h-1层中的结点都是“满”的。且第h层的结点
4、都集中在左边。 （3）满二叉树本身也是完全二叉树。,性质1:在二叉树的第i层上至多有2i-1 个结点。 性质2:深度为 k 的二叉树上至多含 2k-1 个结点。 性质3:对任何一棵二叉树T，若它含有n0 个叶子结点（0度节点）、n2个度为 2 的结点，则必有:n0=n2+1。 性质4:具有n个结点的完全二叉树的深度为 log2n +1 。,6.1.2二叉树的重要性质,若i=1，则该结点是二叉树的根，无双亲，若i1, 编号为 i/2 的结点为其双亲结点； 若2in，则该结点无左孩子(结点i为叶子结点)，否则编号为 2i 的结点为其左孩子结点； 若2i+1n，则该结点无右孩子结点，否则编号为2i+
5、1 的结点为其右孩子结点。,6.1.2二叉树的重要性质,性质 5:若对含 n 个结点的完全二叉树的结点按从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点(i=1且i=n)，有：,二叉树的顺序存储表示：用一组地址连续的存储单元存储数据元素，为了能在存储结构中反映结点之间的逻辑关系，必须将二叉树中的结点依照一定规律存放在存储单元中。两种树的存储方法：,6.1.3 二叉树的存储结构,结论：顺序存储表示方法只适用于完全二叉树。,1.完全二叉树：首先要对该树中每个结点进行编号，根据完全二叉树具有的特性（从1开始按层顺序编号），将完全二叉树上编号为i的结点元素存储在一
6、维数组中下标为i-1的存储单元中。 2.一般二叉树：可对照完全二叉树的编号进行相应的存储。其中对应编号没有结点的，对应存储单元中填充空白字符。,缺点：浪费空间。一个深度为k且只有k个结点的单支二叉树， 要占用2k-1个空间。,二叉树的顺序存储结构类型定义： const MAX=100 / 二叉树的最大结点数 typedef char TElemType ;/结点类型 TElemType SqBiTreeMAX; / 0号单元存储根结点,若地址从0编号，则第i号结点的左右孩子一定保存在第2(i +1)-1+及2(i+1)号单元中；其双亲保存在(i +1)/2-1 若地址从1编号，则第i号结点的左
7、右孩子一定保存在第2i 及2i+1号单元中；其双亲保存在i/ 2,二、二叉树的链式存储表示 1. 二叉链表：每个结点中设置三个域，数据域和分别指向左、右子树的指针域。2三叉链表：为了便于找结点的双亲，可在上述结点结构中增加一个指向其双亲的指针。,1. 二叉链表typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 2三叉链表 typedef struct TriTNode TElemType data; TriTNode *parent; TriTNode *lchild, *rchild; TriTNode, *TriTree;,
