《数据结构严蔚敏版第06章》由会员分享，可在线阅读，更多相关《数据结构严蔚敏版第06章（93页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第六章 树和二叉树 2019年1月16日星期三,6.1 树的类型定义,数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D为空集，则称为空树； 否则: （1）在D中存在唯一的称为根的数据元素root, （2）当n1时，其余结点可分为m(m0)个互不相交的有限集 T1, T2, , Tm, 其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。 基本操作： 查找： Root(T); Value(T, cur_e); Parent(T, cur_e); LeftChild(T, cur_e); TreeEmpty(T); TreeDepth(T); Travers
2、eTree(T, Visit( );,6.1 树的类型定义,插入： InitTree(,6.1 树的类型定义,和线性结构的比较,A (B (E (K, L), F), C(G ), D( H( M), I, J) 嵌套括号表示法,树的表示方法：,基本术语,结点: 数据元素 + 若干指向子树的分支。 结点的度: 分支的个数。 树的度: 树中所有结点的度的最大值。 叶子结点: 度为零的结点。 分支结点: 度大于零的结点； 路径和路径长度。 孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点。 边：双亲节点x到子结点y的有序对(x，y)。 结点的层次: 假设根结点的层次为1，第i 层的结点的子
3、树根结点的层次为i+1。规定根的层数为0。 树的深度：树中叶子结点所在的最大层次。 森林：是m（m0）棵互不相交的树的集合任何一棵非空树是一个二元组 Tree = （root，F）其中：root被称为根结点，F被称为子树森林。,6.2 二叉树的类型定义,二叉树的定义,定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 与树的关系：这也是一个递归定义。 区别： 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。,二叉树的5种基本形态,二叉树的主要基本操作：,查找：
4、 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); 插入： InitBiTree(,性质1： 在二叉树的第i层上至多有2i-1个结
5、点(i=1)。 证明：采用归纳法证明此性质。 当i=1时，只有一个根结点，2i-1=20 =1,命题成立。 现在假定第i1层上命题成立，则第i1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i1层上最大结点数的二倍， 即22i-22i-1。 命题得到证明。,二叉树的重要特性：,性质2：深度为k的二叉树至多有2k1个结点（k=1). 证明：深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数2i-1（第i层上的最大结点数）,二叉树的重要特性：,二叉树的重要特性：,性质3： 对任何一棵二叉树，如果其终端结点数为n0，度
6、为2的结点数为n2，则n0n21。 证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有： Nn0n1n2 （1） 再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数， 则有：NB1。由于这些分支都是由度为1和2的结点射出的，所以有：Bn1+2*n2 NB1n12n21 （2) 由式（1）和（2）得到： n0+n1+n2=n1+2*n2+1 n0n21,两种特殊形态的二叉树： 一棵深度为k且由2k-1个结点的二叉树称为满二叉树。 如果深度为k、由n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n
7、标号的结点相对应，则称这样的二叉树为完全二叉树。 完全二叉树的特点是： （1）所有的叶结点都出现在第k层或k1层。 （2）对任一结点，如果其右子树的最大层次为h，则其左子树的最大层次为h或h1。,满二叉树和完全二叉树,性质4：具有n个结点的完全二叉树的深度为log2n1。 符号x表示不大于x的最大整数。 证明：假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-11n=2k-1 或 2k-1=n2k 取对数得到：k1log2nk 因为k是整数。所以有：klog2n1。,二叉树的重要特性,性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n+1层，每层
8、从左到右),则对任一结点i（11，则其双亲是结点i/2。 （2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 （3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。 证明：略！,完全二叉树的特点:,6.3 二叉树的存储结构,1.顺序存储结构,它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法： #define max-tree-size 100 Typedef telemtype sqbitreemax-tree-size; Sqbitree b
9、t 从树根起，自上层至下层，每层自左至右的给所有结点编号。,完全二叉树, 表示该处没有元素存在仅仅为了好理解,一般二叉树,1.顺序存储结构,缺点：有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！,1.顺序存储结构,（2）二叉链表法,Typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;,2）二叉链表法,二叉树的二叉链表存储表示,Status Creat
10、eBiTree(BiTree *T) /*创建一棵二叉树*/ scanf( ,6.3 二叉树的存储结构,链式存储结构的算法：,三叉链表法,Typedef struct TBiTNode TelemType data; struct TBiTNode *lchild,*rchild,*parent; BiTNode,*BiTree;,三叉链表法,二叉树的三叉链表存储表示,6.4 二叉树的遍历,一、问题的提出,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结点的信息等。 对“二叉树”而言，可以有三条搜索路径： 1先上后下的按层次
11、遍历； 2先左（子树）后右（子树）的遍历； 3先右（子树）后左（子树）的遍历。,6.4 二叉树的遍历,二、先左后右的遍历算法,先（根）序的遍历算法： 若二叉树为空树，则空操作；否则，（1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 中（根）序的遍历算法： 若二叉树为空树,则空操作；否则,（1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 后（根）序的遍历算法： 若二叉树为空树,则空操作;否则,（1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,6.4 二叉树的遍历,示例,先序：/-ab+cd 中序：a-b/c+d 后序：ab-cd+/,先序：-
12、a+/bcd 中序：a-b/c+d 后序：abc/d+-,先序：+-a/bcd 中序：a-b/c+d 后序：abc/-d+,分别称为表达式的前缀表示法、中缀表示法和后缀表示法（逆波兰表示法）。,6.4 二叉树的遍历,三、算法的递归描述,void Preorder (BiTree T, void( *visit)(TElemType / 遍历右子树 ,void InOrderTraverse (BiTree T, void( *visit)(TElemType / 访问结点 ,四、先序遍历算法的非递归描述,先序遍历的非递归算法。t指向根，p为指针，指向当前结点。使用一个堆栈s（），top为栈指针
13、 1 if t=NULL 2 then 输出 这是一棵空树 3 else p=t，top=0 4 DO 5 while p！=NULL 6 输出 data（p）; 7 top+; 8 if topn 9 then 调用 栈满 10 else stop=p，p=lchild（p） 11 if top！=0 12 p=stop; top-; p=rchild（p） 13 while( top=0 & p=null) 算法结束,6.4 二叉树的遍历,四、先序遍历算法的非递归描述,1 if t=NULL 2 then 输出 这是一棵空树 3 else p=t，top=0 4 DO 5 while p！
14、=NULL 6 输出 data（p）; 7 top+; 8 if topn 9 then 调用 栈满 10 else stop=p，p=lchild（p） 11 if top！=0 12 p=stop; top-; p=rchild（p） 13 while( top=0 & p=null) 算法结束,中序遍历的非递归算法,中序遍历的非递归算法，使用堆栈s（），top为指针，t指向根，p为指针，指向当前结点 1 top=0,p=t 2 DO 3 while ( p!=NIL ) 4 top+ 5 if (topn ) 6 then 调用 栈满 7 else stop=p; p=Lchild(p) 8 if top!=0 9 then p=stop, top- 10 输出 data(p) 11 p-rchild(p) 12 while (top=0 算法结束,1 top=0,p=t 2 DO 3 while ( p!=NIL ) 4 top+ 5 if (topn ) 6 then 调用 栈满 7 else stop=p; p=Lchild(p) 8 if top!=0 9 then p=stop, top- 10 输出 data(p) 11 p-rchild(p) 12 while (top=0 ,五、遍历算法的应
