第六章 树和森林 1、树、森林的概念 2、二叉树及其表示 3、遍历二叉树和线索二叉树 4、堆 5、树和森林 6、二叉树的计数 7、霍夫曼树

Presentation on theme: "第六章 树和森林 1、树、森林的概念 2、二叉树及其表示 3、遍历二叉树和线索二叉树 4、堆 5、树和森林 6、二叉树的计数 7、霍夫曼树"— Presentation transcript:

1 第六章 树和森林 1、树、森林的概念 2、二叉树及其表示 3、遍历二叉树和线索二叉树 4、堆 5、树和森林 6、二叉树的计数 7、霍夫曼树
目录 第六章 树和森林 1、树、森林的概念 2、二叉树及其表示 3、遍历二叉树和线索二叉树 4、堆 5、树和森林 6、二叉树的计数 7、霍夫曼树

2 1、树、森林的概念 基本概念 树：n > o 个结点的集合，根、其余结点分为 m >= 0 个集合，每一个集合本身又是一
棵树（子树） 度、叶子、父结点、儿子结点、祖先结点、层次、高度(深度和高度不同，书上定义错) 有序树及无序树 森林 m >= 0 棵互不相交树的集合 A B C D E F G H I L E、G：高度为 3 、度为 3 的树 其它表示方法： ( A(B(L,E),C(F),D(G(I),H)) 书上还介绍了两种，请参考。

3 2、二叉树 1、定义 空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树。 和树的区别：可为空 左右子树有序，不可颠倒 B
C D E F L E、G：二叉树 E、G：结点总数为 3 时的所有二叉树的树的形状

4 2、二叉树 2、性质： 性质1：在二叉树的第 i 层上至多有 2 i个结点。注意：根所在层次为0，依次加1 。 0层：结点个数 20=1 个
1层：结点个数 21=2个 2层：结点个数 22=4 个 A C L D B E F 证：k = 0 时成立，设 k = i-1 时成立 则当 k = i 时在二叉树的第 i 层上至多有 2 i-1 * 2 = 2 i 个结点 C E F L A 性质2：高度为 K 的二叉树至多有 2k+1- 1 个结点。 证：利用性质 1 ，将第 1 层至第 k 层的最多的结点数进行相加： ………… + 2k-1 + 2k = 2k+1 - 1 性质3：二叉树的叶子结点数 n0 等于度为 2 的结点数n2 + 1 证：设度为 1 的结点数为 n1，树枝的总数为 B 则：B = n-1=n0+n1+n2-1 又 B = n1+2×n2； 原命题得证。

5 2、二叉树 完全二叉树: 1、满二叉树 2、从满二叉树最底层从右向左依次去掉若干结点形成的 B C D E F L A P S Q R X
U W V 满二叉树: 每层结点 数最多 B C D E F L A P S Q R U 性质4：具有 n 个结点的完全二叉树的高度为 log2(n +1) - 1 证：根据性质 2 和完全二叉树的定义： 2k-1 < n <= 2k+1 -1 2k < n + 1 <= 2k+1 k < log2(n +1) <= k+1 故：k + 1 = log2(n +1) ; 原命题得证。

6 2、二叉树 性质5：对一棵有 n 个结点的完全二叉树按照从第一层（根所在的层次〕到最后一层，并且 每一层都按照从左到右的次序进行编号。根结点的编号为 0，最后一个结点的编号 为 n-1。 1：对任何一个编号为 i 的结点而言，它的左儿子的编号为 2i+1( 若 2i+1 <= n) ,而右 儿子的编号为 2i+2(若 2i +2 <= n)。 2：对任何一个编号为 j 的结点而言，它的父亲结点的的编号为 (j-1)/2 。根结点无父 结点。 证： A C L 2 1 B E F D 3 5 6 4 P Q R S U 7 8 9 10 11

7 2、二叉树 ·二叉树的 ADT： Template <class Type> class BinaryTree {
public: BinaryTree( ); // 构造空二叉树 BinaryTree ( BinTreeNode < Type> * lch, BinTreeNode < Type> * rch, Type item ); int IsEmpty( ); // 二叉树为空返回1，否则为 0 BinTreeNode < Type> * Parent( BinTreeNode < Type> * ); BinTreeNode < Type> * leftChild( BinTreeNode < Type> * ); BinTreeNode < Type> * RightChild( BinTreeNode < Type> * ); int Insert ( const Type & item ); int Find ( const Type & item ); Type GetData ( ) const; }

8 2、二叉树 3、二叉树的存储结构： 顺序存储结构： 一般情况： rchild lchild data A B C D E F G H I L
1 2 3 4 5 6 7 8 9 rchild lchild data A B C D E F G H I L 应用范围：适用于二叉树上的结点个数已知，或不支持动态存储分配的高级语言。

9 2、二叉树 3、二叉树的存储结构： 顺序存储结构： 特殊情况： data lchild rchild A B C D E F G H I L
1 2 3 4 5 6 7 8 9 A B C D E F G H I L A B C D E F G H I L 应用范围：适用于完全二叉树，且结点个数已知。

10 2、二叉树 3、二叉树的存储结构： 顺序存储结构： 特殊情况：若不是完全二叉树，许多数据场为空，不合算。如下例所示： A B D H I A
1 2 3 4 5 6 7 8 A B ∧ D H I A B D H I

11 2、二叉树 data leftchildrightchild data leftchildrightchild Parent
3、二叉树的存储结构： 链接存储结构： 仅定义结点的类型即可。 A B C D E F G H I L 标准形式：（二叉链表） data leftchildrightchild 广义标准形式：（三叉链表） data leftchildrightchild Parent

12 2、二叉树 ·二叉树的 ADT： Template <class Type> class BinaryTree;
Template <class Type> class BinTreeNode { friend class BinaryTree < Type>; public: BinTreeNode ( ) : leftChild(NULL); rightChild(NULL) { } // BinTreeNode ( Type item, BinTreeNode < Type> * left = NULL, BinTreeNode < Type> * right = NULL ): data(item),leftChild(left), rightChild( right ) { } Type GetData ( ) const { return data; } BinTreeNode < Type> * GetLeft( ) const { return lfetChild; } BinTreeNode < Type> * GetRight( ) const { return rightChild; } void SetData ( const Type & item ) { Data = item; } void SetLeft (BinTreeNode < Type> * L ) { leftChild = L; } void SetRight (BinTreeNode < Type> * R ) { rightChild = R; } private: BinTreeNode < Type> * leftChild, * rightChild; } Type Data; }

13 2、二叉树 ·二叉树的 ADT： Template <class Type> class BinaryTree {
public: BinaryTree( ) : root( NULL) { } // 构造空二叉树 BinaryTree ( Type value) : RefValue( value ). root( NULL) { } virtual ~ BinaryTree ( ) { destroy ( root ); } virtual int IsEmpty ( ) { return root == NULL? 1: 0; } virtual BinTreeNode < Type> * LeftChild( BinTreeNode < Type> * current ) { return root ! = NULL ? Current->leftChild : NULL; } virtual BinTreeNode < Type> * RightChild( BinTreeNode < Type> * current ) { return root ! = NULL ? Current->rightChild : NULL; } virtual BinTreeNode < Type> * Parent( BinTreeNode < Type> * current ) { return root = = NULL || root = = current ? NULL : Parrent ( root, current ); } vitual int Insert ( const Type & item ); vitual int Find ( const Type & item ); const BinTreeNode < Type > * GetRoot ( ) const { return root; } // 接下页

14 2、二叉树 ·二叉树的 ADT： // 接上页 friend istream & operator >> ( istream & in, BinaryTree < Type > &Tree); friend ostream & operator << ( ostream & out, BinaryTree < Type > &Tree); private: BinTreeNode < Type> * root; Type RefValue; BinTreeNode < Type> * Parent( BinTreeNode < Type> * start, BinTreeNode < Type> * current ); int Insert ( BinTreeNode < Type> * & current, const Type & item ); void traverse ( BinTreeNode < Type> * current, ostream & out ) const; void find ( BinTreeNode < Type> * current, const Type & item ) const; void destroy ( BinTreeNode < Type> * current ); }

15 2、二叉树 ·二叉树的 ADT：部分函数的实现。 Template <class Type>
void BinaryTree < Type > :: Traverse ( BinaryTree < Type > * current, ostream & out ) const { // 对以 current 为根的子树进行遍历，并输出数据场之值。 If ( current != NULL ) { out << current->data << ‘ ‘ ; Traverse ( current->leftChild, out ); Traverse ( current->rightChild, out );\ }

16 2、二叉树 ·二叉树的 ADT：部分函数的实现。 Template <class Type>
istream & operator >> ( istream & in, BinaryTree < Type > & Tree ) { // 对 >> 进行重载，输入数据并建立该二叉树。 Type item; cout << “Construct Binary Tree:\ n” cout << “Input data ( end with ” << Tree.RefValue << “ ):”; in >> item; while ( item != Tree.RefValue ) { Tree.Insert ( item ); } // while }

17 3、遍历二叉树和线索二叉树 R 1、遍历二叉树：设 N 代表根节点，L 代表左子树，R 代表右子树。
a. 前序（或先序）：如果二叉树为空，则操作为空：否则访问根结点；前序遍历左子树； 前序遍历右子树。记为：NLR。 b. 中序： 如果二叉树为空，则操作为空：否则中序遍历左子树；访问根结点； 中序遍历右子树。记为：LNR。 c. 后序： 如果二叉树为空，则操作为空：否则后序遍历左子树；后序遍历右子 树；访问根结点。记为：LRN。 前序：A、L、B、E、 C、D、W、X B C D E L A X W R B C D E L A X W 中序：B、L、E、A、 C、W、X、D 后序：B、E、L、X、 W、D、C、A

18 3、遍历二叉树和线索二叉树 A A 前序：A、L、B、E、C、D、W、X L C 中序：B、L、E、A、C、W、X、D L C
1、遍历二叉树：续 a. 前序分析：结点的左儿子、左孙子、左后代、…… 将连续输出。结点的右儿子将在结点、结点的左 子树全部输出之后才输出。 b. 中序分析：最先输出的结点是根结点的最左的左后代。将二叉树中的结点投影到水平轴线上，则得到 中序遍历的序列。 c. 后序分析：根结点（或子树的根结点）将在它的左、右子树的结点输出之后。因此，根结点（或子树 的根结点）在中序序列中的序号等于它的左右子树的结点个数 ＋左右子树中的最先被访问 的结点的序号。注意，结点、右父亲、右祖父、…… 将连续输出。 A A 前序：A、L、B、E、C、D、W、X L C 中序：B、L、E、A、C、W、X、D L C 后序：B、E、L、X、W、D、C、A B E D D B E W W X X B L E A C W X D

19 3、遍历二叉树和线索二叉树 1、根结点进栈 2、结点出栈，被访问 3、结点的右、左儿子（非空）进栈 4、反复执行 2、3 ，至栈空为止。
1、遍历二叉树：续 前序的程序实现： 1、根结点进栈 2、结点出栈，被访问 3、结点的右、左儿子（非空）进栈 4、反复执行 2、3 ，至栈空为止。 e.g: 前序：A、L、B、E、C、D A L C D B E D出栈访问后，栈空结束 C、L 进栈 E、B 进栈 A进栈 A出栈访问 L出栈访问 B出栈访问 E出栈访问 C出栈访问 D进栈 <B> <L> <E> <E> <A> <C> <C> <C> <C> <C> <D> 分析：p的前序的直接后继q: 1、p有左儿子，则q=该左儿子 2、p无左儿子，有右儿子，则q=该左儿子 3、 、p无左儿子、右儿子 ，搜索其祖先结点的右儿子送q。找不到结束。

20 3、遍历二叉树和线索二叉树 Template <class Type> class TreeIterator { public:
TreeIterator ( const BinaryTree < Type > & BT ) : T( BT ). current( NULL) { } virtual ~ TreeIterator ( ) { } virtual void First ( ) = 0; // 第一个位置为当前位置 virtual void operator ++ ( ) = 0; // 下一个被访问结点位置 int operator + ( ) const { return current ! = NULL; } // 判是否有效位置。 const Type & operator ( ) ( ) const; // 返回当前指针 current 所指向的结点的值。 protected: const BinaryTree <Type > & T; const BinaryTree <Type > & current; private: TreeIterator ( const TreeIterator & ) { } TreeIterator & operator = ( const TreeIterator & ) const; }

21 3、遍历二叉树和线索二叉树 1、遍历二叉树：二叉树的迭代器，即本书所讲的游标类（ Tree Iterator ） ：前序的实现 Template <class Type> class Preorder : public TreeIterator < Type > { public: Preorder( const BinaryTree < Type > & BT ); ~Preorder( ) { } void First( ); void operator ++ ( ); protected: Stack < const BinTreeNode <Type > * > st; }; Template <class Type > Preorder <Type>:: Preorder( const BinaryTree <Type> & BT ): TreeIterator< Type > ( BT ) { st.Push( T.Getroot( ) ); } Template <class Type > void Preorder <Type> :: First ( ) { // 得到第一个访问的结点地址 st.MakeEmpty ( ); if ( T.GetRoot( ) ) st.Push( T.Getroot( ) ); operator ++ ( ); } Template <class Type > void Preorder <Type>:: operator ++ ( ) { if ( st.IsEmpty() ) { if ( current == NULL ) { cerr << “Advanced past end ” << endl; exit( 1 ); } current = NULL; rturn; } current = st.Pop( ); if ( current ->GetRight ( ) != NULL ) st.Push( current->GetRight( ) ); if ( current ->GetLeft ( ) != NULL ) st.Push( current->GetLeft( ) ); }

22 3、遍历二叉树和线索二叉树 A e.g: L C D E 分析：1、二叉树最先被访问的结点是二叉树中最左方的叶子。
1、遍历二叉树：设根结点初始时非空 后序算法：1、结点（初始时为根）进栈（标志0），沿左指针查找左儿子（标志1） 2、左儿子非空，返回1。 3、退栈。若为标志1转 4 ，否则标志 2，转 5。 4、进栈转向右子树（标志2），如右儿子非空，则转向 1；空转向 3。 5、访问结点，返回 3 6、反复 1 到 5 ，至栈空为止。 A e.g: 后序：E、L、D、C、A L C D E 分析：1、二叉树最先被访问的结点是二叉树中最左方的叶子。 2、p的后序的直接后继q: 1、p是父结点的右儿子，则q=该父结点。2、p是父结点的左 儿子，如果有右子树，则q=该右子树中最左的叶子。如果，无右子树，q=父结点。 3、p无父结点，那么q == NULL。

23 3、遍历二叉树和线索二叉树 Template <class Type> struct stkNodere {
1、遍历二叉树：二叉树的迭代器，即本书所讲的游标类（ Tree Iterator ） ：后序的实现 Template <class Type> struct stkNodere { const BinaryTree < Type > * Node; int PopTim; stkNodere ( const BinTreeNode <Type > * N = NULL ): Node(N), PopTim(0) { } }; Template <class Type> class Postorder : public TreeIterator < Type > { public: Postorder( const BinaryTree < Type > & BT ); ~Postorder( ) { } void First( ); // 后序情况下的第一个结点的地址 void operator ++ ( ); // 后序情况下的下一个结点的地址 protected: Stack < stkNode <Type> > st;

24 3、遍历二叉树和线索二叉树 1、遍历二叉树：二叉树的迭代器，即本书所讲的游标类（ Tree Iterator ） ：后序的实现 Template <class Type > Preorder <Type>:: Postorder( const BinaryTree <Type> & BT ): TreeIterator< Type > ( BT ) { st.Push( stkNode<Type>( T.Getroot( ) ); } Template <class Type > void Postorder <Type> :: First ( ) { // 得到第一个访问的结点地址 st.MakeEmpty ( ); if ( T.GetRoot( ) ) st.Push ( stkNode<Type>( T.Getroot( ) ); operator ++ ( ); } //根结点地址及标志 0 进栈，去去寻找第一个被访问的最左方的叶子。 Template <class Type > void Postorder <Type>:: operator ++ ( ) { if ( st.IsEmpty() ) { // 当栈空且 current 也为空时，遍历结束。 if ( current == NULL ) { cerr << “Advanced past end ” << endl; exit( 1 ); } current = NULL; return; } // 置当前指针为空，结束。 stkNode<Type> Cnode; for ( ; ; ) { Cnode = st.Pop( ); if ( ++ Cnode.PopTim == 3 ) { current Cnode.Node; return; } // 其左右子树处理完毕,可访问 st.Push( Cnode ); if ( Cnode.PopTim == 1 ) { // 访问左子树。 if ( Cnode.node -> GetLeft ( ) != NULL ) st.Push(stkNode<Type>( Cnode.Node -> GetLeft ( ) ) ); } // 有左儿子，则进栈 else { if ( Cnode.node -> GetRight ( ) != NULL ) st.Push(stkNode<Type>( Cnode.Node -> GetRight ( ) ) ); } // 访左结束，有右儿子进栈 }

25 3、遍历二叉树和线索二叉树 1、结点（初始时是根结点）进栈，沿左指针查找左儿子。 2、若有左儿子，返回第一步。
1、遍历二叉树：续 中序的程序实现： 1、结点（初始时是根结点）进栈，沿左指针查找左儿子。 2、若有左儿子，返回第一步。 3、若无左儿子，判栈空？空则结束。非空，栈顶结点出栈 访问。转向右子树，返回1。 中序：B、L、E、A、C、W、X、D e.g: A 分析：1、二叉树最先被访问的结点是二叉树中最左方的 的左后代。 2、p的中序的直接后继q: 1、p有右子树，则q=p 的右子树的最左方的左后代。 2、p无右子树，如p是父结点的左儿子，则q=该 父结点。 3、p无右子树，如p是父结点的右儿子 则以p 的父结点为根的子树访问完毕。如该子树为其祖 先结点的左子树，那么q=其根。否则，继续寻 找，找不到结束。 L C D B E W X

26 3、遍历二叉树和线索二叉树 B C D E L A X W B C D E L A X W e.g: n = 8 的二叉树 扩展二叉树
2、线索二叉树： 为什么采用线索二叉树：二叉树中的空指针场多达 n + 1 个。 简单证明：设二叉树中结点的总数为 n，度为 2 的结点总数为 n2 。空指针场用 方框代表。增加了方 框结点的二叉树称之为扩展二叉树。在该二叉树之中，原来的 n 个结点全部成为度为 2 的结 点，方框结点成为叶子。根据二叉树的性质 3 ，原命题得证。 B C D E L A X W B C D E L A X W e.g: n = 8 的二叉树 扩展二叉树 怎样利用这 n + 1 个空指针场？ 中序穿线树 后序穿线树

27 3、遍历二叉树和线索二叉树 e.g: n = 6 的二叉树 无前驱结点 无后继结点 A A 中序穿线树 L C L C D D B E B
2、线索二叉树： 中序穿线树（中序线索二叉树）的实现： 在二叉树的结点的标准形式中，增加两个标志域，用于区别是否是穿线。如下所 示： 其中 data 为数据场，leftThread = 0 时，leftchild 场指向本结点的真正的左儿子 leftThread = 1 时，leftchild 场指向本结点的按中序遍历序列的前驱结点(穿线) rightThread = 0 时，rightchild 场指向本结点的真正的右儿子 rightThread = 1 时，rightchild 场指向本结点的按中序遍历序列的后继结点(穿线) leftchild leftThread data rightThread rightrchild e.g: n = 6 的二叉树 无前驱结点 无后继结点 A A 中序穿线树 L C L C D D B E B E

28 3、遍历二叉树和线索二叉树 1:穿线 0:实际儿子 A L C 表示 D B E 2、线索二叉树： 中序穿线树中的结点的数据结构： 1 1
root: 新增头结点 1 root: 新增头结点 1 无前驱结点 无后继结点 A A L C 表示 D B E L 1 C 1:穿线 0:实际儿子 1 B 1 1 E 1 1 D 1

29 3、遍历二叉树和线索二叉树 L A E B L C A D B E D 2、线索二叉树：
在中序穿线树上进行中序遍历、不用堆栈的的算法及程序要点： 1、最先输出最左的左后代结点 2、结点无右后件，则该结点的中序的后继结点，由右儿子的指针场给出。但要注意以下情况： 3、结点有右儿子，则该结点的中序的后继结点，是它的右子树中的最左的左后代结点。 4、最先输出的结点无前驱结点，最后输出的结点无后继结点。 无前驱结点 L 无后继结点 A E B L C A D B E 指向当前结点 D 指向后继结点

30 3、遍历二叉树和线索二叉树 Template < class Type >
2、线索二叉树：在中序穿线树上进行中序遍历、不用堆栈的程序实现。声明部分很简单，请自己看一下。 Template < class Type > ThreadNode < Type > * ThreadNodeIterator < Type > :: First ( ) { // 得到第一个访问的结点 while ( current->leftThread == 0 ) current = current ->leftChild; return current; } ThreadNode < Type > * ThreadNodeIterator < Type > :: Next ( ) { // 得到下一个访问的结点 ThreadNode < Type > * p = current->rightChild; if ( current ->rightThread == 0 ) while ( p->leftThread == 0 ) p = current ->leftChild; current = p; if ( current == T.root ) return NULL; else return current; void ThreadNodeIterator < Type > :: InorderFirst ( ) { // ThreadNodeIterator < Type > * p; for ( p = first; p != NUPP; p = Next( ) ) cout << p->data << endl; T 1 A L C D B E 无后继结点

31 3、遍历二叉树和线索二叉树 G D A A C X C E B B X D F G D 2、父结点有 右儿子 A A C C X B B X
2、线索二叉树：在中序穿线树上插入新的结点的操作。删除部分请自看一下。 仅举新插入的结点为父结点的右儿子的情况。新插入的结点为父结点的左儿子的情况，类似。 G D A A C X C E B B X D F G D 2、父结点有 右儿子 A A C C X B B X E 1、父结点无右儿子 D F

32 4、堆 1、 堆 堆的定义：n 个元素的序列 { k0， k1，…… ， kn-1 }，当且仅当满足以下关系时，称 之为堆：
ki <= k2i+1 ki >= k2i ki <= k2i+2 ki >= k2i+1 ( i = 0,1,2, …… , (n-2)/2 ) 且分别称之为最小化堆和最大化堆。 e.g: 序列 { 96,83,27,11,9} 最大化堆 { 12，36，24，85，47，30，53，91} 最小化堆 或 96 12 2 1 1 2 83 27 36 24 3 4 5 6 3 4 11 9 85 47 30 53 7 91

33 The largest element in a maximum-heap is always found in the root node
70 60 12 40 30 8 10

34 The heap can be stored in an array
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] root 70 60 12 40 30 8 10 70 60 1 12 2 30 4 10 6 40 3 8 5

35 4、堆 [ 0 ] [ 1 ] 70 [ 2 ] 60 [ 3 ] 12 [ 4 ] 40 [ 5 ] 30 [ 6 ] 8 10 root
2、 建堆 时间复杂性的分析： 建堆的时间耗费：比较次数 - 4n 次 O(n) 级 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] root 70 60 12 40 30 8 10 70 60 1 12 2 30 4 10 6 40 3 8 5

36 4、堆 [ 0 ] [ 1 ] 30 [ 2 ] 60 [ 3 ] 8 [ 4 ] 40 [ 5 ] 70 [ 6 ] 12 10 root
2、 建堆 时间复杂性的分析： 建堆的时间耗费：比较次数 - 4n 次 O(n) 级 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] root 30 60 8 40 70 12 10 不合堆的定义，需调整。即建立小堆。建立的第一个小堆的堆顶的下标为 (n-2)/2 30 60 1 8 2 70 4 10 6 40 3 12 5 叶子结点，符合堆的的定义。

37 4、堆 [ 0 ] [ 1 ] 30 [ 2 ] 60 [ 3 ] 12 [ 4 ] 40 [ 5 ] 70 [ 6 ] 8 10 root
2、 建堆 时间复杂性的分析： 建堆的时间耗费：比较次数 - 4n 次 O(n) 级 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] root 30 60 12 40 70 8 10 不合堆的定义，需调整。即建立小堆。建立的第一个小堆的堆顶的下标为 (n-2)/2 30 60 1 12 2 70 4 10 6 40 3 8 5 叶子结点，符合堆的的定义。

38 4、堆 [ 0 ] [ 1 ] 30 [ 2 ] 60 [ 3 ] 12 [ 4 ] 40 [ 5 ] 70 [ 6 ] 8 10 root
2、 建堆 时间复杂性的分析： 建堆的时间耗费：比较次数 - 4n 次 O(n) 级 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] root 30 60 12 40 70 8 10 不合堆的定义，需调整。建立以 L[ 1 ] 为堆顶的正确的最大化小堆。 30 60 1 12 2 70 4 10 6 40 3 8 5 叶子结点，符合堆的的定义。

39 4、堆 [ 0 ] [ 1 ] 30 [ 2 ] 70 [ 3 ] 12 [ 4 ] 40 [ 5 ] 60 [ 6 ] 8 10 root
2、 建堆 时间复杂性的分析： 建堆的时间耗费：比较次数 - 4n 次 O(n) 级 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] root 30 70 12 40 60 8 10 不合堆的定义，需调整。建立以 L[ 1 ] 为堆顶的正确的最大化小堆。 30 70 1 12 2 60 4 10 6 40 3 8 5 叶子结点，符合堆的的定义。

40 4、堆 [ 0 ] [ 1 ] 30 [ 2 ] 70 [ 3 ] 12 [ 4 ] 40 [ 5 ] 60 [ 6 ] 8 10 root
2、 建堆 时间复杂性的分析： 建堆的时间耗费：比较次数 - 4n 次 O(n) 级 不合堆的定义，需调整。建立以 L[ 0 ] 为堆顶的正确的最大化小堆。 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] root 30 70 12 40 60 8 10 30 70 1 12 2 60 4 10 6 40 3 8 5 叶子结点，符合堆的的定义。

41 4、堆 [ 0 ] [ 1 ] 70 [ 2 ] 30 [ 3 ] 12 [ 4 ] 40 [ 5 ] 60 [ 6 ] 8 10 root
2、 建堆 时间复杂性的分析： 建堆的时间耗费：比较次数 - 4n 次 O(n) 级 不合堆的定义，需调整。建立以 L[ 0 ] 为堆顶的正确的最大化小堆。 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] root 70 30 12 40 60 8 10 70 30 1 12 2 60 4 10 6 40 3 8 5 叶子结点，符合堆的的定义。

42 4、堆 [ 0 ] [ 1 ] 70 [ 2 ] 60 [ 3 ] 12 [ 4 ] 40 [ 5 ] 30 [ 6 ] 8 10 root
2、 建堆 时间复杂性的分析： 建堆的时间耗费：比较次数 - 4n 次 O(n) 级 不合堆的定义，需调整。建立以 L[ 0 ] 为堆顶的正确的最大化小堆。 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] root 70 60 12 40 30 8 10 70 60 1 12 2 10 6 40 3 30 4 8 5 叶子结点，符合堆的的定义。

43 4、堆 时间复杂性的分析： 建堆的时间耗费：设树根处于第 0 层，最下面是 h 层。建堆从第 h-1 层开始进行。只 要知道了每一层的结点数（建的小堆的个数），和每建一个小堆所 需的比较次数，就可以求得建堆的时间耗费。 建的小堆的性质：第 i 层上小堆的个数 ＝ 第 i 层上结点的个数 ＝ 最多 2i 第 i 层上小堆的最大层数 ＝ h-i＋1 建第 i 层上每个小堆最多所需的比较次数 ＝ 2×（h-i）次 建堆的时间耗费： S(n) <= ∑ 2i×(h-i)×2 = ∑ 2i+1×(h-i) = ∑ 2h-j+1×j = 2h+1 ∑ j/2j 注意：高度为 h 的完全的二叉树，满足以下式子： 2h <= n 故： 2h+1 <= 2n 又： ∑ j/2j < 2 所以：建堆的时间复杂性为 4n=O(n) 级 h i=h-1 i=h-1 j=1 h j=1 ∞ j=1

44 4、堆 Template < class Type >
3、堆：建立一个最小化堆（建立最大化堆同样道理），堆即最小化堆的声明，请自看。 Template < class Type > MinHeap < Type > :: MinHeap ( int maxSize ) { // MaxHeapSize = DefaultSize < maxSize ? maxSize : DefaultSize; heap = New Type [ MaxHeapSize]; CurrentSize = 0; } MinHeap < Type > :: MinHeap ( Type arr [ ], int n ) { // heap = New Type [ MaxHeapSize]; heap = arr; CurrentSize = n; int currentPos = ( CurrentSize - 2 ) / 2; while (currentPos >= 0 ) { FiltDown ( currentPos, Currentsize -1); currentPos --; } // while end }; 无后继结点

45 4、堆 Template < class Type >
3、堆：建立一个最小化堆（建立最大化堆同样道理），堆即最小化堆的声明，请自看。 Template < class Type > void MinHeap < Type > :: FiltDown( const int start, const int EndOfHeap ) { // int i = start; j = 2 * i + 1; Type temp = heap[ i ]; while ( j <= EndofHeap ) { if ( j < EndofHeap && heap [ j ]. key > heap [ j +1 ]. key ) j ++; if ( temp. key < heap [ j +1 ]. key ) break; else { heap [ i ] = heap [ j ]; i = j; j = 2 * i + 1; } // while end heap [ i ] = temp; }; 无后继结点

46 4、堆 1、插入一个新的结点：插在最后，然后向父结点 方向调整。如插入优先级为 15 的结点在序号 16 处。 12
3、堆：插入一个新的结点，删除一个新的结点，改变结点的优先级。 1、插入一个新的结点：插在最后，然后向父结点 方向调整。如插入优先级为 15 的结点在序号 16 处。 12 1 2 2、结点的优先级改变。如：结点的优先级 从 85 改变为 8 或 93。 变小：向根结点方向调整。 变大：向叶子方向调整。 36 24 3 4 5 6 85 47 30 53 10 7 8 9 11 12 13 14 86 89 48 130 53 90 124 120 3、删除任意一个结点，如：删结点 47。 是 2、中的变小的特殊情况。当成优先 数无穷小的情况，上升到根结点，然后 和最大序号的结点交换，实现删除。在 从根结点开始进行调整。 15 136 4、时间复杂性分析：插入、删除代价都是 O(log2n)级的。建堆是O(n)级的。 是表示优先队列的理想的数据结构。

47 5、树和森林 ………… 1、树的存储结构 标准形式：树中的每个结点除有数据场之外，还有 K 个指针场；其中 K 为树的度数。1、
第一个儿子结点的地址 第二个儿子结点的地址 第 K 个儿子结点的地址 父亲结点的地址 数据场 ………… 广义标准形式：在标准形式的基础上，再增加指向父亲结点的指针场。 E.g: 度数 K ＝ 3 的树 用数组表 示左图的 树 -1 表示空 缺点：空指针场太多，多达 ( K -1 )× n + 1 个。 改进：结点中设立度数场， 指针场依度数定。但 操作麻烦。 采用左儿子、兄弟表 示法。 A 1 2 3 4 5 6 7 8 9 A B C D E F G H I P B C D L E F G H I

48 5、树和森林 1、树的存储结构 左儿子、兄弟表示法：树中的每个结点有数据场、指向它的第一棵子树树根的指针场、
指向它的兄弟结点的指针场。实质上是用二叉树表示一棵树。 第一棵子树根结点的地址 下一个亲兄弟结点的地址 数据场 A A ∧ B C D B C D ∧ L E F G H ∧ L E ∧ ∧ F ∧ G ∧ H ∧ I E.g: 度数 K ＝ 3 的树 ∧ I ∧

49 5、树和森林 2、树、森林于二叉树的转换 树转换成相对应的二叉树： 1、保留每个结点的最左面的分支，其余分支都被删除。
2、同一父结点下面的结点成为它的左方结点的兄弟。 E.g: 度数 K ＝ 3 的树 A B C D E F G H I L A A B C D B C D L E F G H L E F G H I I

50 5、树和森林 2、树、森林于二叉树的转换 森林转换成相对应的二叉树： 增加一个虚拟的根结点，它的儿子为各棵树的根。
那么，就变成了树转换成二叉树的问题。 A E.g: 3 棵分别以B、 C、D为根的树 B A 相应的二叉树 C L B C D B C D D F E L E F G H L E F G H G I I I H

51 5、树和森林 2、树、森林于二叉树的转换 森林转换成相对应的二叉树： 增加一个虚拟的根结点，它的儿子为各棵树的根。
那么，就变成了树转换成二叉树的问题。 E.g: 3 棵分别以B、 C、D为根的树 B A 相应的二叉树 C L B C D B C D D F E L E F G H L E F G H G I I I H

52 5、树和森林 R T1 T2 …… T3 3、树、森林的遍历 树的前序、后序遍历：
1、类似于二叉树的前序遍历：NLR；N:根；L：左子树（第一棵子树）， R：其余的那些子树，遍历方向由第二棵子树至最后一棵子树 2、类似于二叉树的后序遍历：LRN：L：左子树（第一棵子树），R：其 余的那些子树，遍历方向由第二棵子树至最后一棵子树， N:根 N B C D E F G H I L A T T2 …… T3 R 前序：A、B、L、E、C、F、D、G、I、H 后序：L、E、B、F、C、I、G、H、D、A

53 5、树和森林 3、树、森林的遍历 森林的前序、中序遍历： 前序遍历类似于树的前序遍历。增加一个虚拟的根结点，它的儿子为各棵树的
根。那么对这棵树进行前序遍历，即得到森林的前序序列（不含树根结点） 中序遍历类似于树的后序遍历。增加一个虚拟的根结点，它的儿子为各棵树的 根。那么对这棵树进行后序遍历，即得到森林的中序遍历（去掉树根结点） A B C D B C D L E F G H L E F G H I I 前序：B、L、E、C、F、D、G、I、H 中序：L、E、B、F、C、I、G、H、D

54 5、树和森林 3、树、森林的遍历 A B A C L D F B C D E 以 C 为例： 在树中：
树的前序、后序遍历序列和相应的二叉树的前序、中序遍历序列一一对应： 前序序列和对应的二叉树的前序序列完全一致。 E、G：左图的树的根 A，及它的儿子结点 B、C、D 在树的 的前序序列和相应的二叉树中前序序列中的序号。 根 A: 结点 B： 2 2 结点 C： 5 5 结点 D： 7 7 A B A C L D F B C D E 以 C 为例： 在树中： 序号＝ 根节点数 ＋ 第一棵子树的结点数 ＋ 1 ＝ 5 在二叉树中： 序号＝ 根节点数 ＋ 左儿子数＋左儿子子树结点数 ＋ 1 ＝ 5 G L E F G H I H I

55 5、树和森林 3、树、森林的遍历 A B A C L D F B C D E 以 C 为例： 在树中：
树的前序、后序遍历序列和相应的二叉树的前序、中序遍历序列一一对应： 后序序列和对应的二叉树的中序序列完全一致。 E、G：左图的树的根 A，及它的儿子结点 B、C、D 在树的 的后序序列和相应的二叉树的中序序列中的序号。 根 A: 结点 B： 结点 C： 5 5 结点 D： 9 9 A B A C L D F B C D E 以 C 为例： 在树中： 序号＝ 第一棵子树的结点数 ＋ C 的子树的结点数 ＋ 1 ＝ 5 在二叉树中： 序号＝ B 的左子树的结点数 ＋B 的结点数 ＋ C 的左子树结点数 ＋ 1 ＝ 5 G L E F G H I H I 后序：L、E、B、F、C、I、G、H、D、A 中序：L、E、B、F、C、I、G、H、D、A

56 5、树和森林 3、树、森林的遍历 E.g: 3 棵分别以B、 C、D为根的树 A B A 相应的二叉树 C L B C D B C D D
森林的前序、中序（当作后序更好理解）和相应的二叉树的前序、中序遍历序列一一对应 E.g: 3 棵分别以B、 C、D为根的树 A B A 相应的二叉树 C L B C D B C D D F E L E F G H L E F G H G I I I H 注意：本书介绍了森林的后序，一般用的很少。 另外：本书介绍了层次访问，也很简单。只需采用队列，即可实现。

57 6、树的计数 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C 1、二叉树的确定 前序（后序） ＋ 中序 唯一确定一棵二叉树
e.g: A 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C C D、B、E、F 确定过程: 1、 定根 A 2、在中序序列中找到 A 3、中序序列中的 A 的左部为 A 的左子树 上的所有结点， A 的右部为 A 的右子 树中的所有结点。 4、根据 A 的左子树的所有结点的前序序 列确定 A 的左子树的根节点，它是 A 的左儿子。 5、根据 A 的右子树的所有结点的前序序 列确定 A 的右子树的根节点，它是 A 的右儿子。 6、 在左、右子树中反复以上过程。至所有 结点处理完毕。结束 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C A D、E、F B C 前序: B、D、E、F 中序: D、B、E、F A B C E、F D 前序: E、F 中序: E、F

58 6、树的计数 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C 1、二叉树的确定 前序（后序） ＋ 中序 唯一确定一棵二叉树
e.g: A 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C C D、B、E、F 确定过程: 1、 定根 A 2、在中序序列中找到 A 3、中序序列中的 A 的左部为 A 的左子树 上的所有结点， A 的右部为 A 的右子 树中的所有结点。 4、根据 A 的左子树的所有结点的前序序 列确定 A 的左子树的根节点，它是 A 的左儿子。 5、根据 A 的右子树的所有结点的前序序 列确定 A 的右子树的根节点，它是 A 的右儿子。 6、 在左、右子树中反复以上过程。至所有 结点处理完毕。结束 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C A D、E、F B C 前序: B、D、E、F 中序: D、B、E、F A B C 前序: E、F 中序: E、F D E F

59 6、树的计数 1、互不相似的二叉树的棵数的计算 实例： e.g: 当 二叉树的结点个数 n = 3 前序序列为 1、2、3 时 计算要点:
设二叉树的前序的序列 为 1、2、3 ……… n 不同的中序序列的对应 着不同树形的二叉树 不同的中序序列的总数 是不同树形的二叉树的 总和 不同的中序序列在中序 周游时和相应的进出栈 序列一一对应。 不同的进出栈序列的总 数是不同树形的二叉树 的总和 1 1 1 1 1 2 2 2 3 2 2 3 3 3 3 1、进栈 2、进栈 3、进栈 3、出栈 2、出栈 1、出栈 1、进栈 2、进栈 2、出栈 3、进栈 3、出栈 1、出栈 1、进栈 2、进栈 2、出栈 1、出栈 3、进栈 3、出栈 1、进栈 1、出栈 2、进栈 3、进栈 2、出栈 3、出栈 1、进栈 1、出栈 2、进栈 2、出栈 3、进栈 3、出栈

60 6、树的计数 1、互不相似的二叉树的棵数的计算 进出栈序列总数的计算为 2n 个方格中放置 3 个 1 的组合数 － 不合理的序列总数
－ 不合理的序列总数 e.g: n = 3 时，6格放置3个 1 的序列 情况：1 代表进栈，0 表示出栈 实例： e.g: 当 二叉树的结点个数 n = 3 前序序列为 1、2、3 时 1 1 1 1 1 2 2 2 3 2 2 合 理 3 3 3 3 1、进栈 2、进栈 3、进栈 3、出栈 2、出栈 1、出栈 1、进栈 2、进栈 2、出栈 3、进栈 3、出栈 1、出栈 1、进栈 2、进栈 2、出栈 1、出栈 3、进栈 3、出栈 1、进栈 1、出栈 2、进栈 3、进栈 2、出栈 3、出栈 1、进栈 1、出栈 2、进栈 2、出栈 3、进栈 3、出栈 不合理

61 6、树的计数 1、互不相似的二叉树的棵数的计算 进出栈序列总数的计算为 2n 个方格中放置 n 个 1 的组合数 － 不合理的序列总数
－ 不合理的序列总数 e.g: n = 3 时，6格放置3个 1 的序列 情况：1 代表进栈，0 表示出栈 n = 3 时，6 格放置 3 个 1 的序列情况： 3 序列总数 ＝ 2 × 3 3 ＋ 1 不合理的序列总数： 因此，n = 3 时进出栈序列的总数为： 2 × 3 2 × 3 推广到结点数为 n 时的进出栈序列总数： n n + 1 2 × n 2n 合 理 不合理

62 6、树的计数 b0 = 1 bn = bi × b0-i-1 n-1 i= 0 1、互不相似的二叉树的棵数的计算
的总数为： 结点数为 n + 1 时的互不相似的有序树 总数为： n n + 1 2 × n 2 × n n n + 1 2 × n 2 × n 或 或 n n - 1 2 × n 2 × n n n + 1 2 × n 2 × n 2、书上有一种采用递推公式计算的办法，结果一样。 b0 = 1 bn = bi × b0-i-1 n-1 i= 0

63 6、树的计数 2、推论：结点数为 n + 1 时的互不相似的有序树总数和结点数为 n 时的互不相似的二叉树的总数相等。 E.g: n = 4
E.g: n = 4 的所有树 形 1 1 1 3 1 2 1 2 3 2 2 3 2 3 3 1 1 1 3 1 2 1 2 3 2 2 3 2 3 3 1 1 1 1 1 只需考虑 以下二叉 树的棵数即 可 2 2 2 2 2 3 3 3 3 3

64 7、赫夫曼树及其应用 1、最优二叉树（赫夫曼树） G L 2 7 E L E G H H 5 7 5 2 4 4 G H L E 2 4 7
路径长度：结点之间的树枝的总数 树的路径长度：从根到每一结点的路径长度之和 树的带权路径长度：叶子结点的带权路径长度之和。设有 n 片叶子，它们的权值分别 为 w1、w2、…….wn， 相应的路径长度分别为 L1、L2、…….Ln。 则树的带权路径长度可记为： n WPL =∑ wklk k=1 G L 2 7 E L E G H H 5 7 5 2 4 4 WPL=46 WPL=35 G H WPL=36 L E 2 4 7 5 最优二叉树或赫夫曼树：树的带权路径长度 WPL 最小的二叉树。

65 7、赫夫曼树及其应用 1、最优二叉树（赫夫曼树）
赫夫曼算法（产生最优二叉树的算法）的实现： 1、给定一个具有 n 个权值 { w1,w2,………wn } 的结点的集合 F = { T1,T2,………Tn } 。 2、初始时，设 A ＝ F。 3、执行 i = 1 至 n-1 次循环，在每次循环时，做以下事情： 从当前集合中选取权值最小、次最小的两个结点，以 这两个结点作为内部结 点 bi 的左右儿子，bi 的权值为其左右儿子权值之和。在集合中删除这两个权 值最小、次最小的结点。这样，在集合 A 中，结点个数便减少了一个。 e.g: 权值（此处为使用概率）分别为 { 2, 7, 4, 5 } 的结点集合 F＝ { C, A, S, T } 已知。 请利用赫夫曼算法产生最优二叉树。 b3,18 4、A= 1、A= C, 2 A, 7 S, 4 T, 5 b1,6 A, 7 S, 4 C, 2 b2,11 T, 5 3、A= b1,6 A, 7 T, 5 S, 4 C, 2 2、A=

66 7、赫夫曼树及其应用 1 赫夫曼编码： A：0 T：10 C：110 S ：111 2、赫夫曼编码
赫夫曼算法用于通信中的字符的编码。将权值当着使用概率。赫夫曼树的左分支 标记为 1，而右分枝标记为 0；这从根到每一个叶子结点（字符）的路经上标记的字符组成的字 符串，即为该字符的赫夫曼编码。 e.g: 权值（此处为使用概率）分别为 { 2, 7, 4, 5 } 的结点集合 F＝ { C, A, S, T } 已知。 请利用赫夫曼算法产生最优二叉树。 赫夫曼编码： A：0 T：10 C：110 S ：111 赫夫曼编码优点： 占用二进制位少 e.g: 左图发送长度为 n 的字符串，等长表示需 2n 个比特。因共有四个字符，表示每个字符需 二个 比特。 采用赫夫曼编码后，总的比特数 35n/18, 因： A：1*7n /18 T： 2*5n /18 S： 3*4n /18 C：3*2n /18 b1,6 A, 7 S, 4 C, 2 b2,11 T, 5 b3,18 1

67 7、赫夫曼树及其应用 3、 赫夫曼算法的实现：扩充二叉树的声明。
Template < class Type > class ExtBinTree; Template <class Type> class Elelement { friend class ExtBinTree < Type>; private: Type data; // 保存本结点的使用频度和其它数据。 Elelement < Type > * leftChild, * rightChild; }; Template < class Type > class ExtBinTree { public: ExtBinTree ( ) { root = new Elelement < Type>; } ExtBinTree ( ExtBinTree < Type > & bt1, ExtBinTree < Type > & bt2 ) { root->leftChild = bt1.root; root->rightChild = bt2.root; root->data.key = bt1.root->data.key + bt2.root->data.key; } protected: const int DefaultSize = 20; Elelement < Type > * root; }

68 7、赫夫曼树及其应用 3、 赫夫曼算法的实现：赫夫曼树的构造。// 下述函数应作为类 ExtBinTree <Type>的公有成员,否则， Template < class Type > // 无法访问私有成员 DefaultSize。保存使用频度的数组为fr[0]~fr[n-1] void ExtBinTree <Type> :: HuffmanTree ( Type * fr, int n, ExtBinTree < Type > & newtree ) { ExtBinTree < Type > & first, &second; ExtBinTree < Type > Node[ DefaultSize ]; MinHeap < ExtBinTree < Type > > hp; if ( n > DefaultSize ) { cerr << “Size n” << n << “exceed the Boundary of Array ” << endl; return; } for ( int i = 0; i < n; i++ ) { Node[i].root->data.key = fr[i]; Node[i].root->leftChild = Node[i].root->rightChild = NULL; } hp.Minheap ( Node, n ) // 建立具有 n 个结点最小化堆。数组名为 Node。 for ( int i = 0; i < n-1; i++ ) { hp.DeleteMin ( first ); hp.DeleteMin ( second ); newtree = new ExtBinTree < Type > ( first, second ) } hp.Insert ( * newtree ); } // 根据 NO193 的说明，应加 * 号。 } …… n-2 n-1 b1,6 A, 7 S, 4 C, 2 b2,11 T, 5 b3,18