《数据结构 教学课件 ppt 作者 晋良颖 5》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 晋良颖 5（62页珍藏版）》请在金锄头文库上搜索。
1、第 五 章 树与二叉树 51树的定义及基本术语 511树的定义,退出,图5.1 树的示例,图5.2,512基本术语 1、根 2、度（结点的度和树的度） 3、叶 4、分枝结点 5、双亲、子女、祖先、子孙 6、兄弟、堂兄弟 7、结点的层次、树的深度（高度） 8、有序树、无序树 9、森林,12二叉树 521二叉树的性质 (1) 在二叉树的第i上至多有2i-1个结点（i=1） (2) 深度为k的二叉树至多有2k-1个结点。 (3) 设任何一棵二叉树中，叶结点数为n0，度为1 的结点数为n1,度为2的结点数为n2，则有：n0=n2+1 (4) 具有n个结点的完全二叉树其深度为：k= log2n+1 （应
2、改为底函数）,（5）对于具有n个结点的完全二叉树有如下特点： i=1则是树根，若i1则它的双亲为i/2(取整)； 如果2in 则 i没有左子女，否则它的左子女为2i； 如果2i+1n 则 i没有右子女，否则它的右子女为2i+1；,图5-3,522 二叉树的存储结构 1、顺序存储 顺序存储的二叉树的定义如下： #define N 50 /*树结点的最大个数*/ typedef elemtype SQTREEN;,图5-4,1、链式存储,图5-5,图 5-6,一般二叉树的两种结点类型定义如下： typedef struct treenode elemtype data; /*树中结点的数据值。可根
3、据需要替换元素类型elemtype*/ struct treenode *lchild, *rchild; /*指向树结点的左、右孩子指针*/ TREENODE, * TREENODEPTR ; /*二叉树的二叉链表结点类型*/,typedef struct treenode elemtype data; /*树中结点的数据值。可根据需要替换元素类型elemtype*/ struct treenode *lchild, *rchild ，*parent; /*指向树结点的左、右孩子指针和双亲指针*/ PTREENODE, *PTREENODEPTR; /*二叉树的三叉链表结点和指针类型*/,1
4、、按层次顺序为输入，建立二叉树的三叉链表的算法,图 5-7,（1）、输入按层次顺序并用0表示有关的指针为空。输入为： 8，5，10，1，6，9，11，0，3，0，7，0，0，0，0，2，4，0，0，0，0，0，0。 #define N 50 /*定义树中结点数目的上限，做队容量，设树中实际结点数为n*/ 算法 5.1 如书第110页所示,（2）、以层次顺序输入结点值，但不输入非0值，每输入一个结点值时，同时输入它按完全树编号方法所编的序号。,表5.1,算法 5.2 如书第111页所示,图 5-8 其广义表表示为：A（B（C（，D（E，F），G（，H），I（J，K） 算法 5.3 如书第113页
5、所示,53 遍历二叉树 如果以L代表左子树、D代表根，R代表右子树，则二叉树的遍历方案可以有： DLR、LDR、LRD和DRL、RDL、RLD六种 对于根来说，遍历只有三种情况,即前、中、后。若规定遍历子树的顺序为自左向右，则只有DLR、LDR、LRD三种。 531二叉树的遍历算法 1、 二叉树的LDR、DLR和LRD三种遍历的递归算法 (1)、中序遍历 算法 5.4 如书第114页所示,(2)、前序遍历 算法 5.5 如书第115页所示 (3)、后序遍历 算法 5.6 如书第115页所示 例如，对图5-7（a）所示的二叉树，三种遍历的结果为： 中序：1，2，3，4，5，6，7，8，9，10，
6、11； 前序：8，5，1，3，2，4，6，7，10，9，11； 后序：2，4，3，1，7，6，5，9，11，10，8。,2二叉树的LDR、DLR和LRD三种遍历的非递归算法 （1）、两种后序遍历算法 算法 5.7 如书第116页所示,算法 5.8 如书第117页所示,（2）、以二叉链表为存储结构的前序（及中序）遍历的非递归算法。 算法 5.9 如书第118页所示,3、二叉树的层次遍历 四种输出序列如下： （1）、8，5，10，1，6，9，11，3，7，2，4； （2）、2，4，3，7，1，6，9，11，5，10，8； （3）、8，5，10，11，9，6，1，3，7，4，2； （4）、4，2，3
7、，7，11，9，6，1，5，10，8； 算法 5.10 如书第119页所示,532二叉树遍历算法的应用 1、利用遍历的顺序作为输入建立二叉树 算法 5.11 如书第120页所示,图5.9 三个结点的二叉树的各种形态,1、棵二叉树的中序和前序（或后序）遍历输出顺序得到由它们唯一确定的二叉树。 算法5.12 如书第122页所示 int find( int key, int in, int i) /*在数组in中从下标i开始查找等于key的元素的下标*/ int i1,j; for (j=i; key!=inj; j+); i1=j; return i1; ,1、二叉树深度 算法 5.13 如书第1
8、22页所示,4、二叉树表示的算术表达式之值,图5.10 算法 5.14 如书第123页所示,5、求一棵二叉树的叶子结点个数、单枝结点个数并判断该树是不是一棵二叉排序树。 算法 5.15 如书第125页所示,一个由中辍表达式建立算术表达式树的算法 算法 5.16 如书第126页所示,54 线索二叉树（threaded binary tree）,图5-11,54 1二叉树的线索化算法 重新定义结点的类型如下： typedef struct treenode elemtype data; struct treenode *lchild, *rchild，* parent; int ltag, rta
9、g; /*0：表示孩子指针；1：表示前驱或后继*/ PTREENODE, *PTREENODEPTR; 算法 5.17 如书第130页所示,算法 5.18 如书第130页所示 void inorthrea(TREENODEPTR *thrt, TREENODEPTR t),54 2线索二叉树的有关操作 1、对中序线索链表进行非递归的中序遍历 算法 5.19 如书第131页所示 算法 5.20 如书第132页所示,1、对前序索链表进行非递归的前序遍历 算法 5.21 如书第132页所示,3、对某种遍历的线索二叉树中的任一结点，找 它在这种遍历（或其他遍历中）的前驱或后 继。 (1)、找建立了中序
10、线索的二叉树中某结点的 前序遍历的后继。,图5-12,算法 5.22 如书第133页所示,(2)、找建立了后序线索的二叉树中某结点的前驱和后继。,图5.13 一棵后序线索二叉树,算法 5.23 如书第134页所示,5.5二叉排序树（二叉查找树） 551二叉排序树的建立和插入,图5-14 一棵二叉排序树的插入生成过程,算法 5.24 如书第136页所示 算法 5.25 如书第137页所示,552二叉排序树的查找 算法 5.26 如书第138页所示,算法 5.27 如书第139页所示,553二叉排序树的删除,图5-15,图5.16 二叉排序树的删除双枝结点的示例,算法5.28 如书第141页所示,
11、554平衡二叉树的概念,图5.17 两棵不同形态的二叉排序树 ASL(a)=（1+2*2+3*4）/7=17/7； ASL(b)=（1+2+3+4+5+6+7）/7=28/7；,5.6树和森林 561树的存储结构 1、孩子表示法和孩子-双亲表示法,图5-18,1、双亲表示法,图5-19,1、树的二叉链表（孩子-兄弟）表示法 孩子-兄弟链表中结点的类型，可以定义如下： typedef struct csnode int data; /*可以替换为任何所需类型*/ struct csnode *firstchld, *nextsibling; /*最左孩子和右兄弟指针*/ CSNODE, *CSN
12、ODEPTR; 562树和森林与二叉树的转化 1、树与二叉树的转换,图5-20,2、森林与二叉树的转换 （1）、森林转化为二叉树,图5.21 森林转化为二叉树 （2）、由二叉树转化为森林 （3）、由二叉树表示的树再转换成树,563树和森林的遍历 1、树的层次遍历 2、树的前序遍历 #define M 5 /*树的最大可能度数*/ typedef struct cpnode char data; /*可以替换为任何所需类型*/ struct cpnode *ptrM,*parent; /*孩子指针和双亲指针*/ CPNODE, *CPNODEPTR; 算法5.29 如书第149页所示,1、树的后
13、序遍历 算法5.30 如书第150页所示,57哈夫曼树及其应用,图5-22 WPL(a)=（5+4+3+2）*3+1=43； WPL(b)=（1+2）*3+（3+4+5）*2=33； WPL(c)=（5+4）*4+3*3+2*2+1=50；,图5-23,图5-24,类型定义如下： typedef struct char ch; int weight; int lchild,rchild,parent; /*静态指针用下标表示，所以为整型。*/ HTNODE; /*哈夫曼树结点类型*/ typedef struct char *code; char leaf; CODE; /*叶的编码类型*/ 算法5.31 如书第155页所示,图5-25,
