{ printf( 请选择操作，1：增加树结点 2：删除树结点 0：结束操作 fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( switch( op ) { case 0: /* 退出 */ break; case 1: /* 增加树结点 */
printf( 请输入树结点元素：
scanf(
switch( ____1_____ ) { case 0: /* 成功 */ clrscr(); gotoxy( 1, 1 ); printf( 成功，树结构为:\n OutputTree( t ); break; case 1: printf( 该元素已存在 break; default: printf( 内存操作失败
}
case 2: /* 删除结点 */ printf( 请输入要删除的树结点元素： scanf( if( ____2____ ) { /* 删除成功 */ clrscr(); gotoxy( 1, 1 ); printf( 删除成功, 树结构为:\n OutputTree( t ); } else
printf( 该键值树结点不存在\n
break;
}
}
45
break; break;
实验8 树的遍历和哈夫曼树
五、参考程序
程序1：题1 二叉树的遍历操作函数 typedef struct tree { /* 定义树的结构 */ int data; /* 假定树的元素类型为int */ struct tree *lchild; /* 左孩子 */ struct tree *rchild; /* 右孩子 */ }TREE;
typedef struct stack { /* 定义链接栈结构 */ TREE *t; /* 栈结点元素为指向二叉树结点的指针 */ int flag; /* 后序遍历时用到该标志 */ struct stack *link; /* 栈节点链接指针 */ }STACK;
void re_preorder( TREE *tree ) /* 前序遍历, 递归方法 */ { /*编写前序遍历子程序*/ }
void re_midorder( TREE *tree ) /* 中序遍历, 递归方法 */ { if( tree != NULL ) { /* 不为空子树时递归遍历 */ re_midorder( tree->lchild ); /* 先遍历左子树 */ printf( /* 再遍历父结点 */ re_midorder( tree->rchild ); /* 最后遍历右子树 */ } }
void re_posorder( TREE *tree ) /* 后序遍历, 递归方法 */ {
/*编写后序遍历子程序*/
}
void push( STACK **top, TREE *tree ) /* 树结点入栈 */ {
46
STACK *p; /* 工作指针 */ p = (STACK *)malloc( sizeof(STACK) ); /* 申请栈结点 */ p->t = tree; /* 根结点进栈 */ p->link = *top; /* 新栈结点指向栈顶 */ *top = p; /* 栈顶为新结点 */ }
void pop( STACK **top, TREE **tree ) /* 出栈, 栈内元素赋值给树结点 */ { STACK *p; /* 工作指针 */ if( *top == NULL ) /* 空栈 */ *tree = NULL; else { /* 栈非空 */ *tree = (*top)->t; /* 栈顶结点元素赋值给树结点 */ p = *top; *top = (*top)->link; /* 栈顶指向下一个链接, 完成出栈 */
free( p ); /* 释放栈顶结点空间 */
} }
void st_preorder( TREE *tree ) /* 前序遍历, 采用链接栈的迭代方法 */ { STACK *top; /* 栈顶指针 */ top = NULL; /* 初始化为空栈 */ while( tree != NULL ) { /* 二叉树还未遍历完 */ ____1_______; /* 访问根结点 */ if( ___2_______ ) /* 右子树结点入栈 */ push( &top, tree->rchild ); if( tree->lchild != NULL ) /* 左子树结点入栈 */ ________3_____; pop( &top, &tree ); /* 树结点出栈 */
}
}
void st_midorder( TREE *tree ) /* 中序遍历, 采用链接栈的迭代方法 */
{ STACK *top; /* 栈顶指针 */ top = NULL; /* 初始化为空栈 */
while( ___4_____ ) { /* 循环条件为二叉树还未遍历完, 或则栈非空 */
while( tree != NULL ) { /* 二叉树还未遍历完 */
47
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
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; }
break; } }
printf( 前序遍历, 递归方法\n re_preorder( t ); /* 前序遍历, 递归方法 */ printf( 任意键继续\n\n getch(); printf( 中序遍历, 递归方法\n re_midorder( t ); /* 中序遍历, 递归方法 */
printf( 任意键继续\n\n
49