二叉树的ADT 二叉树的ADT:求二叉树的结点个数和高度以及删除一棵二叉树。 template class Type> Type Max( const Type u, const Type v) (if(u>y)return u; else return v: 1 template <class Type> int BinaryNode< Type>:: Size( const Binary Node <Type>*T)const //得到以T为根的二叉树或子树的结点个数。 if(T== NULL) return 0 else return 1+ Size( t->left)+ Size (t->right) template <class Type> int BinaryNode< Type>:: Height( const BinaryNode< Type>* T) const i //得到以T为根的二叉树的高度。 if(T== NULL)return 0 else return 1+ Max( Height(T->left), Height(T->right));
二叉树的ADT template <class Type> Type Max( const Type u, const Type v ) { if ( u > v ) return u; else return v;} template <class Type> int BinaryNode < Type> :: Size ( const BinaryNode <Type> * T ) const { // 得到以 T 为根的二叉树或子树的结点个数。 if ( T == NULL ) return 0; else return 1 + Size( T->left ) + Size( T->right); } template <class Type> int BinaryNode < Type> :: Height ( const BinaryNode < Type> * T ) const { // 得到以 T 为根的二叉树的高度。 if ( T == NULL ) return 0; else return 1 + Max( Height( T->left ),Height( T->right)); } ·二叉树的 ADT：求二叉树的结点个数和高度以及删除一棵二叉树
二叉树的ADT 二叉树的ADT:求二叉树的结点个数和高度以及删除一棵二叉树。 ■■■■■■■■■口 template class Type> void BinaryTree<Type>:: DelTree( BinaryNode< Type>*T)i //删除以T为根的二叉树的所有结点。 if(T!= NULL DelTree( T->left) DelTree (T->right) delete t
二叉树的ADT template <class Type> void BinaryTree<Type> :: DelTree ( BinaryNode < Type> * T ) { // 删除以 T 为根的二叉树的所有结点。 if ( T != NULL ) { DelTree( T->left); DelTree( T->right); delete T; } } ·二叉树的 ADT：求二叉树的结点个数和高度以及删除一棵二叉树
叉树遍历 设N代表根节点,L代表左子树,R代表右子树。 a前序(或先序):如果二叉树为空,则操作为空:否则访问根结点;前序遍历左子树; 前序遍历右子树。记为:NLR。 b.中序: 如果二叉树为空,则操作为空:否则中序遍历左子树;访问根结点 中序遍历右子树。记为:LNR。 c.后序: 如果二叉树为空,则操作为空:否则后序遍历左子树;后序遍历右子 树;访问根结点。记为:LRN 前序:A、L、B、E、 C、D、W、X R 中序:B、L、E、A c、W、X、D 后序:B、E、L、X、 R R W、D、C、A
二叉树遍历 设 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 L R L R R L R 中序：B、L、E、A、 C、W、X、D 后序：B、E、L、X、 W、D、C、A B C D E L A X W
叉树遍历 a前序分析:结点的左儿子、左孙子、左后代、…将连续输出。结点的右儿子将在结点、结点的左 子树全部输出之后才输出。 b中序分析:最先输出的结点是根结点的最左的左后代。将二叉树中的结点投影到水平轴线上,则得到 中序遍历的序列 C.后序分析:根结点(或子树的根结点)将在它的左、右子树的结点输出之后。因此,根结点(或子树 的根结点)在后序序列中的序号等于它的左右子树的结点个数+左右子树中的最先被访问 的结点的序号。注意,结点、右父亲、右祖父、…将连续输出。 前序:A、L、B、E、C、D、W、X c)中序:B、L、E、A、C、W、X、D 后序:B、E、L、X、W、D、C、A B LEA CWX D
二叉树遍历 B C D E L A X W a. 前序分析：结点的左儿子、左孙子、左后代、…… 将连续输出。结点的右儿子将在结点、结点的左 子树全部输出之后才输出。 b. 中序分析：最先输出的结点是根结点的最左的左后代。将二叉树中的结点投影到水平轴线上，则得到 中序遍历的序列。 c. 后序分析：根结点（或子树的根结点）将在它的左、右子树的结点输出之后。因此，根结点（或子树 的根结点）在后序序列中的序号等于它的左右子树的结点个数 ＋左右子树中的最先被访问 的结点的序号。注意，结点、右父亲、右祖父、…… 将连续输出。 前序：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 B L E A C W X D
叉树遍历的迭代器类 二叉树的迭代器: Tree Iterator ADT5.3:二叉树的迭代器类。 template <class Type>class TreeIterator I public: TreeIterator( const Binary Tree< Type>&bt): T(BT), current( NULL)[ 1 virtual TreeIterator()I) virtual void First()=0 //第一个被访问的结点地址送 current virtual void operator++()=0;//下一个被访问的结点地址送 current int operator+() const{ return current!=NUL;}/当前结点为空吗,非空返回True const Type operator ()()const; //返回当前结点指针 curren t所指向的结点的数据值 protected const Binary Tree <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(
二叉树遍历的迭代器类 • 二叉树的迭代器：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( ); }