请输入您要查询的百科知识:

 

词条 二叉数的遍历
释义

二叉树的遍历

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

}

}

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2024/12/24 0:43:05