数据结构 教学课件 晋良颖 5.pdfVIP

第五章 树与二叉树 第五章 树与二叉树 5 ．1树的定义及基本术语 5 ．1．1树的定义 图5.1 树的示例 退出 退出 图5.2 5 ．1．2基本术语 1、根 2、度（结点的度和树的度） 3、叶 4、分枝结点 5、双亲、子女、祖先、子孙 6、兄弟、堂兄弟 7、结点的层次、树的深度（高度） 8、有序树、无序树 9、森林 1．2二叉树 5 ．2 ．1二叉树的性质 (1) 在二叉树的第i上至多有2i-1个结点（i=1 ） (2) 深度为k的二叉树至多有2k-1个结点。 (3) 设任何一棵二叉树中，叶结点数为n0，度为1 的结 点数为n1,度为2 的结点数为n2，则有：n0=n2+1 (4) 具有n个结点的完全二叉树其深度为：k= [log2n]+1 （[]应改为底函数） （5 ）对于具有n个结点的完全二叉树有如下特点： ①i=1则是树根，若i1则它的双亲为i/2(取整) ； ②如果2in 则 i没有左子女，否则它的左子女为2i ； ③如果2i+1n 则 i没有右子女，否则它的右子女为 2i+1 ； 图5-3 5 ．2 ．2 二叉树的存储结构 1、顺序存储 顺序存储的二叉树的定义如下： #define N 50 /*树结点的最大个数*/ typedef elemtype SQTREE[N]; 图5-4 1、链式存储 图5-5 图 5-6 一般二叉树的两种结点类型定义如下： typedef struct treenode { elemtype data; /*树中结点的数据值。可根据需要 替换元素类型elemtype*/ struct treenode *lchild, *rchild; /*指向树结点 的左、右孩子指针*/ } TREENODE, * TREENODEPTR ; /* 二叉树 的二叉链表结点类型*/ typedef struct treenode { elemtype data; /*树中结点的数据值。可根据需要 替换元素类型elemtype*/ struct treenode *lchild, *rchild ，*parent; /*指向树结点的左、右孩子指针和双亲指 针*/ } PTREENODE, *PTREENODEPTR; /*二叉树的三 叉链表结点和指针类型*/ 1、按层次顺序为输入，建立二叉树的三叉链表的算 法 图 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值， 每输入一个结点值时，同时输入它按完全树编号方 法所编的序号。 i 1 2 3 4 5 6 7 9 11 18 19 Value 8 5 10 1 6 9 11 3 7 2 4 表5.1 算法 5.2