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
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
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