《数据结构实验与实训教程(第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; }

break; } }

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

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

49

getch(); printf( \后序遍历, 递归方法\\n\ re_posorder( t ); /* 后序遍历, 递归方法 */ printf( \任意键继续\\n\\n\ getch(); printf( \前序遍历, 采用链接栈的迭代方法\\n\

st_preorder( t ); /* 前序遍历, 采用链接栈的迭代方法 */ printf( \任意键继续\\n\\n\ getch();

printf( \中序遍历, 采用链接栈的迭代方法\\n\ st_midorder( t ); /* 中序遍历, 采用链接栈的迭代方法 */ printf( \任意键继续\\n\\n\ getch(); printf( \后序遍历, 采用链接栈的迭代方法\\n\ st_posorder( t ); /* 后序遍历, 采用链接栈的迭代方法 */ printf( \任意键退出\\n\\n\ getch(); }

程序3:题3 Huffman编码 #include #define MAX 21

typedef struct { /* 定义huffman树结点结构 */ char data; /* 结点值 */ int weight; /* 权重 */ int parent; /* 父结点 */ int left; /* 左结点 */

int right; /* 右结点 */

}huffnode;

typedef struct { /* 定义huffman编码结构 */ char cd[MAX];

int start;

}huffcode; void main() { huffnode ht[2*MAX]; huffcode hcd[MAX], d;

int i, k, f, j, r, n=0, c, m1, m2;

printf( \请输入元素个数( 1 --> %d ):\

scanf( \%d\

50

if( n > MAX-1 || n < 1 ) /* 输入错误, 退出 */ return;

for( i = 0; i < n; i++ ) { fflush( stdin ); printf( \第%d个元素=>\\n\\t结点值:\ scanf( \%c\ printf( \权重:\ scanf( \%d\

}

for( i = 0; ___1___; i++ ) ht[i].parent = ht[i].left = ht[i].right = 0;

for( i = n; i < 2 * n - 1; i++ ) { /* 构造huffman树 */ m1 = m2 = 0x7fff; j = r = 0; /* j, r为最小权重的两个结点位置 */ for( k = 0; k < i; k++ ) if( ht[k].parent == 0 ) if(___2_ < m1 ) { m2 = m1; r = j;

__3______; j = k; }

else if( ht[k].weight < m2 ) {

m2 = _4____;

r = k;

}

ht[j].parent = _5___;

ht[r].parent =___6__;

ht[i].weight = ____7_____; ht[i].left = j; ht[i].right = r; }

for( i = 0; i < n; i++ ) { /* 根据huffman树求huffman编码 */ d.start = n; c = i;

f = ht[i].parent;

while( f != 0 ) { if(___8____ == c ) d.cd[ --d.start ] = '0';

else

51