[教育]CH6数据结构课件.ppt

线性结构 第一个数据元素 （无前驱） 最后一个数据元素 （无后继） 其它数据元素 （一个前驱、一个后继） 基 本 术 语 结点(node) ——表示树中的元素，包括数据元素及若干指向其子树的分支 结点的度(degree) ——结点拥有的子树数 树的度 —— 一棵树中最大的结点度数 叶子(leaf) ——度为0的结点（终端结点） 孩子(child) ——结点子树的根称为该结点的~~ 双亲(parents) ——孩子结点的上层结点叫该结点的~~ 兄弟(sibling) ——同一双亲的孩子 6.2 二叉树 定义：二叉树是n(n?0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 基本形态 二叉树性质 二叉树具有下列 5 个重要的性质。 【性质1】 在二叉树的第i层上最多有2i-1个结点（i ?1）； 证明： 二叉树的第1层只有一个根结点，所以，i = 1时，2i-1 = 21-1 = 20 = 1 成立。 假设对所有的j，1≤ji成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。 几种特殊形式的二叉树 满二叉树 定义：如果一个深度为K的二叉树拥有2K-1个结点，则将它称为 满二叉树。 特点：每一层上的结点数都是最大结点数。 【性质5】 对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i （1≤i≤n），都有： （1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲。否则其双亲结点的编号为 ?i/2?； （2）如果2in，则结点i没有左孩子。否则其左孩子结点的编号为2i； （3）如果2i+1n，则结点i没有右孩子。否则其右孩子结点的编号为2i+1。 由完全二叉树的结构可以看出：结点i+1或者与结点i同层且紧邻i结点的右侧，或者i位于某层的最右端，i+1位于下一层的最左端。 可以看出，i+1的左、右孩子紧邻在结点i的孩子后面，由于结点i 的左、右孩子编号分别为2i和2i+1，所以，结点i+1的左、右孩子编号分别为2i+2和2i+3，经提取公因式可以得到：2(i+1)和2(i+1)+1，即结点i+1的左孩子编号为2(i+1)；右孩子编号为2(i+1)+1。 又因为二叉树由n个结点组成，所以，当2(i+1)+1n，且2(i+1)=n时，结点i+1只有左孩子，而没有右孩子；当2(i+1)n，结点i+1既没有左孩子也没有右孩子。 以上证明得到（2）和（3）成立。 下面利用上面的结论证明（1）： 对于任意一个结点i，若2i≤n，则左孩子的编号为2i，反过来结点2i的双亲就是i，而 ?2i/2?=i；若2i+1≤n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而 ?(2i+1)/2? =i。 由此可以得出（1）成立。 二叉树的存储结构 顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树 （1）构造一棵完全二叉树 void CreateBTree(QBTree *BT,EntryType item[ ],int n) { if (n=MAX_TREE_NODE_SIZE) n=MAX_TREE_NODE_SIZE-1; for (i=1; i=n;i++) BT-item[i]=item[i]; BT-n=n; } （2）获取给定结点的左孩子 int LeftCHild(QBTree BT,int node) { if (2*nodeBT.n) return 0; else return 2