树及二叉树.pdf

《树及二叉树.pdf》由会员分享，可在线阅读，更多相关《树及二叉树.pdf（89页珍藏版）》请在三一文库上搜索。

1、1 物料管理物料管理 ALDS 1 Algorithms and DataStrucstures:Trees 5.1 树的定义和术语树的定义和术语 5.2 二叉树二叉树: :定义、性质、存储定义、性质、存储 5.3 二叉树的遍历二叉树的遍历 5.4 二叉树遍历的迭代器类二叉树遍历的迭代器类 5.5 中序穿线树中序穿线树 5.6 最优二叉树及其应用最优二叉树及其应用 5.7 树和森林树和森林 目录目录 第五章第五章 树及二叉树树及二叉树 2 物料管理物料管理 ALDS 2 Algorithms and DataStrucstures:Trees 1、树、森林的概念、树、森林的概念 基本概念基本概

2、念 树：树：n o 个结点的集合，根、其余结点分为个结点的集合，根、其余结点分为 m = 0 个集合，每一个集合本身又是一个集合，每一个集合本身又是一 棵树（子树）棵树（子树） 度、叶子、父结点、儿子结点、祖先结点、层次、高度度、叶子、父结点、儿子结点、祖先结点、层次、高度(从根或子树的根向下看从根或子树的根向下看) 有序树及无序树有序树及无序树 森林森林 m = 0 棵互不相交树的集合棵互不相交树的集合 其它表示方法：其它表示方法： ( A(B(L,E),C(F),D(G(I),H) 还有其它表示方法，如：类似于书籍的目录表示法。还有其它表示方法，如：类似于书籍的目录表示法。 A B C D

3、 E F G H I L E、G：高度为高度为 4 、度为、度为 3 的树的树 高度定义为层数或层数高度定义为层数或层数1，都可以；本书定义为层数。，都可以；本书定义为层数。 3 物料管理物料管理 ALDS 3 Algorithms and DataStrucstures:Trees 1、树、森林的概念、树、森林的概念 树的树的 ADT ADTADT 5 5. .1 1: : 树的树的ADTADT 数据及关系数据及关系: : 具有相同数据类型的数据元素或结点的有限集合。树T的二元组形式为： T（D，R） 其中D为树T中结点的集合，R为树中结点之间关系的集合。 DRootDF 其中，Root为树

4、T的根结点，DF为树T的根Root的子树集合。 R，i1，2，m 其中，ri是树T的根结点Root的子树Ti的根结点。 操作操作: : Constructor： 前提：已知根结点的数据元素之值。 结果：创建一棵树。 Getroot: 前提：已知一棵树。. 结果：得到树的根结点。 FirstChild： 前提：已知树中的某一指定结点 p。 结果：得到结点 p 的第一个儿子结点。 NextChild： 前提：已知树中的某一指定结点 p 和它的一个儿子结点 u。 结果：得到结点 p 的儿子结点 u 的下一个兄弟结点 v。 4 物料管理物料管理 ALDS 4 Algorithms and DataSt

5、rucstures:Trees E、G：结点总数为：结点总数为 3 时的所有二叉树的时的所有二叉树的 树的形状树的形状 2、二叉树、二叉树 1、定义、定义 空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树。空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树。 和树的区别：可为空和树的区别：可为空 左右子树有序，不可颠倒左右子树有序，不可颠倒 B C D E F L E、G：二叉树：二叉树 5 物料管理物料管理 ALDS 5 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 2、性质：、性质： 性质性质1：在二叉树的第：在二叉树的第

6、i 层上至多有层上至多有 2 i-1个结点个结点 B C D E F L A 1层：结点个数层：结点个数 21-1=20 个个 2层：结点个数层：结点个数 22-1=21 个个 3层：结点个数层：结点个数 23-1=22 个个 证：证：k = 1 时成立，设时成立，设 k = i-1 时成立时成立 则当则当 k = i 时时在二叉树的第在二叉树的第 i 层上至多有层上至多有 2 i-1-1 * 2 = 2 i-1 个结点个结点 性质性质2：高度为：高度为 K 的的二叉树至多有二叉树至多有2 k- 1 个结点个结点 证：利用性质证：利用性质 1 ，将第，将第 1 层至第层至第 k 层的最多的结点

7、数进行相加：层的最多的结点数进行相加： 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+2n2； 原命题得证。原命题得证。 C E F L A 6 物料管理物料管理 ALDS 6 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 B C D E F L A P S Q

8、R U B C D E F L A P S Q R X U W V 满二叉树满二叉树: 每层结点每层结点 数最多数最多 完全二叉树完全二叉树: 1、满二叉树、满二叉树 2、从满二叉树、从满二叉树 最底层从右向左最底层从右向左 依次去掉若干结依次去掉若干结 点形成的点形成的 性质性质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 ;

9、原命题得证。原命题得证。 7 物料管理物料管理 ALDS 7 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 性质性质5：对一棵有：对一棵有 n 个结点的完全二叉树按照从第一层（根所在的层次个结点的完全二叉树按照从第一层（根所在的层次到最后一层，并且到最后一层，并且 每一层都按照从左到右的次序进行编号。根结点的编号为每一层都按照从左到右的次序进行编号。根结点的编号为 1，最后一个结点的编号，最后一个结点的编号 为为 n。 1：对任何一个编号为对任何一个编号为 i 的结点而言，它的左儿子的编号为的结点而言，它的左儿子的编号为 2i( 若若 2i =

10、n) ,而右儿子的而右儿子的 编号为编号为 2i+1(若若 2i +1 = n)。 2：对任何一个编号为对任何一个编号为 j 的结点而言，它的父亲结点的的编号为的结点而言，它的父亲结点的的编号为 j/2 。根结点无父结根结点无父结 点。点。 证：证： B C D E F L P S Q R U 1 2 7 3 5 6 8 4 9 10 11 12 A 8 物料管理物料管理 ALDS 8 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 3、二叉树的存储结构：、二叉树的存储结构： 顺序存储结构：顺序存储结构： 一般情况：一般情况： A B C D E

11、F G H I L A 1 -1 B 9 2 C 5 3 D 6 -1 E -1 -1 F -1 -1 G 8 7 H -1 -1 I -1 -1 L -1 4 0 1 2 3 4 5 6 7 8 9 right left data 应用范围：适用于二叉树上的结点个数已知，或不支持动态存储分配的高级语言。应用范围：适用于二叉树上的结点个数已知，或不支持动态存储分配的高级语言。 9 物料管理物料管理 ALDS 9 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 3、二叉树的存储结构：、二叉树的存储结构： 顺序存储结构：顺序存储结构： 特殊情况：特殊情

12、况： 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 0 1 2 3 4 5 6 7 8 9 10 right left data 应用范围：适用于完全二叉树，且结点个数已知。应用范围：适用于完全二叉树，且结点个数已知。 D C G E F B A H I L 10 物料管理物料管理 ALDS 10 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 3、二叉树的存储结构：、二叉树的存储结构： 顺序存储结构：顺序存储结构： 特殊情况：若不是完全二叉树，许多数据场为空，不合算。如下

13、例所示：特殊情况：若不是完全二叉树，许多数据场为空，不合算。如下例所示： 考虑浪费空间最多的情况，是一种什么情况？考虑浪费空间最多的情况，是一种什么情况？ A B D H I 0 1 2 3 4 5 6 7 8 9 D B A H I 11 物料管理物料管理 ALDS 11 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 3、二叉树的存储结构：、二叉树的存储结构： 链接存储结构：链接存储结构： 仅定义结点的类型即可。结点之间的关系通过指针实现。仅定义结点的类型即可。结点之间的关系通过指针实现。 A B C D E F G H I L data le

14、ft right 标准形式：（二叉链表）标准形式：（二叉链表） 广义标准形式：（三叉链表）广义标准形式：（三叉链表） data left right Parent 12 物料管理物料管理 ALDS 12 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 3、二叉树的存储结构：、二叉树的存储结构： 链接存储结构：链接存储结构： A B / C D E F G G F D C B A E 13 物料管理物料管理 ALDS 13 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 templatetemplate

15、classclass BinaryTree; / 二叉树类 BinaryTree 的向前说明 templatetemplate classclass BinaryNode friendfriend classclass BinaryTree ; publicpublic: : BinaryNode ( ) : left(NULL), right(NULL) / 二叉树结点的构造函数。 BinaryNode ( Type item, BinaryNode * L = NULL, BinaryNode * R = NULL ): data(item),left(L), right( R) Bina

16、ryNode ( ) Type GetData ( ) constconst returnreturn data; / 得到二叉树结点的数据值。 BinaryNode * GetLeft( ) constconst returnreturn left; /得到二叉树结点的左儿子地址。 inaryNode * GetRight( ) constconst returnreturn right; /得到二叉树结点的左儿子地址。 voidvoid SetData ( constconst Type / 设置二叉树结点的数据值。 voidvoid SetLeft (BinaryNode * L ) l

17、eft = L; / 设置二叉树结点的左儿子地址。 voidvoid SetRight (BinaryNode * R ) right = R; / 设置二叉树结点的右儿子地址。 二叉树的二叉树的 ADT： 14 物料管理物料管理 ALDS 14 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 templatetemplate classclass BinaryTree; / 二叉树类 BinaryTree 的向前说明 templatetemplate classclass BinaryNode friendfriend classclass Bi

18、naryTree ; publicpublic: : voidvoid PrintPreOrder( ) constconst; / 按前序打印二叉树的结点的数据值。 voidvoid PrintPostOrder( ) constconst; / 按后序打印二叉树的结点的数据值。 voidvoid PrintInOrder( ) constconst; / 按中序打印二叉树的结点的数据值。 BinaryNode * Duplicate( ) constconst; / 复制二叉树中的所有结点。 privateprivate: : BinaryNode * left , * right ; /

19、 结点的左、右儿子的地址 Type data; / 结点的数据信息 ; 二叉树的二叉树的 ADT： 15 物料管理物料管理 ALDS 15 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 templatetemplate classType classclass BinaryTreeBinaryTree publicpublic: : BinaryTree(BinaryTree( ) ) : : root(root( NULL)NULL) / 构造空二叉树构造空二叉树 BinaryTreeBinaryTree ( ( constconst Type

20、Type ; BinaryTreeBinaryTree ( ( ) ) DelTreeDelTree ( ( rootroot ) ); ; intint IsEmptyIsEmpty ( ( ) ) constconst returnreturn rootroot = NULLNULL; ; / 二叉树为空二叉树为空，返回非返回非0 0，否则为否则为0 0。 constconst BinaryNodeBinaryNode * * Getroot(Getroot( )const)const returnreturn rootroot; ; intint MakeEmptyMakeEmpty (

21、 ( ) ) DelTree(DelTree( root)root); ; rootroot = NULLNULL; ; / 使二叉树为空使二叉树为空。 constconst BinaryTreeBinaryTree ; privateprivate: : BinaryNodeBinaryNode * * rootroot; ; / 二叉树的根结点二叉树的根结点。 BinaryTree(BinaryTree( constconst BinaryTreeBinaryTree ; voidvoid DelTree(DelTree( BinaryNodeBinaryNode * * T T ) );

22、 ; ; ; templatetemplate classType constconst BinaryTreeBinaryTree ; / 其具体实现其具体实现，见程序见程序5 5. .1 1。 ifif ( ( T T. .rootroot !=!= NULLNULL ) ) rootroot = = T T. .rootroot- -Duplicate(Duplicate( ) ); ; 二叉树的二叉树的 ADT： 16 物料管理物料管理 ALDS 16 Algorithms and DataStrucstures:Trees 2、二叉树、二叉树 template template Typ

23、e Max( const Type u, const Type v )Type Max( const Type u, const Type v ) if ( u v ) return u; else return v; if ( u v ) return u; else return v; template template int BinaryNode : Size ( const BinaryNode * T ) const int BinaryNode : Size ( const BinaryNode * T ) const / / 得到以得到以 T T 为根的二叉树或子树的结点个数。

24、为根的二叉树或子树的结点个数。 if ( T = NULL ) return 0;if ( T = NULL ) return 0; else return 1 + Size( Telse return 1 + Size( T- -left ) + Size( Tleft ) + Size( T- -right);right); template template int BinaryNode : Height ( const BinaryNode * T ) const int BinaryNode : Height ( const BinaryNode * T ) const / / 得到

25、以得到以 T T 为根的二叉树的高度。为根的二叉树的高度。 if ( T = NULL ) return 0;if ( T = NULL ) return 0; else return 1 + Max( Height( Telse return 1 + Max( Height( T- -left ),Height( Tleft ),Height( T- -right);right); 二叉树的二叉树的 ADT：求二叉树的结点个数和高度以及删除一棵二叉树。求二叉树的结点个数和高度以及删除一棵二叉树。 17 物料管理物料管理 ALDS 17 Algorithms and DataStrucstur

26、es:Trees 2、二叉树、二叉树 template template void BinaryTree : DelTree ( BinaryNode * T ) void BinaryTree : DelTree ( BinaryNode * T ) / / 删除以删除以 T T 为根的二叉树的所有结点。为根的二叉树的所有结点。 if ( T != NULL ) if ( T != NULL ) DelTree( TDelTree( T- -left);left); DelTree( TDelTree( T- -right);right); delete T;delete T; 二叉树的二叉

27、树的 ADT：求二叉树的结点个数和高度以及删除一棵二叉树。求二叉树的结点个数和高度以及删除一棵二叉树。 18 物料管理物料管理 ALDS 18 Algorithms and DataStrucstures:Trees C D E L A W L R L R R L R 3、二叉树遍历、二叉树遍历 1、遍历二叉树：设、遍历二叉树：设 N 代表根节点，代表根节点，L 代表左子树，代表左子树，R 代表右子树。代表右子树。 a. 前序（或先序）：如果二叉树为空，则操作为空：否则访问根结点；前序遍历左子树；前序（或先序）：如果二叉树为空，则操作为空：否则访问根结点；前序遍历左子树； 前序遍历右子树。记为

28、：前序遍历右子树。记为：NLR。 b. 中序：中序： 如果二叉树为空，则操作为空：否则中序遍历左子树；访问根结点；如果二叉树为空，则操作为空：否则中序遍历左子树；访问根结点； 中序遍历右子树。记为：中序遍历右子树。记为：LNR。 c. 后序：后序： 如果二叉树为空，则操作为空：否则后序遍历左子树；后序遍历右子如果二叉树为空，则操作为空：否则后序遍历左子树；后序遍历右子 树；访问根结点。记为：树；访问根结点。记为：LRN。 前序：前序：A、L、B、E、 C、D、W、X 中序：中序：B、L、E、A、 C、W、X、D 后序：后序：B、E、L、X、 W、D、C、A B C D E L A X W X

29、B 19 物料管理物料管理 ALDS 19 Algorithms and DataStrucstures:Trees 3、二叉树遍历、二叉树遍历 B C D E L A X W 1、遍历二叉树：续、遍历二叉树：续 a. 前序分析：结点的左儿子、左孙子、左后代、前序分析：结点的左儿子、左孙子、左后代、 将连续输出。结点的右儿子将在结点、结点的左将连续输出。结点的右儿子将在结点、结点的左 子树全部输出之后才输出。子树全部输出之后才输出。 b. 中序分析：最先输出的结点是根结点的最左的左后代。将二叉树中的结点投影到水平轴线上，则得到中序分析：最先输出的结点是根结点的最左的左后代。将二叉树中的结点投影

30、到水平轴线上，则得到 中序遍历的序列。中序遍历的序列。 c. 后序分析：根结点（或子树的根结点）将在它的左、右子树的结点输出之后。因此，根结点（或子树后序分析：根结点（或子树的根结点）将在它的左、右子树的结点输出之后。因此，根结点（或子树 的根结点）在中序序列中的序号等于它的左右子树的结点个数的根结点）在中序序列中的序号等于它的左右子树的结点个数 左右子树中的最先被访问左右子树中的最先被访问 的结点的序号。注意，结点、右父亲、右祖父、的结点的序号。注意，结点、右父亲、右祖父、 将连续输出。将连续输出。 前序：前序：A、L、B、E、C、D、W、X 中序：中序：B、L、E、A、C、W、X、D 后序

31、：后序：B、E、L、X、W、D、C、A B C D E L A X W B L E A C W X D 20 物料管理物料管理 ALDS 20 Algorithms and DataStrucstures:Trees 3、二叉树遍历、二叉树遍历 B C D E L A 1、遍历二叉树：续、遍历二叉树：续 前序的程序实现：前序的程序实现： 1、根结点进栈根结点进栈 2、结点出栈，被访问、结点出栈，被访问 3、结点的右、左儿子（非空）进栈、结点的右、左儿子（非空）进栈 4、反复执行、反复执行 2、3 ，至栈空为止。，至栈空为止。 前序：前序：A、L、B、E、C、D e.g: A出栈出栈 访问访问

32、L出栈出栈 访问访问 B出栈出栈 访问访问 E出栈出栈 访问访问 C出栈出栈 访问访问 D出栈访问出栈访问 后，栈空后，栈空 结束结束 A进栈进栈 C、L 进栈进栈 E、B 进栈进栈 D进栈进栈 分析：分析：p的前序的直接后继的前序的直接后继q: 1、p有有左儿子，则左儿子，则q=该左儿子该左儿子 2、p无无左儿子，有右儿子，则左儿子，有右儿子，则q= 该左儿子该左儿子 3、 、p无无左儿子、右儿子左儿子、右儿子 ，搜索其祖先结点的右儿子送，搜索其祖先结点的右儿子送q。找不到结束。找不到结束。 21 物料管理物料管理 ALDS 21 Algorithms and DataStrucstures

33、:Trees 4、二叉树遍历的迭代器类、二叉树遍历的迭代器类 二叉树的迭代器：二叉树的迭代器：Tree Iterator ADT 5.3: ADT 5.3: 二叉树的迭代器类。二叉树的迭代器类。 template template class class TreeIterator public:public: TreeIterator ( constconst BinaryTree / 第一个被访问的结点地址送current virtual void operator virtual void operator + ( ) = 0; / 下一个被访问的结点地址送current int oper

34、ator int operator + ( )constconst return return current != NULL;/当前结点为空吗，为空返回 True const const Type const; / 返回当前结点指针 current 所指向的结点的数据值。 protected:protected: const const BinaryTree const const BinaryNode * current; / 指向当前结点的指针。 private:private: TreeIterator ( const const TreeIterator ; template tem

35、plate const const Type returnreturn current-GetData( ); 22 物料管理物料管理 ALDS 22 Algorithms and DataStrucstures:Trees 4、二叉树遍历的迭代器类、二叉树遍历的迭代器类 遍历二叉树：遍历二叉树：Tree Iterator ：前序的实现。：前序的实现。 templatetemplate classclass Preorder : publicpublic TreeIterator publicpublic: : Preorder( constconst BinaryTree Preorder(

36、 ) voidvoid First( ); voidvoid operatoroperator + ( ); voidvoid Preorder_NLR ( ); protectedprotected: : Stack constconst BinaryNode * s; ; templatetemplate Preorder : Preorder( constconst BinaryTree templatetemplate voidvoid Preorder : First ( ) s.MakeEmpty ( ); ifif ( T.Getroot( ) ) s.Push( T.Getro

37、ot( ) ); operatoroperator + ( ); /堆栈清空。若二叉树T非空，则根结点进栈，并得到当前结点。 23 物料管理物料管理 ALDS 23 Algorithms and DataStrucstures:Trees 4、二叉树遍历的迭代器类、二叉树遍历的迭代器类 遍历二叉树：遍历二叉树：Tree Iterator ：前序的实现。：前序的实现。 templatetemplate voidvoid Preorder : operatoroperator + ( ) ifif ( s.IsEmpty() ) ifif ( current = NULL ) cerr “Adva

38、nced past end ” GetRight ( ) != NULL ) s.Push( current-GetRight( ) ); /非空左儿子进栈。 ifif ( current -GetLeft ( ) != NULL ) s.Push( current-GetLeft( ) ); /非空右儿子进栈。 templatetemplate voidvoid Preorder : Preorder_NLR ( ) First( ); / 将当前指针 current 指向根结点。 whilewhile( operatoroperator +( ) ) / 当前指针 current 非空时继

39、续执行。 coutcout operatoroperator()() endlendl; / 输出当前结点的数据场之值。 operatoroperator +( ); / 使前序次序下的下一个结点成为当前结点。 24 物料管理物料管理 ALDS 24 Algorithms and DataStrucstures:Trees 4、二叉树遍历的迭代器类、二叉树遍历的迭代器类 遍历二叉树：设根结点初始时非空遍历二叉树：设根结点初始时非空 后序算法：后序算法：1、结点（初始时为根）进栈（标志结点（初始时为根）进栈（标志0），沿左指针查找左儿子（标志），沿左指针查找左儿子（标志1） 2、左儿子非空，返回

40、、左儿子非空，返回1。 3、退栈。若为标志、退栈。若为标志1转转 4 ，否则标志，否则标志 2，转，转 5。 4、进栈转向右子树（标志、进栈转向右子树（标志2），），如右儿子非空，则如右儿子非空，则转向转向 1；空转向；空转向 3。 5、标志改为标志改为3，访问结点，返回访问结点，返回 3 6、反复、反复 1 到到 5 ，至栈空为止。，至栈空为止。 e.g: C D E L A 后序：后序：E、L、D、C、A 分析：分析：1、二叉树最先被访问的结点是二叉树中最左方的叶子。、二叉树最先被访问的结点是二叉树中最左方的叶子。 2、p的后序的直接后继的后序的直接后继q: 1、p是父结点的右儿子是父结点

41、的右儿子，则，则q=该父结点。该父结点。2、p是父结点的是父结点的左左 儿子，如果有右子树，则儿子，如果有右子树，则q=该右子树中最左的叶子。如果，无右子树，该右子树中最左的叶子。如果，无右子树，q=父结点。父结点。 3、p无父结点，那么无父结点，那么q = NULL。 25 物料管理物料管理 ALDS 25 Algorithms and DataStrucstures:Trees 4、二叉树遍历的迭代器类、二叉树遍历的迭代器类 后序遍历时的实现实例；注意堆栈中保存的是当前结点的祖先。后序遍历时的实现实例；注意堆栈中保存的是当前结点的祖先。 0 1 1 0 1 0 1 2 1 1 2 2 1

42、2 1 2 1 2 0 0 2 1 1 2 1 2 2 1 2 1 2 2 2 ( (1 1) ) ( (2 2) ) ( (3 3) ) ( (4 4) ) ( (5 5) ) ( (6 6) ) ( (7 7) ) ( (8 8) ) ( (9 9) ) ( (1010) ) ( (1111) ) ( (1212) ) ( (1313) ) ( (1414) ) ( (1515) ) D C B E A 26 物料管理物料管理 ALDS 26 Algorithms and DataStrucstures:Trees 4、二叉树遍历的迭代器类、二叉树遍历的迭代器类 遍历二叉树：遍历二叉树：T

43、ree Iterator 后序的后序的实现实现 templatetemplate structstruct StNode constconst BinaryNode * Node; intint TimesPop; StNode( constconst BinaryNode * N = NULL ): Node(N), TimesPop(0) ; templatetemplate classclass Postorder : publicpublic TreeIterator publicpublic: : Postorder( constconst BinaryTree Postorder( ) voidvoid First( ); / 后序遍历时的第一个结点的地址。 voidvoid operator + ( ); / 后序遍历时的下一个结点的地址。 protectedprotected: : Stack StNode s; ; templatetemplate Postorder : Postorder(constconst BinaryTree temp