子的指针，data是数据元素的内容。定义二叉树结点值的类型为字符型且结点个数不超过10个。
typedef char ElemType;
const int MaxLength=10;//结点个数不超过10个
typedef struct BTNode{ ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree; （2）构造二叉链表
按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。 void CreateBiTree(BiTree &T){ char ch; ch=getchar(); if(ch==' ') T=NULL; else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) printf(\ T->data=ch;
CreateBiTree(T->lchild); CreateBiTree(T->rchild); } }
（3）递归的先序遍历
函数功能是用递归的方法对二叉树进行先序遍历，调用此函数可以获得二叉树的递归的先序遍历的结果。
void PreOrderTraverse(BiTree T){ if(T){
printf(\ PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild);
5
} }
（4）递归的中序遍历
函数功能是用递归的方法对二叉树进行中序遍历。 void InOrderTraverse(BiTree T){ if(T){
InOrderTraverse(T->lchild); printf(\ InOrderTraverse(T->rchild); } }
（5）递归的后序遍历
函数功能是用递归的方法对二叉树进行中序遍历。 void PostOrderTraverse(BiTree T){ if(T){
PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf(\ } }
（6）非递归的先序遍历算法
函数功能是用非递归的方法对二叉树进行先序遍历。void NRPreOrder(BiTree bt) { BiTree stack[MaxLength],p; int top; if (bt!=NULL){ top=0;p=bt;
while(p!=NULL||top>0) { while(p!=NULL) {
6
printf(\ stack[top]=p; top++;
p=p->lchild; }
if (top>0)
{ top--; p=stack[top]; p=p->rchild; } } }
}
（7）非递归的中序遍历算法
此函数的功能是用非递归的方法实现二叉树的中序遍历算法。 void NRInOrder(BiTree bt) { BiTree stack[MaxLength],p; int top; if (bt!=NULL){ top=0;p=bt;
while(p!=NULL||top>0) { while(p!=NULL) {
stack[top]=p; top++;
p=p->lchild; }
if (top>0)
{ top--; p=stack[top];printf(\ } }
}
7
（5）非递归的后序遍历算法
此函数的功能是用非递归的方法实现二叉树的后序遍历算法。调用此函数可以获得二叉树的非递归的后序遍历的结果。其中bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈1：遍历左子树的现场保护，2：遍历右子树前的现场保护。首先将bt和tag(为1)入栈，遍历左子树；为返回后，修改栈顶tag2，遍历右子树；最后访问根结点。 typedef struct {
BiTree ptr; int tag; }stacknode;
void NRPostOrder(BiTree bt) {
stacknode s[MaxLength],x; BiTree p=bt; int top;
if(bt!=NULL){ top=0;p=bt; do {
while (p!=NULL) ｛
s[top].ptr = p;
s[top].tag = 1;
top++;
p=p->lchild; }
8
while (top>0 && s[top-1].tag==2) {
x = s[--top]; p = x.ptr;
printf(\ }
if (top>0) {
s[top-1].tag =2;
p=s[top-1].ptr->rchild; } }while (top>0);}
}
5．课程设计心得及存在问题
虽然都说“程序＝数据结构＋算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。我感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。
但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。
另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。我以前对递归算法一直很害怕，总是看不明白究竟这递归是怎么进行的。在这次实验中我终于克服了这一障碍，一次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！
这次实验中我也出现过一些比较严重的错误。在用链表结构编写程序时我错误的把一个
9
定义的一级指针用二级指针来做，结果出现了一些难以想象的后果。程序设计中不会树化为二叉树的算法，故并未实现此功能。
10