《数据结构实验与实训教程(第4版)》程序代码

push( &top, tree ); /* 树结点入栈 */ _____5______; /* 沿左子树前进, 将经过的结点依次进栈 */ }

if( top != NULL ) { /* 左子数入栈结束, 且栈非空 */ pop( &top, &tree ); /* 树结点出栈 */ ______6__________; /* 访问根结点 */

_______7______ ; /* 向右子树前进 */

} }

}

void st_posorder( TREE *tree ) /* 后序遍历, 采用链接栈的迭代方法 */ { STACK *top; /* 栈顶指针 */ top = NULL; /* 初始化为空栈 */ do{ while( _____8______ ) { /* 二叉树还未遍历完 */ push( &top, tree ); /* 树结点入栈 */ top->flag = 0; /* 标志为0, 表示右子树未访问 */ _____9______; /* 沿左子树前进, 将经过的结点依次进栈 */ }

if( top != NULL ) { /* 栈非空 */ while( top!=NULL && ____10_____ ) { /* 右子树已访问 */ pop( &top, &tree ); /* 出栈 */ printf( \ }

if( top != NULL ) {

____11______; /* 置右子树为访问标志 */

tree = (top->t)->rchild;/* 查找栈顶元素的右子树 */

} }

}while( top != NULL ); /* 循环条件为栈非空 */

}

程序2：题2 主函数

/* 本程序实现了二叉查找树的中序遍历, 前序遍历, 后序遍历的递归和迭代方法 */ #include #include #include void main()

48

{ TREE *t; int i,op=-1;

/* 定义树 */ t = NULL;

/* 初始化为空树 */

while( op != 0 ) { printf( \请选择操作，1：增加树结点 0：结束操作 \ fflush( stdin ); /* 清空标准输入缓冲区 */

scanf( \

switch( op ) { case 0: /* 退出 */ break; case 1: /* 增加树结点 */ printf( \请输入树结点元素：\ scanf( \ switch( InsertNode( &t, i ) { case 0: /* 成功 */ clrscr(); gotoxy( 1, 1 ); printf( \成功，数结构为:\\n\ OutputTree( t ); break; case 1:

printf( \该元素已存在\

break;

default: printf( \内存操作失败\ break;