花儿为什么.ppt

树和森林的概念树和森林的概念二叉树二叉树 ( ( Binary Tree) Binary Tree) 二叉树的表示二叉树的表示二叉树遍历二叉树遍历 ( ( Binary Tree Traversal) Binary Tree Traversal) 线索化二叉树线索化二叉树 ( ( Threaded Binary Tree) Threaded Binary Tree) 堆堆 ( ( Heap ) Heap ) 树与森林树与森林( ( Tree & Forest) Tree & Forest) 二叉树的计数二叉树的计数霍夫曼树霍夫曼树 ( ( Huffman Tree) Huffman Tree) 树和森林的概念树和森林的概念树的定义树的定义树是由树是由 n n ( (n n?? 0) 0) 个结点组成的有限集合。如果个结点组成的有限集合。如果 n n = 0 = 0 , ,称为空树;如果称为空树;如果 n n > 0 > 0 , ,则则??有一个特定的称之为有一个特定的称之为根根( ( root) root) 的结点,它只有的结点,它只有直接后继,但没有直接前驱; 直接后继,但没有直接前驱; ??除根以外的其它结点划分为除根以外的其它结点划分为 m m ( (m m?? 0) 0) 个互不个互不相交的有限集合相交的有限集合 T T 0 0, , T T 1 1, , ……, , T T m m -1 -1, ,每个集合又是一每个集合又是一棵树,并且称之为根的棵树,并且称之为根的子树子树( ( subTree subTree ) )。。每棵子树每棵子树的根结点有且仅有一个直接前驱,但可以有的根结点有且仅有一个直接前驱,但可以有 0 0个个或多个直接后继。或多个直接后继。 n n结点结点( ( node) node) n n结点的度结点的度( ( degree) degree) n n分支分支( ( branch) branch) 结点结点 n n叶叶( ( leaf) leaf) 结点结点 n n子女子女( ( child) child) 结点结点 n n双亲双亲( ( parent) parent) 结点结点 n n兄弟兄弟( ( sibling) sibling) 结点结点 n n祖先祖先( ( ancestor) ancestor) 结点结点 n n子孙子孙( ( descendant) descendant) 结点结点 n n结点所处层次结点所处层次( ( level) level) n n树的高度树的高度( ( depth) depth) n n树的度树的度( ( degree degree ) ) ??有序树有序树??无序树无序树??森林森林 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) Binary Tree) 二叉树的定义二叉树的定义二叉树的五种不同形态二叉树的五种不同形态一棵二叉树是结点的一个有限集合,该一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树组成。性质性质 1 1若二叉树的层次从若二叉树的层次从 0 0开始开始, , 则在二叉树的则在二叉树的第第 i i 层最多有层最多有 2 2 i i 个结点。个结点。( (i i?? 0) 0) [ [证明用数学归纳法证明用数学归纳法] ]性质性质 2 2高度为高度为 k k的二叉树最多有的二叉树最多有 2 2 k+ k+ 1