《fh第4单元非线性结构（一）.ppt》由会员分享，可在线阅读，更多相关《fh第4单元非线性结构（一）.ppt（41页珍藏版）》请在金锄头文库上搜索。
1、1 /41,第4单元 非线性结构(一）,第二章 2.12.4 节 树的基本概念和逻辑结构 二叉树的逻辑结构,存储结构 二叉树的遍历操作及有关算法 特殊二叉树的表示及性质 树、森林、二叉树的转换,2 /41,2.1 树的逻辑结构及其运算,一. 树的定义 1. 逻辑定义 数据结构：Tree=（D，R） 其中：D 具有相同数据类型的元素的集合； 关系R满足： 1) 存在唯一的元素没有前趋,称为根； 2) 其余元素都有且只有一个前趋； 3) 所有元素，或有若干个互不相同的后继，或无后继； 则称Tree为树。,3 /41,2. 树的递归定义 树是一个或多个结点组成的有限集合T，有一个特定结点称为根，其余
2、结点分为m（m0）个互不相交的集合T1，T2，,Tm。每个集合又是一棵树，被称为这个根的子树。,4 /41,3. 树结构举例,书目录 目录树 树结构 C1（章） BOOK S1.1(节) S1.2 C1 C2 C3 C2 S2.1 S1.1 S1.2 S2.1 S2.2 S2.3 S2.11 S2.12 S2.2 S2.1.1 S2.1.2 S2.3 C3,5 /41,4.树的一般表示形式,A,B,C,D,E,F,K,L,G,H,I,J,M,A,(a),(b),(a)只有根结点的树,(b)一般的树,6 /41,二. 基本术语（一）,结点的度 结点拥有的子树数；A的度为3。 根结点 无前趋的结点
3、；例如，A结点。 支结点 度不为0的结点；如B，C，D等。 叶结点 无后继的结点；如K，L，M。 子结点和父结点 兄弟结点 拥有同一父结点的结点之间互为兄弟结点 结点的层次 根结点层次为1,其它结点递增,7 /41,二.基本术语（二）,树的度 树中结点的最大度数；上述树的度为3。 有序树 结点的各子树看成从左至右有顺序且不能互换，则该树为有序树。否则为无序树。 路径 由结点序列组成. 长度 长度等于路径中结点数-1. 高度 从一结点到叶结点的最长路径为该结点的高度；例如，结点A到M的高度为4。 深度 从根结点到某结点的路径为该结点的深度；M的深度为4。 森林 0棵或多棵互不相交的树的集合。,8
4、 /41,三. 树的操作,1.setnull(T) 将T置为空树 2.ROOT(x) 求x所在树的根结点 3.PARENT(T,x） 树T中x结点的双亲； 4.CHILD(T,x,i）求T中结点x的第i个子结点。 5.ins_child(T,y,i,x) x作为T中y结点的第i个孩子 6.del_child(T,x,i) 删除结点x的第i个子树。 7.TRAVERSE(T） 遍历树T。按次序依次访问树中各个结点，且使每个结点只被访问一次。,9 /41,2.2 二叉树,一. 二叉树定义及运算 1. 定义 n个结点的集合（n0） T = 所有子树都有左、右之分,10 /41,2.二叉树的五种基本形
5、态,（a） （b） （c）,（d） （e）,O 空结点,O 单个结点,O,O,右子树为空 的二叉树,O,O,左子树为空 的二叉树,O,O,O,左、右子树 非空的二叉树,11 /41,3. 二叉树与树的区别,表达形式（对3个结点） 树 二叉树 （a） （b） （c） （d） （e）,O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,有五种不同形式,12 /41,二叉树与树的区别（二）,二叉树是一种特定的树结构，但不是普通树的特殊情况； 二叉树可以为空；而树不能为空； 非空二叉树是有序树,而树可以是有序或无序树。,13 /41,4.二叉树的性质,性质一 二叉树的第i层上至多有2i-1个结
6、点(i1) 性质二 深度为k的二叉树上最多含有2k-1个结点（k 1）。,14 /41,1,2,3,8,6,5,7,4,10,9,11,12,13,14,15,第3层有23-1 个结点. 深度为4,则最多有24 -1 个结点.,15 /41,5. 二叉树的基本运算,1.setnull(BT) 将二叉树BT置空 2.root(x) x所在二叉树的根 3.parent(BT,x） x结点的双亲 4.lchild(BT,x） 求x左孩子结点 rchild(BT,x) 求x右孩子结点 5.ins_lchild(BT,x,y) y置为x的左孩子 ins_rchild(BT,x,y) y置为x的右孩子 6
7、.del_lchild(BT,x) 删除 x的左子树 del_rchild(BT,x) 删除 x的右子树 7.TRAVERSE(BT） 遍历树T,16 /41,二. 二叉树的链式结构,data,leftp,rightp,左指针 数据 右指针,A,B,C,D,E,F,G,A,B,D,C,E,F,G,NULL,特点: 找子易, 找父难.,1. 二叉链表,NULL,NULL,17 /41,二. 二叉树的链式结构(续),parent,data,rightp,左指针 数据 父结点 右指针,A,B,C,D,E,F,G,C,特点: 找子、找父都易,leftp,A,B,D,E,G,F,2. 三叉链表,18 /
8、41,三.特殊二叉树-满二叉树,1. 满二叉树 若深度为k的二叉树T中共有2k-1个结点(k1),则称T为满二叉树。 （a）满二叉树 （b）非满二叉树,O,O,O,O,O,O,O,O,O,O,O,O,O,19 /41,三.特殊二叉树-满二叉树,满二叉树的性质 对满二叉树从第1层开始,自上而下、从左至右对每个结点由1开始编号，则深度为k的满二叉树结点编号i(1i2k-1-1),满足以下关系： 1) i的左子树根编号为2*i，右子树根编号为 2*i+1 2) i的父结点编号为int(i/2) 应用: 用一维数组存储满二叉数的结点,由一个结点的编号，计算出左、右子树的根及父结点的编号,20 /41,
9、满二叉树存储举例,1,4,3,2,5,7,6,1 2 3 4 5 6 7,1 2 3 4 5 6 7,第i个结点存放在第i个位置； 第i个结点的父结点在第 i/2个位置; 第i个结点的左子结点就存放在 第2*i的个位置;右子存放在第2*i+1位置.,21 /41,三.特殊二叉树-完全二叉树,深度为k的二叉树T,每层结点数目若满足: 第i层(1ik-1)的结点个数均为2i-1 第k层从右边连续缺若干个结点 这样的树称为完全二叉树。 特点: 叶结点只能出现在层次最大的两层上. （a）完全二叉树 （b） 非完全二叉树,O,O,O,O,O,O,O,O,O,O,O,22 /41,完全二叉树的性质,设完全
10、二叉树的结点总数为n，深度为k，某结点编号为i(1ik-1),则有： 1) 若i1,则i的双亲结点编号为int(i/2) 2) 若2*in,则i的左子结点的编号为2*i,否则 i为叶结点; 3) 若2*i+1n,则i 的右子结点的编号为2*i+1,否则,i为叶结点. 完全二叉树也可以采用一维树组作为存储结构,且方法完全同满二叉树.,23 /41,三.特殊二叉树-平衡二叉树,1.平衡因子: 二叉树上任一结点的左子树深度减去右子树深度的差值。 2.平衡二叉树: 二叉树中,每个结点的平衡因子的绝对值都不大于1。 （a）平衡二叉树 （b）非平衡二叉树,O,O,O,O,O,O,O,O,O,O,O,O,O
11、,O,O,O,24 /41,三.特殊二叉树-二叉排序树,定义: 或者是空二叉树； 或者是： 左子树上所有结点的值均小于根结点的值； 右子树上所有结点的值均大于等于根结点的值； 左、右子树本身又是一棵二叉排序树。,25 /41,二叉排序树例题,例(P65) 有7个元素的序列: 10,18,3,3,9,13,25 试根据算法的基本思想构造一棵二叉排序树 a）二叉排序树 b）非二叉排序树,10,5,7,12,14,18,15,15,14,18,5,10,12,13,7,26 /41,四.二叉树的遍历,1. 遍历: 按一定次序访问树结构中的所有结点，且每个结点只被访问一次。 2. 遍历方法 先序遍历
12、中序遍历 后序遍历,27 /41,先序遍历,方法：根-左-右 1) 访问根结点 2) 先序遍历左子树 3) 先序遍历右子树,根,左子树,右子树,a,b,c,28 /41,中序遍历,方法：左-根-右 1) 中序遍历左子树 2) 访问根结点 3) 中序遍历右子树,根,左子树,右子树,a,b,c,29 /41,后序遍历,方法：左-右-根 1) 后序遍历左子树 2) 后序遍历右子树 3) 访问根结点,根,左子树,右子树,a,b,c,30 /41,二叉树的遍历举例,先序遍历序列： ABDEGCFHI 填空法: A( B(DE(G) ) C(F(HI) 中序遍历序列：DBGEACHFI 投影法 后序遍历序
13、列：DGEBHIFCA 填空法: (DGEB)(HIFC)A,31 /41,遍历序列的特性: 由同一棵树先序和中序遍历可构造唯一的二叉树 由同一棵树后序和中序遍历可构造唯一的二叉树 例: P69,已知一棵二叉树的先序遍历和中序遍历序列,构造此二叉树,32 /41,二叉树遍历算法,二叉树遍历方法： 递归算法 非递归算法 递归算法和非递归算法中又分： 先序法 中序法 后序法,33 /41,二叉树遍历算法（递归算法）,二叉链表的C语言描述： struct tnode int data； struct tnode *lc,*rc ; ； typedef struct tnode TNODE;,34 /
14、41,二叉树遍历算法（前序法递归程序）,void preorder_t(TNODE *root) if ( root != NULL ) printf(“%d n”,root-data); if (root-lc!=NULL) preorder_t(root-lc); if (root-rc!=NULL) preorder_t(root-rc); 前序遍历序列为： A B C D E F,A,B,C,D,E,F,35 /41,2.3 树类的存储结构,双亲表示: 数组实现 孩子表示: 链表实现 孩子兄弟表示: 二叉链表实现,36 /41,一. 双亲表示法,1,2,3,4,5,6,7,8,9,序号 结点 双亲,1 2 3 4 5 6 7 8 9,1 2 3 4 5 6 7 8 9,0 1 1 2 2 3 5 5 5,特点： 找双亲容易，找子结点难,存储数据元素结点同时存储双亲结点的位置,37 /41,二. 孩子表示法,1,2,3,4,5,6,7,8,9,1 2 3 4 5 6 7 8 9,2,3,NULL,4,5,NULL,6,NULL,NULL,7,8,9,NULL,特点: 便于实现对孩子的操作,不便于对父亲 的操作.,NULL,NULL,NULL,NULL,为每个结点的孩子建立一个链表,38 /41,三.孩子兄弟表
