《数据结构课件C 版第 六章》由会员分享，可在线阅读，更多相关《数据结构课件C 版第 六章（69页珍藏版）》请在金锄头文库上搜索。
1、2019/7/13,mayan,第六章 树,树 二叉树 线索二叉树 树与森林 Huffman树,2019/7/13,mayan,树 -树的定义和术语,树：一棵树 T，简称为树，它是n (n0) 个结点的有限集合。当n = 0时，T 称为空树；否则，T 是非空树，记作 其中，r 是一个特定的称为根(root)的结点，它没有直接前驱；根以外的其他结点划分为 m (m 0) 个互不相交的有限集合T1, T2, , Tm，每个集合又是一棵树，并且称之为根的子树。,2019/7/13,mayan,树 -树的定义和术语,相关术语 子女：若结点的子树非空，结点子树的根即为该结点的子女。 双亲：若结点有子女，
2、该结点是子女双亲。 兄弟：同一结点的子女互称为兄弟。 度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。 分支结点：度不为0的结点即为分支结点，亦称为非终端结点。,2019/7/13,mayan,树 -树的定义和术语,叶结点：度为0的结点即为叶结点，亦称为终端结点。 祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。 子孙：某结点的所有下属结点，都是该结点的子孙。 结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以此类推。 深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。,2019/7/13,mayan,树 -树的定义和术语,高度：规
3、定叶结点的高度为1，其双亲结点的高度等于它的高度加一。 树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。 有序树：树中结点的各棵子树 T0, T1, 是有次序的，即为有序树。 无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。 森林：森林是m（m0）棵树的集合。,2019/7/13,mayan,树 -树的抽象数据类型,教材 p118-120,2019/7/13,mayan,二叉树 -二叉树的定义,一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,2019/7/13,mayan,二叉树 -二叉
4、树的性质,性质1 若二叉树结点的层次从 1 开始, 则在二叉树的第 i (i1)层最多有 2i-1 个结点。 证明用数学归纳法 性质2 深度为 k (k0) 的二叉树最少有 k 个结点，最多有 2k-1个结点。 证明：因为每一层最少要有1个结点，因此，最少结点数为 k。最多结点个数借助性质1用求等比级数前k项和的公式20 +21 +22 + +2k-1 = 2k-1,2019/7/13,mayan,二叉树 -二叉树的性质,性质3 对任何一棵二叉树，如果其叶结点有 n0 个, 度为 2 的非叶结点有 n2 个, 则有 n0n21 证明：若设度为 1 的结点有 n1 个，总结点数为n，总边数为e，
5、则根据二叉树的定义， n = n0+n1+n2 , e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1则 n2 = n0-1 n0 = n2+1,2019/7/13,mayan,二叉树 -二叉树的性质,定义1 满二叉树 (Full Binary Tree) ：深度为k的满二叉树是有2k-1个结点的二叉树。 定义2 完全二叉树 (Complete Binary Tree)：若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1k-1) 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。,2019/7/13,mayan,二叉树
6、-二叉树的性质,性质4 具有 n (n0) 个结点的完全二叉树的深度为 log2(n+1)。 证明： 设完全二叉树的深度为k，则有2k-1-1 n 2k-1 即 2k-1 n+12k ，取对数 k-1 log2(n+1) k 有 k= log2(n+1),2019/7/13,mayan,二叉树 -二叉树的性质,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, , n，则有以下关系： 若i = 1, 则 i 无双亲； 若i 1, 则 i 的双亲为i2； 若2*i = n, 则 i 的左子女为 2*i； 若2*i+1 = n, 则 i 的右子女为2*i+1；
7、若 i 为奇数, 且i != 1, 则其左兄弟为i-1； 若 i 为偶数, 且i != n, 则其右兄弟为i+1； 结点i 所在的层次为log2i+1,2019/7/13,mayan,二叉树 -二叉树的抽象数据类型,教材 P121-123,2019/7/13,mayan,二叉树 -二叉树的数组存储表示,教材p126定义,2019/7/13,mayan,二叉树 -二叉树的链表存储表示,二叉链表和三叉链表的概念 二叉树结点定义：每个结点有3个域，data域存储结点数据，lchild和rchild分别存放指向左子女和右子女的指针。 二叉链表如下图所示：,2019/7/13,mayan,二叉树 -二叉
8、树的链表存储表示,每个结点增加一个指向双亲的指针parent，使得查找双亲也很方便。,2019/7/13,mayan,二叉树 -二叉树的链表存储表示,整个二叉树的链表有一个表头指针，他指向二叉树的根结点。 在含有n个结点的二叉链表中有n+1个空链指针域，三叉链表则有n+2个空链指针域。 2n-(n-1)=n+1 n+1+1=n+2,2019/7/13,mayan,二叉树 -二叉树的链表存储表示,二叉树的链表表示,2019/7/13,mayan,二叉树 -二叉树的二叉链表存储表示,二叉树的二叉链表存储表示 typedef struct BiTNode TElemType data; struct
9、 BiTNode *lchild, *rchild;/ 左、右孩子指针 BiTNode, *BiTree; 二叉树的三叉链表存储表示 typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;,基于二叉树的二叉链表存储表示的基本操作的函数原形见教材p127,2019/7/13,mayan,二叉树 -二叉树的遍历,二叉树的遍历（Binary Tree Traversal）就是按
10、某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。“访问”的意思是对结点施行某些操作。 令L、R、D分别代表遍历一个结点的左子树、右子树和访问该结点的操作，则可能有DLR, LDR,LRD,DRL,RDL,RLD六种遍历二叉树的规则，若规定先左后右则有DLR（前序遍历）、 LDR（中序遍历）、 LRD（后序遍历）三种。,2019/7/13,mayan,二叉树 -二叉树的遍历,三种遍历算法： 先序遍历：访问根结点；先序遍历左子树；先序遍历右子树。 中序遍历：中序遍历左子树；访问根结点；中序遍历右子树。 后序遍历：后序遍历左子树；后序遍历右子树；访问根结点。,2019/7/13,mayan
11、,二叉树 -二叉树的遍历,Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) / 算法6.1.采用二叉链表存储结构，Visit是对数据元 /素操作的应用函数，先序遍历二叉树T的递归算 / 法，对每个数据元素调用函数Visit。 / 最简单的Visit函数是： / Status PrintElement( ElemType e ) / 输出元素e的值 / printf( e ); / 实用时，加上格式串 / return OK; / / 调用实例：PreOrderTraverse(T, PrintElement);,2019
12、/7/13,mayan,二叉树 -二叉树的遍历,if (T) if (Visit(T-data) if (PreOrderTraverse(T-lchild, Visit) if (PreOrderTraverse(T-rchild, Visit) return OK; return ERROR; else return OK; / PreOrderTraverse,2019/7/13,mayan,二叉树 -二叉树的遍历,中序遍历二叉树T的非递归算法 Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.2.采用二叉链
13、表存储结构，Visit是对数据元 /素操作的应用函数。中序遍历二叉树T的非递归算 /法，对每个数据元素调用函数Visit。,2019/7/13,mayan,二叉树 -二叉树的遍历,InitStack(S); Push(S, T); / 根指针进栈 while (!StackEmpty(S) while (GetTop(S, p) / InOrderTraverse,2019/7/13,mayan,二叉树 -二叉树的遍历,中序遍历二叉树T的非递归算法 Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.3.采用二叉链表
14、存储结构，Visit是对数据 /元素操作的应用函数。中序遍历二叉树T的非递归 /算法，对每个数据元素调用函数Visit。,2019/7/13,mayan,二叉树 -二叉树的遍历,InitStack(S); p = T; while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lchild; else Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InOrderTraverse,2019/7/13,mayan,二叉树 -以递归方式建立二叉树,BiTree
15、CreateBiTree(BiTree &T) / 算法6.4 / 按先序次序输入二叉树中结点的值（一个字 /符），#字符表示空树，构造二叉链表表示的二 /叉树T。,2019/7/13,mayan,二叉树 -以递归方式建立二叉树,char ch; scanf(“%c“, / CreateBiTree,2019/7/13,mayan,二叉树,例1：给定一棵二叉树的先序序列EBADCFHGIKJ和中序序列ABCDEFGHIJK，画出这颗二叉树。,2019/7/13,mayan,二叉树,例2：给定一棵二叉树的中序序列DCBGEAHFIJK和后序序列DCEGBFHKJIA，画出这颗二叉树。,2019/7/13,mayan,二叉树,例3：给定一棵二叉树的先序和后序序列不能确定一棵二叉树。,2019/7/13,mayan,线索二叉树 -线索二叉树的概念,为什么提出线索二叉树？ 遍历的过程实质上是对一个非线性结构进行线性化的操作，使每个结点（除第一个和最后一个）在这个线性序列中有且仅有一个直接前驱和直接后继。二叉树中只存储了左右孩子的信息，因此，前驱和后继的信息无法直接找到。就提出了线索二叉树的概念。 又因为n个结点的二叉链表中有n+1个空链域，
