山大计算机数据结构ppt电子版资料DS06课件.ppt

树和森林的概念 二叉树 (Binary Tree) 二叉树的表示 二叉树遍历 (Binary Tree Traversal) 线索化二叉树 (Threaded Binary Tree) 堆 ( Heap ) 树与森林 (Tree Forest) 二叉树的计数 霍夫曼树 (Huffman Tree);树和森林的概念;结点(node) 结点的度(degree) 分支(branch)结点 叶(leaf)结点 子女(child)结点 双亲(parent)结点;template class Type class Tree { public: Tree ( ); ~Tree ( ); position Root ( ); BuildRoot ( const Type value ); position FirstChild ( position p ); position NextSibling ( position p, position v ); position Parent ( position p ); Type Retrieve ( position p ); position InsertChild ( const position p, const Type value );; position DeleteChild ( position p, int i ); void DeleteSubTree ( position t ); int IsEmpty ( ); };二叉树 (Binary Tree);性质1 若二叉树的层次从0开始, 则在二叉树的第 i 层最多有 2i 个结点。(i ? 0) [证明用数学归纳法] 性质2 高度为k的二叉树最多有 2k+1-1个结点。 (k ? -1) [证明用求等比级数前k项和的公式] 性质3 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2, 则有 n0＝n2＋1;证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 定义1 满二叉树(Full Binary Tree) 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的高度为h，则共有h+1层。除第h层外，其它各层(0?h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。;性质4 具有n个结点的完全二叉树的高度为 ?log2(n+1)? -1 证明：设完全二叉树的高度为h，则有 2h - 1 n ? 2h+1 - 1 2h n+1 ? 2h+1 取对数 h log2(n+1) ? h+1 ;性质5 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，然后按此结点编号将树中各结点顺序地存放于一个一维数组中, 并简称编号为i的结点为结点i (0 ? i ? n-1。则有以下关系： 若i == 0, 则 i 无双?? 若i 0, 则 i 的双亲为?(i -1)/2? 若2*i+1 n, 则 i 的左子女为2*i+1 若2*i+2 n, 则 i 的右子女为2*i+2 若 i 为偶数, 且i != 0, 则其左兄弟为i-1 若 i 为奇数, 且i != n-1, 则其右兄弟为i+1 i 所在层次为 ?log2 (i+1)? ;二叉树的抽象数据类型;完全二叉树的数组表示 一般二叉树的数组表示; 单支树;二叉树链表表示的示例;二叉链表的静态结构;template class Type class BinaryTree; template class Type Class BinTreeNode { friend class BinaryTree; public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) { }