第4单元非线性结构（一）精品

《第4单元非线性结构（一）精品》由会员分享，可在线阅读，更多相关《第4单元非线性结构（一）精品（41页珍藏版）》请在金锄头文库上搜索。

1、第4单元 非线性结构(一）l第二章 2.12.4 节 树的基本概念和逻辑结构 二叉树的逻辑结构,存储结构 二叉树的遍历操作及有关算法 特殊二叉树的表示及性质 树、森林、二叉树的转换12.1 树的逻辑结构及其运算l一. 树的定义l1. 逻辑定义 数据结构：Tree=（D，R） 其中：D 具有相同数据类型的元素的集合； 关系R满足：1) 存在唯一的元素没有前趋,称为根；2) 其余元素都有且只有一个前趋；3) 所有元素，或有若干个互不相同的后继 ，或无后继；则称Tree为树。2l2. 树的递归定义l 树是一个或多个结点组成的有限集 合T，有一个特定结点称为根，其余 结点分为m（m0）个互不相交的集

2、合T1，T2，,Tm。每个集合又是一 棵树，被称为这个根的子树。33. 树结构举例l 书目录 目录树 树结构 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 C344.树的一般表示形式ABCDEFKLGHIJMA(a)(b)(a)只有根结点的树(b)一般的树5二. 基本术语（一）l结点的度 结点拥有的子树数；A的度为3。l根结点 无前趋的结点；例如，A结点。l支结点 度不为0的结点；如B，C，D等。l叶结点 无后继的结点；如K，L，M。l子

3、结点和父结点l兄弟结点 拥有同一父结点的结点之间互为 兄弟结点l结点的层次 根结点层次为1,其它结点递增6二.基本术语（二）l树的度 树中结点的最大度数；上述树的度为3 。l有序树 结点的各子树看成从左至右有顺序且 不能互换，则该树为有序树。否则为无序树。l路径 由结点序列组成.l长度 长度等于路径中结点数-1.l高度 从一结点到叶结点的最长路径为该结点 的高度；例如，结点A到M的高度为4。l深度 从根结点到某结点的路径为该结点的深 度；M的深度为4。l森林 0棵或多棵互不相交的树的集合。7三. 树的操作l1.setnull(T) 将T置为空树l2.ROOT(x) 求x所在树的根结点l3.PA

4、RENT(T,x） 树T中x结点的双亲；l4.CHILD(T,x,i）求T中结点x的第i个子结点 。l5.ins_child(T,y,i,x) x作为T中y结点的第i 个孩子l6.del_child(T,x,i) 删除结点x的第i个子树 。l7.TRAVERSE(T） 遍历树T。按次序依次访问 树中各个结点，且使每个结点只被访问一次 。82.2 二叉树l一. 二叉树定义及运算l1. 定义n个结点的集合（n0）T =所有子树都有左、右之分92.二叉树的五种基本形态（a）（b）（c）（d）（e）O 空结点O 单个结点OO右子树为空 的二叉树OO左子树为空的二叉树OOO左、右子树 非空的二叉 树10

5、3. 二叉树与树的区别l表达形式（对3个结点）l树l二叉树 （a） （b） （c） （d） （e） 有两种不同形式OOO（a）OOOO O OO O OOOOO OO有五种不同形式OOO（b）11二叉树与树的区别（二）l二叉树是一种特定的树结构，但不是 普通树的特殊情况；l二叉树可以为空；而树不能为空；l非空二叉树是有序树,而树可以是有序 或无序树。124.二叉树的性质l性质一二叉树的第i层上至多有2i-1个结点 (i1)l性质二 深度为k的二叉树上最多含有2k-1个 结点（k 1）。131 238657410911 121314 15第3层有23-1 个结点.深度为4,则最多有24 -1 个

6、结点.145. 二叉树的基本运算l1.setnull(BT) 将二叉树BT置空l2.root(x) x所在二叉树的根l3.parent(BT,x） x结点的双亲l4.lchild(BT,x） 求x左孩子结点l rchild(BT,x) 求x右孩子结点l5.ins_lchild(BT,x,y) y置为x的左孩子l ins_rchild(BT,x,y) y置为x的右孩子l6.del_lchild(BT,x) 删除 x的左子树l del_rchild(BT,x) 删除 x的右子树l7.TRAVERSE(BT） 遍历树T15二. 二叉树的链式结构data leftprightp左指针 数据 右指针AB

7、CDEFGABDCEFGNULL特点: 找子易, 找父难 .1. 二叉链表NULLNULL16二. 二叉树的链式结构(续)parent datarightp左指针 数据 父结点 右指针ABCDEFGC特点: 找子、找父都 易leftpABDEGF2. 三叉链表17三.特殊二叉树-满二叉树 l1. 满二叉树l若深度为k的二叉树T中共有2k-1个 结点(k1),则称T为满二叉树。（a）满二叉树 （b）非满二叉树 OOOO O OOOO OOOO18三.特殊二叉树-满二叉树l满二叉树的性质l对满二叉树从第1层开始,自上而下、从左 至右对每个结点由1开始编号，则深度为k 的满二叉树结点编号i(1i2k

8、-1-1),满足 以下关系： 1) i的左子树根编号为2*i，右子树根编 号为 2*i+1 2) i的父结点编号为int(i/2)l应用: 用一维数组存储满二叉数的结点,由 一个结点的编号，计算出左、右子树的根 及父结点的编号19满二叉树存储举例14325761 2 3 4 5 6 71 2 3 4 5 6 7第i个结点存放在第i个位置； 第i个结点的父结点在第 i/2个位置; 第i个结点的左子结点就存放在 第2*i的 个位置;右子存放在第2*i+1位置.20三.特殊二叉树-完全二叉树l深度为k的二叉树T,每层结点数目若满足: 第i层(1ik-1)的结点个数均为2i-1 第k层从右边连续缺若干

9、个结点这样的树称为完全二叉树。l特点: 叶结点只能出现在层次最大的两层上. l （a）完全二叉树 （b） 非完全二叉树O OO OOOOOOOO21完全二叉树的性质l设完全二叉树的结点总数为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为叶结点.l完全二叉树也可以采用一维树组作为存储结构 ,且方法完全同满二叉树.22三.特殊二叉树-平衡二叉树l1.平衡因子: 二叉树上任一结点的左 子树深度减去右子树

10、深度的差值。l2.平衡二叉树: 二叉树中,每个结点的 平衡因子的绝对值都不大于1。l（a）平衡二叉树 （b）非平衡二 叉树O OOOOO O O OO OO O OO O23三.特殊二叉树-二叉排序树l定义: 或者是空二叉树； 或者是： 左子树上所有结点的值均小于根结 点的值； 右子树上所有结点的值均大于等于 根结点的值； 左、右子树本身又是一棵二叉排 序树。 24二叉排序树例题l例(P65) 有7个元素的序列: l 10,18,3,3,9,13,25l试根据算法的基本思想构造一棵二叉 排序树la）二叉排序树 b）非二叉排序树1057121418151514185 101213725四.二叉树

11、的遍历l1. 遍历: 按一定次序访问树结构 中的所有结点，且每个结点只被 访问一次。l2. 遍历方法 先序遍历 中序遍历 后序遍历26先序遍历l方法：根-左-右 1) 访问根结点 2) 先序遍历左子树 3) 先序遍历右子树 根左子树右子树abc27中序遍历l方法：左-根-右 1) 中序遍历左子树 2) 访问根结点 3) 中序遍历右子树根左子树右子树abc28后序遍历l方法：左-右-根 1) 后序遍历左子树 2) 后序遍历右子树 3) 访问根结点根左子树右子树abc29二叉树的遍历举例oooooooEoCFoABDGHI先序遍历序列： ABDEGCFHI 填空法: A( B(DE(G) ) C(

12、F(HI) 中序遍历序列：DBGEACHFI 投影法后序遍历序列：DGEBHIFCA 填空法: (DGEB)(HIFC)A30l遍历序列的特性: 由同一棵树先序和中序遍历可构造唯一 的二叉树 由同一棵树后序和中序遍历可构造唯一 的二叉树l例: P69,已知一棵二叉树的先序遍历 和中序遍历序列,构造此二叉树31二叉树遍历算法l二叉树遍历方法： 递归算法 非递归算法l递归算法和非递归算法中又分 ： 先序法 中序法 后序法32二叉树遍历算法（递归算法）l二叉链表的C语言描述：struct tnode int data；struct tnode *lc,*rc ; ；typedef struct tn

13、ode TNODE;33二叉树遍历算法（前序法递归程序）lvoid 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 FABCDEF342.3 树类的存储结构l双亲表示: 数组实现l孩子表示: 链表实现l孩子兄弟表示: 二叉链表实现35一. 双亲表示法123456789序号结点双亲1 2 3 4 5 6 7 8 91

14、 2 3 4 5 6 7 8 90 1 1 2 2 3 5 5 5特点： 找双亲容易，找子结点难存储数据元素结点同时存储 双亲结点的位置36二. 孩子表示法1234567891 2 3 4 5 6 7 8 923NULL45NULL 6NULL NULL 789NULL特点: 便于实现对孩子的操 作,不便于对父亲 的操作.NULLNULL NULL NULL为每个结点的孩子 建立一个链表37三.孩子兄弟表示法12345678912NULL374 5 68 9左子女右 兄弟表示382.4 树、森林转换成二叉树l一. 树转换成二叉树 加线: 连接兄弟结点； 抹线:保留一个结点的最左子结点, 抹掉其余兄弟结点与上级结点连线 ； 以根为轴，顺时针旋转加线oooooooo o oooooooooooo抹线 旋转oooooo o39二. 森林转换成二叉树l将森林中每棵树的树根连接起来；l将每棵树转换成对应的二叉树；l以第一棵树的根为轴顺时针旋转 ooooooo o o