二叉数的遍历
二叉树的遍历
• Preorder前序遍历——访问结点的操作发生在遍历其左右子树之前
• Inorder中序遍历——访问结点的操作发生在遍历其左右子树之前
• Postorder后序遍历——访问结点的操作发生在遍历其左右子树之后
• Level order层次遍历
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)
{
Stack<BinaryNode<T>*> s(10);
BinaryNode<T> * p = t;
for ( ; ; )
{
1) while(p!=NULL)
{ s.push(p); p = p->Left; }
2) 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;
}
void Postorder(BinaryNode <T> * t)
{
Stack <StkNode<T>>s(10);
StkNode<T> Cnode;
BinaryNode<T> * p = t;
for( ; ; )
{
1)while (p!=NULL)
{
Cnode.ptr = p;
Cnode.tag = 0;
s.push(Cnode);
p = p->Left;
}
2)Cnode = s.pop( );
p = Cnode.ptr;
3)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;}
}
}