《【数据结构讲解】树和森林》由会员分享，可在线阅读，更多相关《【数据结构讲解】树和森林（119页珍藏版）》请在金锄头文库上搜索。
1、树和森林的概念树和森林的概念 二叉树二叉树 ( (Binary Tree)Binary Tree) 二叉树的表示二叉树的表示 二叉树遍历二叉树遍历 ( (Binary Tree Traversal)Binary Tree Traversal) 线索化二叉树线索化二叉树 ( (Threaded Binary Tree)Threaded Binary Tree) 堆堆 ( ( Heap )Heap ) 树与森林树与森林 ( (Tree Tree ( ); position Root ( ); BuildRoot ( const Type position FirstChild ( position
2、 p ); position NextSibling ( position p, position v ); position Parent ( position p ); Type Retrieve ( position p ); position InsertChild ( const position p, const Type 树的抽象数据类型树的抽象数据类型 position DeleteChild ( position p, int i ); void DeleteSubTree ( position t ); int IsEmpty ( ); 二叉树二叉树 ( (Binary T
3、ree)Binary Tree) 二叉树的定义二叉树的定义 二叉树的五种不同形态二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该一棵二叉树是结点的一个有限集合，该 集合或者为空，或者是由一个根结点加上两集合或者为空，或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的棵分别称为左子树和右子树的、互不相交的 二叉树组成。二叉树组成。 性质性质1 1 若二叉树的层次从若二叉树的层次从0 0开始开始, , 则在二叉树的则在二叉树的 第第 i i 层最多有层最多有 2 2 i i 个结点。个结点。( (i i 0) 0) 证明用数学归纳法证明用数学归纳法 性质性质2 2 高度为高度
4、为k k的二叉树最多有的二叉树最多有 2 2k+ k+1 1-1 -1个结点。个结点。 ( (k k -1) -1) 证明用求等比级数前证明用求等比级数前k k项和的公式项和的公式 性质性质3 3 对任何一棵二叉树对任何一棵二叉树, , 如果其叶结点个数为如果其叶结点个数为 n n0 0 , , 度为度为2 2的非叶结点个数为的非叶结点个数为 n n 2 2 , , 则有则有 n n 0 0 n n 2 2 1 1 二叉树的性质二叉树的性质 证明：证明：若设度为若设度为1 1的结点有的结点有n n1 1个，总结点个个，总结点个 数为数为n n，总边数为总边数为e e，则根据二叉树的定义，则根据
5、二叉树的定义， n n = = n n 0 0 + + n n 1 1 + + n n 2 2 e e = 2 = 2n n 2 2 + + n n 1 1 = = n n - 1 - 1 因此，有因此，有 2 2n n 2 2 + + n n 1 1 = = n n 0 0 + + n n 1 1 + + n n 2 2 - 1 - 1 n n 2 2 = = n n 0 0 - 1 - 1 n n 0 0 = = n n 2 2 + 1 + 1 定义定义1 1 满二叉树满二叉树( (Full Binary Tree)Full Binary Tree) 定义定义2 2 完全二叉树完全二叉树(
6、 (Complete Binary Tree)Complete Binary Tree) 若设二叉树的高度为若设二叉树的高度为h h，则共有则共有h h+1+1层。除第层。除第h h 层外，其它各层层外，其它各层(0(0 h h-1-1) )的结点数都达到最大个数的结点数都达到最大个数 ，第，第h h层从右向左连续缺若干结点，这就是完全层从右向左连续缺若干结点，这就是完全 二叉树。二叉树。 性质性质4 4 具有具有n n个结点的完全二叉树的高度为个结点的完全二叉树的高度为 loglog 2 2 ( (n n+1)+1) - -1 1 证明：证明：设完全二叉树的高度为设完全二叉树的高度为h h，
7、则有则有 2 2 h h - - 1 1 n n 2 2h h+1 +1 - - 1 1 2 2 h h n+n+1 1 2 2h h+1 +1 取对数取对数 h h 0, 则则 i i 的双亲为的双亲为 ( (i i -1)/2-1)/2 n n 若若2*2*i i+1 +1 n n, , 则则 i i 的左子女为的左子女为2*2*i i+1+1 若若2*2*i i+2 +2 n n, , 则则 i i 的右子女为的右子女为2*2*i i+2+2 n n 若若 i i 为偶数为偶数, , 且且i i != 0, != 0, 则其左兄弟为则其左兄弟为i i-1-1 若若 i i 为奇数为奇数,
8、 , 且且i i != != n n-1, -1, 则其右兄弟为则其右兄弟为i i+1+1 n n i i 所在层次为所在层次为 loglog 2 2 ( (i i+1)+1) 二叉树的抽象数据类型二叉树的抽象数据类型 template class BinaryTree public: BinaryTree ( ); BinaryTree ( BinTreeNode * lch, BinTreeNode * rch, Type item ); int IsEmpty ( ); BinTreeNode *Parent ( ); BinTreeNode *LeftChild ( ); BinTre
9、eNode *RightChild ( ); int Insert ( const Type int Find ( const Type Type GetData ( ) const; BinTreeNode *GetRoot ( ) const; 完全二叉树的数组表示 一般二叉树的数组表示 二叉树的表示二叉树的表示 数组表示数组表示 单支树 链表表示链表表示 由于一般二叉树必须仿照完由于一般二叉树必须仿照完 全二叉树那样存储，可能会全二叉树那样存储，可能会 浪费很多存储空间，单支树浪费很多存储空间，单支树 就是一个极端情况。就是一个极端情况。 二叉树链表表示的示例 二叉链表的静态结构 tem
10、plate class BinaryTree; template Class BinTreeNode friend class BinaryTree; public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) BinTreeNode ( Type item, BinTreeNode *left = NULL, BinTreeNode *right = NULL ) : data (item), leftChild (left), rightChild (right) Type 二叉树的类定义二叉树的类定义 BinTreeNode
11、 *GetLeft ( ) const return leftChild; BinTreeNode *GetRight ( ) const return rightChild; void SetData ( const Type void SetLeft ( BinTreeNode *L ) leftChild = L; void SetRight ( BinTreeNode *R ) rightChild = R; private: BinTreeNode *leftChild, *rightChild; Type data; ; template class BinaryTree publ
12、ic: BinaryTree ( ) : root (NULL) BinaryTree ( Type value ) : RefValue (value), root (NULL) virtual BinaryTree ( ) destroy ( root ); virtual int IsEmpty ( ) return root = NULL ? 1 : 0; virtual BinTreeNode *Parent ( BinTreeNode *current ) return root = NULL | root = current？ NULL : Parent ( root, curr
13、ent ); virtual BinTreeNode *LeftChild ( BinTreeNode *current ) return root != NULL ? currentleftChild : NULL; virtual BinTreeNode *RightChild ( BinTreeNode *current ) return root != NULL ? currentrightChild : NULL; virtual int Insert ( const Type virtual int Find ( const Type BinTreeNode *GetRoot (
14、) const return root; friend istream Type RefValue; BinTreeNode *Parent ( BinTreeNode *start, BinTreeNode *current ); int Insert ( BinTreeNode * template void BinaryTree: destroy ( BinTreeNode *current ) if ( current != NULL ) destroy ( currentleftChild ); destroy ( currentrightChild ); delete current; Template BinTreeNode *BinaryTree :Parent ( BinTreeNode *start, BinTreeNode *cuurent ) if ( start = NULL ) return NULL; if ( startleftChild =
