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

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

break; } }

printf( \前序遍历, 递归方法\\n\ re_preorder( t ); /* 前序遍历, 递归方法 */ printf( \任意键继续\\n\\n\ getch(); printf( \中序遍历, 递归方法\\n\ re_midorder( t ); /* 中序遍历, 递归方法 */

printf( \任意键继续\\n\\n\

49