Preorder traversal(中->左->右)

template<class T>

void PreOrder(BinaryNode<T>* t) // preorder traversal of *t.

{if(t)

{visit(t);

PreOrder(tàLeft);

PreOrder(tàRight);}

Inorder traversal(左->中->右)

//递归算法

template<class T>

void InOrder(BinaryNode<T>* t)

{if(t)

InOrder(tàLeft);

visit(t);

InOrder(tàRight);

//非递归算法

void Inorder(BinaryNode <T> * t)

Sack<BinaryNode<T>*> s(10);

BinaryNode<T> * p = t;

for ( ; ; )

while(p!=NULL)

s.push(p);

p = p->Left;

if (!s.IsEmpty( ))

p = s.pop( );

cout << p->element;

p = p->Right;

else

return

Postorder traversal(左->右->中)

//递归算法

template<class T>

void PostOrder(BinaryNode<T>* t)

if(t)

PostOrder(tàLeft);

PostOrder(tàRight);

visit(t)

//非递归算法

struct StkNode

BinaryNode <T> * ptr;

int tag;

vid Postorder(BinaryNode <T> * t)

Stack <StkNode<T>>s(10);

StkNode<T> Cnode;

BinaryNode<T> * p = t;

for( ; ; )

while (p!=NULL)

Cnode.ptr = p;

Cnode.tag = 0;

s.push(Cnode);

p = p->Left;

Cnode = s.pop( );

p = Cnode.ptr;

while ( Cnode.tag = = 1) //从右子树回来

cout << p->element;

if ( !s.IsEmpty( ))

Cnode = s.pop( );

p = Cnode.ptr;

else

return;

4)Cnode.tag = 1;

s.push(Cnode);

p = p->Right; //从左子树回来//for

Level order: it is a non-recursive function and a queue is used.

template<class T>

void LevelOrder(BinaryNode<T>* t)

LinkedQueue<BinaryNode<T>*> Q;

while(t)

visit(t); //visit t

if(tàLeft)

Q.Add(tàLeft);

if(tàRight)

Q.Add(tàRight);

try

Q.Delete(t);

}catch(OutOfBounds){return;}