DS树和叉树树和叉树的定义.ppt

6.2.1 二叉树(Binary Tree)的定义 研究二叉树的意义？ 问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。 二叉树的定义: 或者为空树；或者是由一个根结点加上两棵互不相交的、分别称为左子树和右子树的二叉树组成。 二叉树的特点： ⑴ 每个结点最多有两棵子树； (2) 子树有左右之分，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 完全二叉树的顺序存储 作业 独立完成五个性质的证明。 课件中的习题 预习树的遍历 Q：在有n个结点的满二叉树中，有多少个叶子结点？ 解： 因为在满二叉树中没有度为1的结点，只有度为0的叶子结点和度为2的分支结点，所以， n＝ n0 + n2，即n2＝n – n0 而由性质3知， n0＝n2 + 1 所以， n – n0 = n0 -1 即叶子结点数 n0＝（n + 1）/2 例 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（ ）个叶子结点。 【解答】12 【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。 分析分支数。 性质4：具有n个结点的完全二叉树的深度为 4 2 3 1 5 6 7 8 9 10 11 12 证明： 设完全二叉树的深度为h，则有 (2h-1 -1 ) n ? (2h -1) 或 2h-1 ? n 2h 两边取对数 h-1 log2(n+1) ? h 或 h-1 ? log2n h 即 log2(n+1) ?h log2(n+1)+1 或 log2n＜h ≤log2n+1 因为h是整数，所以h = 或 即 2h-1 n +1 ? 2h 或 2h-1 ? n 2h 性质5： 若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号(或者说采用顺序存储结构)，则对二叉树中任意一个编号为i的结点： (1) 若i=1，则i是根结点；若i≠1，双亲结点parent(i)的编号为 ； (2) 若2i≤n，左孩子leftchild(i)的编号为2i；若2in，则i无左孩子； (3) 若2i+1≤n，右孩子rightchild(i)的编号为2i+1；若2i+1n，则i无右孩子。 4 2 3 1 5 6 7 8 9 10 11 12 性质5：证明 结论(3)是结论(2)以及同一层的结点从左到右顺序编号的直接推论。 由结论(2)和结论(3)可得到结论(1)。 现在我们来证明结论(2)。 (2) 若2in，则i无左孩子；若2i≤n，左孩子leftchild(i)的编号为2i； 归纳法证明 对于i=1，显然其左孩子的编号为2；当n2，结点i没有左孩子，结论成立。 假设对于所有的j(1≤j ≤i)，其左孩子leftchild(j)的编号为2j； 那么，结点i+1的左孩子leftchild(i+1)应该紧随结点i的左孩子和右孩子之后，由于结点i的左孩子的编号是2i，因此，结点i+1的左孩子的编号是2i+2=2(i+1)。而且当n2(i+1)时，结点i+1没有左孩子。 1 8 9 10 4 5 6 7 2 3 1 8 9 10 4 5 6 7 2 3 对一棵具有n个结点的完全二叉树中所有结点从1开始按层序编号，则 结点i 的双亲结点为 i/2； 结点i 的左孩子为2i； 结点i 的右孩子为2i＋1。 性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。 完全二叉树的基本性质 第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 6.2.3 二叉树的存储结构 （1）二叉树的顺序存储表示 （2）二叉树的链式存储表示 Q:实现树的存储结构，关键是什么? Q:什么是存储结构? Q:树中结点之间的逻辑关系是什么? 思考问题的出发点：如何表示结点的双亲和孩子 如何表示树中结点之间的逻辑关系。 数据元素以及数据元素之间的逻辑关系在存储器中的表示。 1.二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点 SqBiTree bt; 按照顺序存储结构的定义，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为 i的结点元素存储