第五章 树及二叉树 1.树的定义和术语 2.二叉树:定义、性质、存储 3.二叉树的遍历 4. 二叉树遍历的迭代器类 *5. 中序穿线树 6. 最优二叉树及其应用 7. 树和森林

树和森林 树：n > 0 个结点的集合，根+其余结点分为 m >= 0 个集合，每一个集合本身又是一棵树（子树） 结点的度：该结点的子树数目 树的度：树中各结点度数的最大值 叶子、父结点、儿子结点、兄弟结点 祖先结点：从根结点到该结点的路径上所有结点 层次、高度：根为1, 依次往下数 有序树：规定所有结点的儿子结点次序，否则为无序树 森林： m >= 0 棵互不相交树的集合 A B C D E F G H I L 高度为 4 、度为 3 的树 其它表示方法： 1. ( A(B(L,E),C(F),D(G(I),H)) 2. 类似于书籍的目录表示法。 高度定义为层数或层数－1，都可以；本书定义为层数。

树和森林 ADT 5.1: 树的ADT 数据及关系: 具有相同数据类型的数据元素或结点的有限集合。树T的二元组形式为： T＝（D，R） 其中D为树T中结点的集合，R为树中结点之间关系的集合。 D＝{Root}∪DF 其中，Root为树T的根结点，DF为树T的根Root的子树集合。 R＝{<Root，ri>，i＝1，2，…，m} 其中，ri是树T的根结点Root的子树Ti的根结点。 操作: Constructor： 前提：已知根结点的数据元素之值。 结果：创建一棵树。 Getroot: 前提：已知一棵树。. 结果：得到树的根结点。 FirstChild： 前提：已知树中的某一指定结点 p。 结果：得到结点 p 的第一个儿子结点。 NextChild： 前提：已知树中的某一指定结点 p 和它的一个儿子结点 u。 结果：得到结点 p 的儿子结点 u 的下一个兄弟结点 v。

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

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

完全二叉树 完全二叉树: 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 个结点的完全二叉树高度为 log2n + 1 证：根据性质 2 和完全二叉树的定义：设其高度为 k 2k-1-1< n <= 2k -1 2k-1 < n + 1 <= 2k 2k-1 <= n < 2k 故：k-1 <= log2n < k ; 原命题得证。

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

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

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

二叉树的顺序存储 特殊情况：若不是完全二叉树，许多数据场为空，不合算。如下例所示： 考虑浪费空间最多的情况，是一种什么情况？ 浪费 2^k - 1 – k 个单元 1 2 3 4 5 6 7 8 9 A B ∧ D H I A B D H I

二叉树的链接存储 data left right data left right Parent 仅定义结点的类型即可。结点之间的关系通过指针实现。 A B C D E F G H I L 标准形式：（二叉链表） data left right 广义标准形式：（三叉链表） data left right Parent

二叉树的链接存储 例： A ∧ B /\ C D E F G

二叉树的ADT template <class Type> class BinaryTree; // 二叉树类 BinaryTree 的向前说明 template <class Type> class BinaryNode { friend class BinaryTree < Type>; public: BinaryNode ( ) : left(NULL), right(NULL) { } // 二叉树结点的构造函数。 BinaryNode ( Type item, BinaryNode < Type> * L = NULL, BinaryNode < Type> * R = NULL ): data(item),left(L), right( R) { } ～BinaryNode ( ) { } Type GetData ( ) const { return data; } // 得到二叉树结点的数据值。 BinaryNode<Type> * GetLeft( ) const { return left;} //得到二叉树结点的左儿子地址。 inaryNode<Type> * GetRight( ) const { return right; } void SetData ( const Type & item ) { data = item; } // 设置二叉树结点的数据值。 void SetLeft (BinaryNode < Type> * L ) { left = L; } // 设置二叉树结点的左儿子地址。 void SetRight (BinaryNode < Type> * R ) { right = R; } // 设置二叉树结点的右儿子地址。

二叉树的ADT template <class Type> class BinaryTree; // 二叉树类 BinaryTree 的向前说明 template <class Type> class BinaryNode { friend class BinaryTree < Type>; public: void PrintPreOrder( ) const; // 按前序打印二叉树的结点的数据值。 void PrintPostOrder( ) const; // 按后序打印二叉树的结点的数据值。 void PrintInOrder( ) const; // 按中序打印二叉树的结点的数据值。 BinaryNode<Type> * Duplicate( ) const; // 复制以本结点为根的子树。 private: BinaryNode < Type> * left , * right ; // 结点的左、右儿子的地址 Type data; // 结点的数据信息 };

二叉树的ADT template <class Type> class BinaryTree { public: BinaryTree( ) : root( NULL) { } // 构造空二叉树 BinaryTree ( const Type & value ) { root = new BinaryNode<Type> ( value ); } ~BinaryTree ( ) { DelTree ( root ); } int IsEmpty ( ) const { return root == NULL; } // 二叉树为空，返回非0，否则为0。 const BinaryNode<Type> * Getroot( )const { return root; } int MakeEmpty ( ) { DelTree( root); root == NULL; } // 使二叉树为空。 const BinaryTree<Type> & operator = ( const BinaryTree<Type> & T); private: BinaryNode<Type> * root; // 二叉树的根结点。 BinaryTree( const BinaryTree<Type> & ); void DelTree( BinaryNode<Type> * T ); }; template <class Type> const BinaryTree<Type> & BinaryTree<Type> :: operator = ( const BinaryTree<Type> & T ) { if ( this != &T ) { DelTree(root); // 其具体实现，见程序5.1。 if ( T.root != NULL ) root = T.root->Duplicate( ); }

二叉树的ADT ·二叉树的 ADT：求二叉树的结点个数和高度以及删除一棵二叉树。 template <class Type> Type Max( const Type u, const Type v ) { if ( u > v ) return u; else return v;} int BinaryNode < Type> :: Size ( const BinaryNode <Type> * T ) const { // 得到以 T 为根的二叉树或子树的结点个数。 if ( T == NULL ) return 0; else return 1 + Size( T->left ) + Size( T->right); } int BinaryNode < Type> :: Height ( const BinaryNode < Type> * T ) const { // 得到以 T 为根的二叉树的高度。 else return 1 + Max( Height( T->left ),Height( T->right));

二叉树的ADT ·二叉树的 ADT：求二叉树的结点个数和高度以及删除一棵二叉树。 template <class Type> void BinaryTree<Type> :: DelTree ( BinaryNode < Type> * T ) { // 删除以 T 为根的二叉树的所有结点。 if ( T != NULL ) { DelTree( T->left); DelTree( T->right); delete T; }

二叉树遍历 R 设 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

二叉树遍历 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

二叉树遍历的迭代器类 二叉树的迭代器：Tree Iterator ADT 5.3: 二叉树的迭代器类。 template <class Type> class TreeIterator { public: TreeIterator ( const BinaryTree < Type > & BT ) : T( BT ), current( NULL) { } virtual ~TreeIterator ( ) { } virtual void First ( ) = 0; // 第一个被访问的结点地址送current virtual void operator ++ ( ) = 0; // 下一个被访问的结点地址送current int operator + ( )const{ return current != NULL;}//当前结点为空吗，非空返回 True const Type & operator ( ) ( ) const; // 返回当前结点指针 current 所指向的结点的数据值。 protected: const BinaryTree <Type > & T; const BinaryNode<Type > * current; // 指向当前结点的指针。 private: TreeIterator ( const TreeIterator & ) { } const TreeIterator & operator = ( const TreeIterator & ); }; template <class Type> const Type & TreeIterator <Type> :: operator ( ) ( ) const { Exception( current == NULL, “This node is NULL!” ); return current->GetData( ); }

非递归前序遍历 1、根结点进栈 2、结点出栈，被访问 3、结点的右、左儿子（非空）进栈 4、反复执行 2、3 ，至栈空为止。 e.g: 前序的程序实现（非递归）： 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。找不到结束。

前序遍历的迭代器 遍历二叉树：Tree Iterator ：前序的实现。 template <class Type> class Preorder : public TreeIterator < Type > { public: Preorder( const BinaryTree < Type > & R ); ~Preorder( ) { } void First( ); void operator ++ ( ); void Preorder_NLR ( ); protected: Stack < const BinaryNode <Type > * > s; }; template <class Type> Preorder<Type> :: Preorder( const BinaryTree <Type> & R ) : TreeIterator<Type > ( R ) { s.Push( T.Getroot( ) ); } void Preorder <Type> :: First ( ) { s.MakeEmpty ( ); if ( T.Getroot( ) ) s.Push( T.Getroot( ) ); operator ++( ); } //堆栈清空。若二叉树T非空，则根结点进栈，并得到当前结点。

前序遍历的迭代器 template <class Type> 遍历二叉树：Tree Iterator ：前序的实现。 template <class Type> void Preorder <Type> :: operator ++ ( ) { if ( s.IsEmpty() ) { if ( current == NULL ) { cerr << “Advanced past end ” << endl; exit( 1 ) }; current = NULL; return; } current = s.Top( ); s.Pop( ); // 得到当前结点的地址，并进行出栈操作。 if ( current ->GetRight ( ) != NULL ) s.Push( current->GetRight( ) ); //非空右儿子进栈。 if ( current ->GetLeft ( ) != NULL ) s.Push( current->GetLeft( ) ); //非空左儿子进栈。 } void Preorder < Type > :: Preorder_NLR ( ) { First( ); // 将当前指针 current 指向根结点。 while( operator +( ) ) { // 当前指针 current 非空时继续执行。 cout << operator()() << endl; // 输出当前结点的数据场之值。 operator ++( ); // 使前序次序下的下一个结点成为当前结点。

非递归后序遍历 A e.g: L C D E 分析：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。

非递归后序遍历 A B C D E 后序遍历时的实现实例；注意堆栈中保存的是当前结点的祖先。 <A> <A> 1     <A> <A> 1 <A> 1 <D> <A> 1 <D> 1 <A> 1 A <B> <B> 1 <B> 2 <B> 2 (1) (2) (3) (4) (5) B C <D> 2 <A> 1 <A> 1 <A> 1 <A> 2 <E> <A> 2 <B> 2 <B> 2 <C> <C> 1   (6) (7) (8) (9) (10) D E <E> 1 <A> 2 <A> 2 <E> 2 <A> 2 <A> 2 <A> 2     <C> 1 <C> 1 <C> 1 <C> 2 (11) (12) (13) (14) (15)

后序遍历的迭代器 遍历二叉树：Tree Iterator 后序的实现 template <class Type> struct StNode { const BinaryNode<Type > * Node; int TimesPop; StNode( const BinaryNode <Type > * N = NULL ): Node(N), TimesPop(0) { } }; template <class Type> class Postorder : public TreeIterator < Type > { public: Postorder( const BinaryTree < Type > & R ); ~Postorder( ) { } void First( ); // 后序遍历时的第一个结点的地址。 void operator ++ ( ); // 后序遍历时的下一个结点的地址。 protected: Stack < StNode<Type> > s; template <class Type> Postorder<Type> :: Postorder(const BinaryTree<Type> & R) : TreeIterator<Type> (R) { s.Push( StNode<Type>( T.Getroot( ) ) ); } void Postorder <Type> :: First ( ) { // 得到第一个访问的结点地址 s.MakeEmpty ( ); if ( T.Getroot( ) ) s.push ( StNode<Type>( T.Getroot( ) ); operator ++ ( ); } // 根结点地址及标志 0 进栈，去寻找第一个被访问的最左方的叶子。

后序遍历的迭代器 遍历二叉树：Tree Iterator 后序的实现 template <class Type> void Postorder <Type>:: operator ++ ( ) { if ( s.IsEmpty() ) { // 当栈空且 current 也为空时，遍历结束。 if ( current == NULL ) { cerr << “Advanced past end ” << endl; exit( 1 ); } current = NULL; return; } // 置当前指针为空，结束。 StNode<Type> Cnode; for ( ; ; ) { Cnode = s.Top( ); s.Pop( ); if ( ++ Cnode.TimePop == 3 ) { current = Cnode.Node; return; } //其左右子树处理完毕,该结点可访问。 s.Push( Cnode ); if ( Cnode. TimesPop == 1 ) // 转向访问左子树。 { if ( Cnode.Node -> GetLeft ( ) != NULL ) // 有左儿子，进栈。 s.Push(StNode<Type>( Cnode.Node -> GetLeft ( ) ) ); } else { // Cnode.TimePop == 2 访左结束，转向访问右子树。 if ( Cnode.Node -> GetRight ( ) != NULL ) s.Push(StNode<Type>( Cnode.Node -> GetRight ( ) ) );

非递归中序遍历 中序的程序实现： 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

中序遍历的迭代器 程序 5.5: 中序遍历迭代器类 template <class Type> class Inorder : public Postorder < Type > { public: Inorder( const BinaryTree < Type > & R ) : Postorder<Type> (R) { } void operator ++ ( ); // 中序时的下一个结点的地址。 }; template <class Type> void Inorder<Type>:: operator ++ ( ) { if ( s.IsEmpty() ) { // 当栈空且 current 也为空时，遍历结束。 if ( current == NULL ) {cerr<< “Advanced past end ”<<endl;exit(1);} Cnode = NULL; return; } // 置当前指针为空，结束。 StNode<Type> Cnode; for ( ; ; ) { current = s.Top( ); s.Pop( ); if ( ++Cnode. TimesPop == 2 ) // 其左子树处理完毕,该结点可访问。 { current = Cnode.Node; if ( Cnode.Node -> GetRight ( ) != NULL ) // 有右儿子，进栈。 s.Push(StNode<Type>( Cnode.Node->GetRight() ) ); return; } s.Push( Cnode); if ( Cnode.Node -> GetLeft ( ) != NULL ) s.Push(StNode<Type>( Cnode.Node->GetLeft() ) );  

中序穿线树 B C D E L A X W B C D E L A X W e.g: n = 8 的二叉树 扩展二叉树 简单证明：设二叉树中结点的总数为 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 个空指针场？ 中序穿线树 后序穿线树

中序穿线树的链接存储 e.g: n = 6 的二叉树 无前驱结点 无后继结点 A A 中序穿线树 L C L C D D B E B E · 中序穿线树（中序中序穿线树）的实现： 在二叉树的结点的标准形式中，增加两个标志域，用于区别是否是穿线。如下所 示: ( 注意：在顺序存储一颗二叉树时，可不必使用额外的空间；见下页） 其中 data 为数据场， leftThread = 0 时，leftchild 场指向本结点的真正的左儿子 leftThread = 1 时，leftchild 场指向本结点的按中序遍历序列的前驱结点(穿线) rightThread = 0 时，rightchild 场指向本结点的真正的右儿子 rightThread = 1 时，rightchild 场指向本结点的按中序遍历序列的后继结点(穿线) leftchild leftThread data rightThread rightright e.g: n = 6 的二叉树 无前驱结点 无后继结点 A A 中序穿线树 L C L C D D B E B E

中序穿线树的链接存储 1:穿线 0:实际儿子 A L C 表示 D B E · 中序穿线树中的结点的数据结构： 无前驱结点 无后继结点 A Root: 根结点指针 无前驱结点 无后继结点 A A L C 表示 D B E L 1 C 1:穿线 0:实际儿子 ∧ 1 B 1 1 E 1 1 D 1 ∧

中序穿线树的顺序存储 data left right A 2 5 L 3 4 B 0 -2 E -2 -1 C 0 6 D 7 0 中序穿线树的结点的顺序存储结构： B D L A X W 空 C E 2 3 4 8 7 6 5 1 C 0 6 A 2 5 L 3 4 B 0 -2 X -7 -6 W -5 8 D 7 0 E -2 -1 data left right

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

中序穿线树的中序遍历 template <class Type> · 中序穿线树遍历的实现算法。 template <class Type> int InorderThreadTree<Type> :: First ( ) { current = root; if ( !current ) return current;//为0是中序穿线二叉树空的标志。 while( arr[current].left >0 ) current = arr[current].left; return current; // 在中序次序下第一个被访问的结点的下标地址。 } int InorderThreadTree<Type> :: Next ( ) { aftcurrent = arr[current].right; if ( aftcurrent <= 0 ) { current = - aftcurrent; return current; } // 为0是中序遍历结束的标志，否则是中序次序下的下一个结点的地址。 while( arr[aftcurrent].left > 0 ) aftcurrent = arr[aftcurrent].left; current = aftcurrent; return current; //在中序次序下的下一个被访问的结点的地址。 void InorderThreadTree<Type> :: Inorder ( ) { int p = First( ); while( p != 0 ) { cout << arr[p].data << endl; p = Next( ); } return; root A L C D B E 无后继结点

中序穿线树 E E Q A U C 122 S D B D 250 99 300 200 110 E E Q A 105 230 U C · 中序穿线树在中序穿线树上插入新的结点的操作 本书中建立的实际上是中序穿线二叉排序树，所以新插入结点时必须寻找他的插入位置，即其父结点。考虑新插入的结点为父结点的右儿子的情况。新插入的结点为父结点的左儿子的情况，类似。 E E Q A U C 122 S D B D 250 99 新插入结点 D 作为叶子结点，其父结点的右儿子指针场应为非正数。 新插入结点 D 作为叶子结点，其父结点的左儿子指针场应为非正数。 300 200 110 E E Q A 105 230 U C 216 S B D D

中序穿线树 template <class Type> Istream & operator >> (istream & in, InorderThreadTree<Type> & x){ int size, j, k = 2;Type ele; cout << “Enter size of your InorderThreadTree array! ” << endl; in >> size; if (size > x.MaxSize ) { cout << “Error: out of spaces!”; return in; } cout << “ Enter data of every element one by one!” << endl; in >> ele; if (ele == x.flag) { cout << “Input data end!” << endl; return in; } x.arr[1].setdata (ele); x.root = 1; // 根结点单独生成。 while ( in >> ele, ele != x.flag) { j = x.root; x.arr[k].setdata (ele); while(1 ) { if ( x.arr[k].data < x.arr[j].data ) if ( x.arr[j].left > 0) j = x.arr[j].left; else { x.arr[k].left = x.arr[j].left; x.arr[k].right = -j; x.arr[j].left = k; break; } // 新结点 k 插入后为结点 j 的左儿子，是叶子。 else if ( x.arr[j].right > 0) j = x.arr[j].right; else { x.arr[k].right = x.arr[j].right; x.arr[k].left = -j; x.arr[j].right = k; break; } // 新结点 k 插入后为结点 j 的右儿子，是叶子。 } k++; return in;

最优二叉树 G L 2 7 E L E G H H 5 7 5 2 4 4 G H L E 2 4 7 5 路径长度：结点之间的树枝的总数 树的路径长度：从根到每一结点的路径长度之和 树的带权路径长度：叶子结点的带权路径长度之和。设有 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 最小的二叉树。

赫夫曼算法 e.g: 权值（此处为使用概率）分别为 { 2, 7, 4, 5 } 的结点集合 F＝ { C, A, S, T } 已知。 赫夫曼算法（产生最优二叉树的算法）的实现： 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=

赫夫曼编码 赫夫曼算法用于通信中的字符的编码。权值为使用概率。赫夫曼树的左分支 标记为 0，而右分枝标记为 1；这从根到每一个叶子结点的路经上标记的字符组成的字符串，即为该字符的赫夫曼编码。 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

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

最小化堆的最小元素 root 7 16 62 24 50 88 77

最小化堆的顺序存储 [ 1 ] [ 2 ] 7 [ 3 ] 16 [ 4 ] 62 [ 5 ] 24 [ 6 ] 50 [ 7 ] 88 root 7 16 62 24 50 88 77 7 1 16 2 62 3 50 5 77 7 24 4 88 6

建堆的复杂性 [ 1 ] [ 2 ] 7 [ 3 ] 16 [ 4 ] 62 [ 5 ] 24 [ 6 ] 50 [ 7 ] 88 77 建堆的时间耗费：比较次数 - 4n 次 O(n) 级 （课本第 241页） [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] 7 16 62 24 50 88 77 root 7 1 16 2 62 3 50 5 77 7 24 4 88 6

建最小化堆 数组 h [ 1 ] [ 2 ] 50 [ 3 ] 16 [ 4 ] 62 [ 5 ] 24 [ 6 ] 7 [ 7 ] 88 77 root 符合堆的定义，不需调整。即最小化小堆已符合定义。建立的第一个小堆的堆顶的下标为 n/2 50 1 16 2 62 3 7 5 77 7 24 4 88 6 叶子结点，符合堆的的定义。

建最小化堆 数组 h [ 1 ] [ 2 ] 50 [ 3 ] 16 [ 4 ] 62 [ 5 ] 24 [ 6 ] 7 [ 7 ] 88 77 不合堆的定义，需调整。建立以 L[ 2 ] 为堆顶的正确的最小化小堆。 root 50 1 16 2 62 3 7 5 77 7 24 4 88 6

建最小化堆 数组 h [ 1 ] [ 2 ] 50 [ 3 ] 7 [ 4 ] 62 [ 5 ] 24 [ 6 ] 16 [ 7 ] 88 77 不合堆的定义，需调整。建立以 L[ 2 ] 为堆顶的正确的最小化小堆。 root 50 1 7 2 62 3 16 5 77 7 24 4 88 6

建最小化堆 数组 h [ 1 ] [ 2 ] 50 [ 3 ] 7 [ 4 ] 62 [ 5 ] 24 [ 6 ] 16 [ 7 ] 88 不合堆的定义，需调整。建立以 L[ 1 ] 为堆顶的正确的最小化堆。 数组 h 50 7 62 24 16 88 77 root 50 1 7 2 62 3 16 5 77 7 24 4 88 6

建最小化堆 数组 h [ 1 ] [ 2 ] 7 [ 3 ] 50 [ 4 ] 62 [ 5 ] 24 [ 6 ] 16 [ 7 ] 88 不合堆的定义，需调整。建立以 L[ 1 ] 为堆顶的正确的最小化堆。 数组 h 7 50 62 24 16 88 77 root 7 1 50 2 62 3 16 5 77 7 24 4 88 6

建堆的复杂性 时间耗费的代价：建堆的时间耗费 ＋ 排序的时间耗费 建堆的时间耗费：设树根处于第 1 层，该堆共有 h 层。建堆从第 h-1 层开始进行。只 要知道了每一层的结点数（建的小堆的个数），和每建一个小堆所 需的比较次数，就可以求得建堆的时间耗费。 建的小堆的性质：第 i 层上小堆的个数 ＝ 第 i 层上结点的个数 ＝ 最多 2i-1 第 i 层上小堆的高度 ＝ h-i+1 建第 i 层上每个小堆最多所需的比较次数 ＝ 2×（h-i）次 建堆的时间耗费： T(n) <= ∑ 2i-1×(h-i)×2 = ∑ 2i×(h-i) = ∑ 2h-j×j = 2h ∑ j/2j 注意：即使是 高度为 h 的完全的二叉树，满足以下式子： 2h－1 <= n <= 2h-1 故： 2h <= 2n 又： ∑ j/2j < 2 所以：建堆的时间复杂性为 4n=O(n) 级 1 1 h-1 i=h-1 i=h-1 j=1 10 30 40 60 12 70 8 6 2 3 1 7 4 5 3=h h-1 j=1 ∞ j=1

最小化堆的ADT template < class EType> class MinHeap { public: MinHeap( int sz ); // 堆的构造函数。 MinHeap( EType arr[ ], int n, int sz ); // 带有堆的初始值的构造函数。 ~MinHeap( ) {delete [ ] heap; } // 堆的析构函数。 void BuildHeap( int j ); // 建立最小化堆。 void Insert( const EType & x ); // 结点插入最小化堆中的堆尾，并调整为最小化堆。 void DeleteMin( EType & x ) ; // 删除最小化堆中的最小元素，即：堆顶结点。 // 删除之后，仍应调整为最小化堆。 int IsEmpty( ) const { return CurrentSize == 0; } // 判堆空吗？ int IsFull( ) { return CurrentSize == MaxSize; } // 判堆满吗，即单元用光吗？ void Clear( ) { CurrentSize = 0; } // 置堆空，堆中没有一个元素。 private: EType * heap; // 保存堆的数组，即堆的存储空间。 int CurrentSize; // 堆的当前结点的个数。 int MaxSize; // 数组可以保存的结点的最大数目，即容量。 void SiftDown( int j ); };   

最小化堆的ADT template < class EType> MinHeap<EType> :: MinHeap( int sz ) { heap = new EType[sz + 1]; CurrentSize = 0; MaxSize = sz; } // 建立存储堆的数组 heap[1]至heap[sz]，此时仍是空的堆。sz 为数组的最大容量。   template<class EType> MinHeap<EType> :: MinHeap( EType arr[ ], int n, int sz ) { Exception( sz < n, “MaxSize is less then CurrentSize!”); CurrentSize = n; heap = new EType[ sz + 1]; for ( int j = 1; j<=n; j++ ) heap[j] = arr[j]; // 对当前最小化堆进行赋值。 BuildHeap( ); } // 建立的最小化堆是heap[1]至heap[n]。sz 为数组的最大容量。  

最小化堆的ADT 建立最小化堆的主要函数 SiftDown 及 BuildHeap 的实现： template < class EType> void MinHeap<EType> :: SiftDown( int j ) { // heap[1], …,heap[n]为存储堆的数组。heap[0]不用。 int MinSon; // 用于记录小儿子的下标地址。 heap[0] = heap[j]; // 暂时存放 heap[ j ] 至 heap[ 0 ]。 for ( ; j*2 <= CurrentSize; j = MinSon) { MinSon = 2 * j; if ( MinSon != CurrentSize && heap [MinSon+1 ] < heap [MinSon ] ) MinSon++; if ( heap[MinSon] < heap[0] ) heap[j] = heap[MinSon]; else break; } heap [j ] = heap[0]; // 取回 heap[ j ] 之值。   void MinHeap<EType> :: BuildHeap( ) { for ( int j = CurrentSize/2; j > 0; j-- ) SiftDown(j);

最小化堆 利用最小化堆挑选最小和次最小的结点 (总共n-1趟) 的总的代价分析： O ( n logn ) 考虑最大比较次数： 3 log(n-1) + 5( log(n-2) + log(n-2) +…… log2 ) 考察：5log(n-1) + 5( log(n-2) + log(n-2) +…… log2 ) － 2log(n-1) 的时间代价即可。 该代价如何得出，请看下例。注意：以下实例是以一趟挑选最小和次最小的结点为例的。 以n=8 个结点集合为例，它们的权值分别为：{91，36，24，85，47，30，53，12} 选出最小结点、删除 调整剩下的结点仍成为最小化堆 创建的最小化堆 1 1 代价2 log(n-1) 1 12 91 24 2 3 2 3 2 3 36 24 36 24 36 30 4 5 6 7 4 5 6 7 4 5 6 7 85 47 30 53 85 47 30 53 85 47 91 53 8 8 1 8 最大的代价 log (n-1) 91 12 53 1 12 2 3 30 1 36 30 2 3 30 36 53 2 3 4 5 6 7 36 53 85 47 91 24 4 5 6 7 85 47 91 24 4 5 6 7 8 8 85 47 91 36 12 代价2 log(n-2) 12

最小化堆 在赫夫曼算法中，利用最小化堆挑选最小值和次最小值的结点的总的代价的说明。n=8 个结点集合为 例，它们的权值分别为：{ 91，36，24，85，47，30，53，12 } 趟数 选最小值之后进行 选次最小值之后 得到中间结点 加入中间结点后 调整的比较次数 调整的比较次数 后结点总数 调整的比较次数 1、 2 log (n-1) 2 log (n-2) (n-1) log (n-1) 2、 2 log (n-2) 2 log (n-3) (n-2) log (n-2) n-2、 2 log 2 仅一个结点 2 log 2 无需比较 n-1、 无需比较 无需比较 1 只有一个结点

最小化堆 求 y=logx 的积分的示意图 利用最小化堆挑选最小和次最小的结点的代价分析： O ( n logn ) 只要求得 log(n-1) + log(n-2) + log(n-2) +…… log2 的级别为 O ( n logn )即可。 Y轴 y=logn 2 求 y=logx 的积分的示意图 1 1 X轴 1 2 3 4 n-1 n n-1 n log(n-1)! = Σ logj ≤ logx dx     不难求出上述积分的值为：nlogn-nloge+2loge - 2 ；命题得证。 j=2 2

赫夫曼算法的实现 0 1 2 …….n…… 2n-2 2n-1 赫夫曼算法的实现：使用最小化堆挑选出最小的结点。 template <class Type> void BestBinaryTree ( Type weight[ ], int n, node<Type> BestBinaryTree[ ], int m) { // weight[1] 到weight[n]保存权值， weight[0]不用。BestBinaryTree[1]到 // BestBinaryTree[2n-1]保存最优二叉树，BestBinaryTree[0 ]不用，m应为2n-1。 node< Type > * minptr = new node<Type>; // 暂存最小值用。 MinHeap< node < Type > > MinHp(n); //建立最小化堆，容量为n个单元，0 号单元不用。 int j,k = m; for ( j = 1; j <= n; j++ ) { minptr->setdata( weight[j]); minptr->setorder(j); MinHp.Insert( *minptr); } for ( j = n+1; j <= m; j++ ) { MinHp.DeleteMin ( *minptr ); BestBinaryTree[k] = *minptr; MinHp.DeleteMin ( *minptr ); BestBinaryTree[k-1] = *minptr ; minptr->setdata(BestBinaryTree[k].data + BestBinaryTree[k-1].data, k, k -1 ); minptr->setorder(); k -= 2; MinHp.Insert( *minptr ); // 内部结点 bj 插入最小化堆。 } MinHp.DeleteMin ( *minptr ); BestBinaryTree[1] = *minptr; // 插入根结点。 b1,6 A, 7 S, 4 C, 2 b2,11 T, 5 b3,18 0 1 2 …….n…… 2n-2 2n-1

赫夫曼编码 b1,6 A, 7 S, 4 C, 2 b2,11 T, 5 b3,18 堆栈 1 1 1 <b1> 1 1 1 <b1> <b2> <b3> 注意：访问到叶子C时，只需检查C和b1、b1和b2、b2和b3之间的关系，即可得出叶子C的赫夫曼编码110。 算法：在后序遍历的程序基础上进行改进，注意 到当访问到叶子结点时，其父结点全部 在堆栈中，通过堆栈中结点之间的关系 ，可以方便地得到该叶子结点的赫夫曼编 码，如右图。

附：自上而下建堆法简介 数组 h [ 1 ] [ 2 ] 50 [ 3 ] 16 [ 4 ] 62 [ 5 ] 24 [ 6 ] 7 [ 7 ] 数组 h 50 16 62 24 7 88 77 root 50 1 16 2

附：自上而下建堆法简介 数组 h [ 1 ] [ 2 ] 16 [ 3 ] 50 [ 4 ] 62 [ 5 ] 24 [ 6 ] 7 [ 7 ] 数组 h 16 50 62 24 7 88 77 root 16 1 50 2

附：自上而下建堆法简介 数组 h [ 1 ] [ 2 ] 50 [ 3 ] 16 [ 4 ] 62 [ 5 ] 24 [ 6 ] 7 [ 7 ] 数组 h 50 16 62 24 7 88 77 root 16 1 50 2 62 3

附：自上而下建堆法简介 数组 h [ 1 ] [ 2 ] 16 [ 3 ] 50 [ 4 ] 62 [ 5 ] 24 [ 6 ] 7 [ 7 ] 数组 h 16 50 62 24 7 88 77 root 16 1 50 2 62 3 24 4

附：自上而下建堆法简介 数组 h [ 1 ] [ 2 ] 16 [ 3 ] 24 [ 4 ] 62 [ 5 ] 50 [ 6 ] 7 [ 7 ] 数组 h 16 24 62 50 7 88 77 root 16 1 24 2 62 3 50 4

附：自上而下建堆法简介 数组 h [ 1 ] [ 2 ] 16 [ 3 ] 24 [ 4 ] 62 [ 5 ] 50 [ 6 ] 7 [ 7 ] 数组 h 16 24 62 50 7 88 77 root 16 1 24 2 62 3 7 5 50 4

附：自上而下建堆法简介 数组 h [ 1 ] [ 2 ] 16 [ 3 ] 7 [ 4 ] 62 [ 5 ] 50 [ 6 ] 24 [ 7 ] 数组 h 16 7 62 50 24 88 77 root 16 1 7 2 62 3 50 4 24 5

附：自上而下建堆法简介 数组 h [ 1 ] [ 2 ] 7 [ 3 ] 16 [ 4 ] 62 [ 5 ] 50 [ 6 ] 24 [ 7 ] 数组 h 7 16 62 50 24 88 77 root 7 1 16 2 62 3 24 5 50 4

附：自上而下建堆法简介 数组 h [ 1 ] [ 2 ] 7 [ 3 ] 16 [ 4 ] 62 [ 5 ] 50 [ 6 ] 24 [ 7 ] 数组 h 7 16 62 50 24 88 77 root 7 1 16 2 62 3 24 5 50 4 88 6

附：自上而下建堆法简介 数组 h [ 1 ] [ 2 ] 7 [ 3 ] 16 [ 4 ] 62 [ 5 ] 50 [ 6 ] 24 [ 7 ] 数组 h 7 16 62 50 24 88 77 root 7 1 16 2 62 3 24 5 77 7 50 4 88 6

附：自上而下建堆法简介 求 y=logx 的积分的示意图 利用自上而下法建立最小化堆得代价分析： O ( n logn ) 考虑最大比较次数： log2 + log3 + …… log(n-1) + logn 考察： log2 + log3 + …… log(n-1) + logn 的时间代价级别为O ( n logn )。 Y轴 y=logn 2 求 y=logx 的积分的示意图 1 1 X轴 1 2 3 4 n n+1 n n+1 log(n!) = Σ logj ≤ logx dx     不难求出上述积分的值为：(n+1)log(n+1)-(n+1)loge + 2loge - 2 ； 它是O ( n logn ) 的。 j=2 2

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

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

树和森林与二叉树的转换 树转换成相对应的二叉树： 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

树和森林与二叉树的转换 森林转换成相对应的二叉树： 增加一个虚拟的根结点，它的儿子为各棵树的根。 那么，就变成了树转换成二叉树的问题。 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

树和森林与二叉树的转换 森林转换成相对应的二叉树： 增加一个虚拟的根结点，它的儿子为各棵树的根。 那么，就变成了树转换成二叉树的问题。 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

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

森林的前序、中序遍历 前序遍历类似于树的前序遍历。增加一个虚拟的根结点，它的儿子为各棵树的 根。那么对这棵树进行前序遍历，即得到森林的前序序列（不含树根结点） 中序遍历类似于树的后序遍历。增加一个虚拟的根结点，它的儿子为各棵树的 根。那么对这棵树进行后序遍历，即得到森林的中序遍历（去掉树根结点） 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

树的遍历 A B A C L D F B C D E 以 C 为例： 在树中： 序号＝ 根节点数 ＋ 第一棵子树的结点数 ＋ 1 ＝ 5 树的前序、后序遍历序列和相应的二叉树的前序、中序遍历序列一一对应： 前序序列和对应的二叉树的前序序列完全一致。 例：左图的树的根 A，及它的儿子结点 B、C、D 在树的 的前序序列和相应的二叉树中前序序列中的序号。 根 A: 1 1 结点 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

树的遍历 A B A C L D F B C D E 以 C 为例： 在树中： 树的前序、后序遍历序列和相应的二叉树的前序、中序遍历序列一一对应： 后序序列和对应的二叉树的中序序列完全一致。 E、G：左图的树的根 A，及它的儿子结点 B、C、D 在树的 的后序序列和相应的二叉树的中序序列中的序号。 根 A: 10 10 结点 B： 3 3 结点 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

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

二叉树的确定 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C 前序（后序） ＋ 中序 唯一确定一棵二叉树 例： 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

二叉树的确定 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C 二叉树的确定 前序（后序） ＋ 中序 唯一确定一棵二叉树 例: 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

树的计数 互不相似的二叉树的棵数的计算 例： 当 二叉树的结点个数 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、进栈 3、出栈 2、出栈 1、进栈 1、出栈 2、进栈 2、出栈 3、进栈 3、出栈

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

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

树的计数 b0 = 1 bn = bi × bn-i-1 n-1 i= 0 互不相似的二叉树的棵数的计算 结点数为 n 时的互不相似的二叉树 的总数为： 结点数为 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 一种采用递推公式计算的办法，结果一样。 b0 = 1 bn = bi × bn-i-1 n-1 i= 0

树的计数 推论：结点数为 n + 1 时的互不相似的有序树总数和结点数为 n 时的互不相似的二叉树的总数相等。 例: n = 4 的所有树 例: 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