二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(15)

if ( p ) {

visit ( p->data );

// 左、右子树入队列

q[rear] = p->lchild; rear = ( rear+1 ) % MAXSIZE;

q[rear] = p->rchild; rear = ( rear+1 ) % MAXSIZE;

}

}

}

nn) 非递归遍历二叉树

一般借助栈实现。设想一指针沿二叉树中序顺序移动，每当向上层移动时就要出栈。 (a) 中序非递归遍历

指针p从根开始，首先沿着左子树向下移动，同时入栈保存；当到达空子树后需要退栈访问结点，然后移动到右子树上去。

void InOrder ( BinTree bt, VisitFunc visit )

{

InitStack ( S );

p = bt;

while ( p || ! StackEmpty(S) ) {

if ( p ) {

Push ( S, p );

p = p->lchild;

} else {

Pop ( S, p );

visit ( p ); // 中序访问结点的位置

p = p->rchild;

}

}

}

(b) 先序非递归遍历

按照中序遍历的顺序，将访问结点的位置放在第一次指向该结点时。

void Preorder ( BinTree bt, VisitFunc visit )

{

InitStack ( S );

p = bt;

while ( p || ! StackEmpty(S) ) {

if ( p ) {

visit ( p ); // 先序访问结点的位置

Push ( S, p );

p = p->lchild;

} else {

Pop ( S, p );

p = p->rchild;

}

}

}

或者，由于访问过的结点便可以弃之不用，只要能访问其左右子树即可，写出如下算法。 void Preorder ( BinTree bt, VisitFunc visit )

{

InitStack ( S );

Push ( S, bt );

while ( ! StackEmpty(S) ) {

Pop ( S, p );

if ( p ) {

visit ( p );

Push ( S, p->rchild ); // 先进栈，后访问，所以

Push ( S, p->lchild ); // 这里先让右子树进栈

}

}

}

(c) 后序非递归遍历

后序遍历时，分别从左子树和右子树共两次返回根结点，只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。

void PostOrder ( BinTree bt, VisitFunc visit )

{

InitStack ( S ), InitStack ( tag );

p = bt;

while ( p || ! StackEmpty(S) ) {

if ( p ) {

Push ( S, p ), Push ( tag, 1); // 第一次入栈

p = p->lchild;

} else {

Pop ( S, p ), Pop ( tag, f );

if ( f==1 ) {

// 从左子树返回，二次入栈，然后p转右子树

Push ( S, p ), Push ( tag, 2 );

p = p->rchild;

} else {

// 从右子树返回(二次出栈)，访问根结点，p转上层

visit ( p );

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-15.html