因为每个结点所存储的数据类型为字符串，却无法使用字符串和 String 等数据类型， 所以使用单链表作为结点所存储的数据类型。以#表示空结点。 利用先序遍历创建链表
2.1.1 用单链表 s 记录输入的数据 2.1.2 利用非递归调用分别生成根节点的左子树和右子树。 2.1.3 返回菜单重新选择。
基本程序如下：
void CreatBiTree_q(BiTree &T)/ { · · · · · · if(ch=='#') T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) exit(0); T->data=ch; T->LTag=Link; T->RTag=Link;
5
int right=0; typedef char TElemType;
typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; int LTag, RTag,flag; }BiTNode,*BiTree; BiTree pre; void CreatBiTree_q(BiTree &T) { TElemType ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) exit(0); T->data=ch; T->LTag=Link; T->RTag=Link; CreatBiTree_q(T->lchild); CreatBiTree_q(T->rchild); } } void CreateBiTree(BiTree *T) { TElemType ch; scanf("%c",&ch); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BiTNode)); if(!*T) exit(-1); (*T)->data=ch;
1.课题设计目的 ：培养学生用学到的书本知识解决实际问题的能力；培养实际 工作所需要的动手能力；培养学生以科学理论和工程上能力的技术， 规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性 作用；通过课程设计的实践，学生可以在程序设计方法、上机操作 等基本技能和科学作风方面受到比较系统和严格的训练。 课题设 计 2.课题设计意义： 。锻炼我们的编码能力，真正的理解数据结构的编码思想，并
目的与 且锻炼我们的动手能力和成员间的配合，提高程序编写能力。 设计意 义
指导教师： 年 月 日
Байду номын сангаас
1
目
录
第一章 课程与设计的目的与意义.............................................................................. 1 1.1 课题设计目的：.............................................................................................. 1 1.2 课题设计意义：.............................................................................................. 1 第二章 可行性分析...................................................................................................... 1 2.1 创建二叉树链表的结点存储结构及数据的输入函数................................. 1 2.1.1 用单链表 s 记录输入的数据............................................................... 1 2.1.2 利用非递归调用分别生成根节点的左子树和右子树。................... 1 2.1.3 返回菜单重新选择。........................................................................... 1 2.2 先序遍历、中序遍历、后序遍历二叉链表。.............................................. 2 2.3 主函数.............................................................................................................. 2 第三章、调试界面：.................................................................................................... 2 3.1 调试所用二叉树：.......................................................................................... 2 3.2 程序运行如下：.............................................................................................. 3 第四章、错误分析：.................................................................................................... 5 第五章、总结................................................................................................................ 5 第六章、 附录.............................................................................................................. 6 6.1 源程序.............................................................................................................. 6 6.2 参考资料....................................................................................................... 12
1
CreatBiTree_q(T->lchild); CreatBiTree_q(T->rchild); } } 2.2 先序遍历、中序遍历、后序遍历二叉链表。
A 、先序遍历：访问根节点，左子树，右子树的顺序。 B、中序遍历：访问左子树，根节点，右子树的顺序。 C、后序遍历：访问左子树，右子树，根节点的顺序。 D、层次遍历：从根结点开始，按从左至右的顺序依次访问。 E、中序线索化：将二叉树线索化，再进行中序遍历输出。
2.3 主函数
a、调用生成二叉树的函数，从键盘输入二叉树的各个结点 b、分别调用先序遍历、中序遍历、后序遍历二叉树的函数，输出所有结点 显示的菜单为： *********************************************** 请选择遍历算法 1.按先序输入二叉树序列以#表示空节点 2.先序遍历二叉树递非归算法 3.中序遍历二叉树非递归算法 4.后序遍历二叉树非递归算法 5.层次遍历二叉树非递归算法 6.中序线索遍历二叉树算法 0.按 0 退出"<<endl 请输入序号（0，1,2,3,4,5,6） ：
3.2 程序运行如下：
：
图1 菜单界面
图2
创建界面
3、先序非遍历二叉树：
3
4、中序非遍历二叉树：
5、后序非遍历二叉树：
6、层次遍历二叉树：
4
7、中序线索化，中序遍历：
第四章、错误分析
1、中序线索化后，先序、中序、后序、层次遍历均出现错误，陷入死循环， 改正：另外编写一个创建二叉树的函数，中序线索化另外重新创建，中序输出函数也另外 编写 2、中序线索化时，用到的线索在结构体内定义，在线索化时，显示为未定义 改正：直接在外部定义线索#define Link 0 和#define Thread 1
6
CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } } void PreOrderTraverse(BiTree &T) { BiTree p,S[20]; int top=-1; p=T; do { while(p!= NULL) { cout << p->data<<" "; top++; S[top]=p; p=p->lchild; } if( top >-1 ) { p=S[top]; top--; p = p->rchild; } }while (( p != NULL ) ||(top>-1)); } int inorderTraverse(BiTree &T) { BiTree p,s[20];int i=-1; p=T; while(p||i>-1) { if(p) { i++; s[i]=p; p=p->lchild; } else { p=s[i]; cout<<" ";