二叉數的遍歷

所謂遍歷(Traversal)是指沿著某條搜尋路線，依次對樹中每個結點均做一次且僅做一次訪問。遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。二叉樹上訪問結點所做的操作依賴於具體的套用問題。

規則

· 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)

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;}