C语言树和二叉树
一、实验目的：
（1）掌握二叉树的存储实现。
（2）掌握二叉树的遍历思想。
（3）掌握二叉树的常见算法的程序实现。
二、实验内容：
（1）输入字符序列，建立二叉链表。
（2）中序遍历二叉树:递归算法。
（3）中序遍历二叉树:非递归算法。（最好也能实现先序，后序非递归算法）
（4）求二叉树的高度 。
（5）求二叉树的叶子个数。
（6）建立中序线索二叉树，并实现中序遍历。
（8）借助队列实现二叉树的层次遍历。
（9）在主函数中设计一个简单的菜单，分别调试上述算法。
(10) 综合训练：为N个权值设计哈夫曼编码。
（其中要求必须完成1，2，4，5，9内容，其它可以选做）
实验说明:
1.类型定义 //二叉链表存储
#define ElemType char//元素类型
typedef struct BiTNode
{ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
2.元素类型可以根据实际情况选取。
注意问题:
1.注意理解递归算法的执行步骤。
2.注意字符类型数据在输入时的处理。
3.重点理解如何利用栈结构实现非递归算法
追问：大哥,要包含哪些头文件呀,注明一下吧,我这里调试不通过呀
答案：非递归先序遍历：
void TraversalTree_DLR(BinTNode *t)
{ BinTNode *stack[M]; int top;
BinTNode *p;
if( t==NULL ) return;
top = 1; stack[top] = t;
while ( top > 0 )
{ p = stack[top--];
putchar( p->data );
if ( p->rchild != NULL ) stack[ ++top ] = p->rchild ;
if ( p->lchild != NULL ) stack[ ++top ] = p->lchild ;
}
中序：void TraversalTree_LDR(BinTNode *t)
{ BinTNode *stack[M]; int top;
BinTNode *p;
if( t==NULL ) return;
top = 0; p = t;
while ( p != NULL )
{ while ( p != NULL )
{ stack[++top] = p; p = p->lchild; }
do {
p = stack[top--]; putchar( p->data ); p = p->rchild;
} while ( top > 0 && p == NULL)；
}
}
后序：
void TraversalTree_LRD(BinTNode *t)
{ struct
{ BinTNode *ptr;
char tag;
} *stack[M];
int top;
BinTNode *p;
if( t==NULL ) return;
top = 0; p = t;
while ( p != NULL )
{ while ( p != NULL )
{ stack[++top].ptr = p; stack[top].tag =‘L’;p = p->lchild; }
while( top>0 && ( stack[top].tag ==‘R’||
stack[top].tag ==‘L’&& stack[top].ptr -> rchild == NULL ))
{ p = stack[top--].ptr; putchar( p->data );}
if(top>0)
{ stack[top].tag =‘R’; p = stack[top].ptr->rchild; }
else break; // p = NULL;
}
}
上一个：请问C语言难吗
下一个：二级C语言排序技术2
