二叉树遍历 数据结构课程设计.doc

1、目 录摘要I第一章 问题定义1第二章 设计思路2第三章 数据结构定义3第四章 系统功能模块设计4第五章 运行与调试6总 结10附 录I1程序清单I2参考资料X摘要 本课设主要实现对二叉树进行的三种次序遍历，输出三种遍历次序的遍历序列。 先序遍历对二叉树进行根左右次序遍历，中序遍历对二叉树进行左根右次序遍历，后续遍历对二叉树进行左右根遍历次序。 采用二叉链表实现各种遍历操作。 关键字： 二叉树 二叉链表 遍历 I第一章 问题定义1.1 课题：建立二叉树，层序、先序、中序、后序遍历（ 用递归或非递归的方法）以及中序线索化。1.2意义：通过以前的学习以及查看相关资料，按照题目要求编写程序，进一步加强

2、对编程的训练，使得自己掌握一些将书本知识转化为实际应用当中去，在整个程序中，主要应用的是链表，但也运用了栈。通过两种方法解决现有问题。1.3要求：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数； 实现二叉树的中序线索化。第二章 设计思路2.1中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：(1)遍历左子树；(2)访问根结点；(3)遍历右子树。2.1先序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：(1) 访问根结点；(2) 遍历

3、左子树；(3) 遍历右子树。2.2后序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：(1)遍历左子树；(2)遍历右子树；(3)访问根结点。第三章 数据结构定义二叉树定义：二叉树是另一种树形结构，（1）每个节点最多有两颗子树 。(2)子树有左右之分创建二叉树链表的结点存储结构及数据的输入函数。因为每个结点所存储的数据类型为字符串，却无法使用字符串和String等数据类型，所以使用单链表作为结点所存储的数据类型。以#表示空结点，利用先序遍历创建链表。 3.1用单链表s记录输入的数据。 3.2利用非递归调用分别生成根节点的左子树和右子树。3.3返回菜单重新选择。基本程序如下：void Cre

4、atBiTree_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; CreatBiTree_q(T-lchild); CreatBiTree_q(T-rchild);第四章 系统功能模块设计4.1调用生成二叉树的函数，从键盘输入二叉树的各个结点4.2分别调用先序遍历、中序遍历、后序遍历二叉树的函数，输出所有结点显示的菜单为： * 请选择遍历算法 1.按先序输入二叉树序列以#表示空节点 2.先序遍历二叉

5、树递非归算法 3.中序遍历二叉树非递归算法 4.后序遍历二叉树非递归算法 5.层次遍历二叉树非递归算法 6.中序线索遍历二叉树算法 0.按0退出endl 请输入序号（0，1,2,3,4,5,6）： A B C D E F G 输入的二叉树是：ABC#DE#F#G#（#代表空结点）输出的遍历应该是：先序遍历：A B C D E F G 中序遍历：C B E F D G A 后序遍历：C B G E F D A 层序遍历：A B C D E F G 中序线索化遍历：C B E F D G A第五章 运行与调试5.1菜单界面：5.2创建界面：5.3先序非遍历二叉树：5.4中序非遍历二叉树：5.5后序

6、非遍历二叉树：5.6层次遍历二叉树：5.7中序线索化，中序遍历：总 结实验开始时定义结构时，比细心，总会有或多或少的问题出现，如数据域和指针域定义的类型不一样，在实验过程中总有这样或那样的问题，在本次实验中，二叉树的先序，中序，后序遍历都是采用非递归调用，用起来稍微复杂，这使我更进一步学习和理解了树的遍历，更灵活地运用了指针与数组10附 录1程序清单#include #include #include #include #define Link 0#define Thread 1int right=0;typedef char TElemType; typedef struct BiTNode

7、 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); CreatBiT

8、ree_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; CreateBiTree(&(*T)-lchild); CreateBiTree(&(*T)-rchild); void PreOrderTraverse(BiTree &T) BiTree p,S20; int top=-1; p=T; do while(p!= NU

9、LL) cout datalchild; if( top -1 ) p=Stop; top-; p = p-rchild; while ( p != NULL ) |(top-1);int inorderTraverse(BiTree &T)BiTree p,s20;int i=-1;p=T;while(p|i-1)if(p)i+;si=p;p=p-lchild;elsep=si;cout ;coutdata;i-;p=p-rchild;return 0;void postorder (BiTree T) int s220,top=0; BiTree p,s120; p=T; do while

10、 (p!=NULL) s1top=p; s2top+=0; p=p-lchild; while(top & s2top-1=1) top-;p=s1top; cout ;coutdata; if(top0) s2top-1=1; p=s1top-1-rchild; while (top0); void LevelOrder(BiTree &b) BiTree qu20; int front,rear; front=rear=-1; rear+; qurear=b; while(front!=rear) front=(front+1)%20; b=qufront; printf( %c ,b-d

11、ata); if(b-lchild!=NULL) rear=(rear+1)%20; qurear=b-lchild; if(b-rchild!=NULL) rear=(rear+1)%20; qurear=b-rchild; void InThreading(BiTree p) if(p) InThreading(p-lchild); if(!p-lchild)/前驱线索 p-LTag=Thread; p-lchild=pre; if(!pre-rchild)/后继线索 pre-RTag=Thread; pre-rchild=p; pre=p; InThreading(p-rchild);

12、void InOrderThreading(BiTree *Thrt,BiTree T) if(!(*Thrt)=(BiTree)malloc(sizeof(BiTNode) exit(0); (*Thrt)-LTag=Link; (*Thrt)-RTag=Thread; (*Thrt)-rchild=(*Thrt); if(!T) (*Thrt)-lchild=(*Thrt); else (*Thrt)-lchild=T; pre=(*Thrt); InThreading(T); pre-rchild=(*Thrt); pre-RTag=Thread; (*Thrt)-rchild=pre;

13、 void InorderTraverse_Thr(BiTree &T) BiTree p; p=T-lchild; while(p!=T)p=T; while(p-LTag=Link) p=p-lchild; coutdata; while(p-RTag=Thread&p-rchild!=T) p=p-rchild;cout ; coutdata; p=p-rchild; int main() BiTree T,t; int e; while(e!=0) coutendl请选择遍历算法：endl; cout1.按先序输入二叉树序列以#表示空节点 endl; cout2.先序遍历二叉树递归算法

14、：endl; cout 3.中序遍历二叉树递归算法：endl; cout4.后序遍历二叉树递归算法： endl; cout5.层次遍历二叉树递归算法endl; cout6.中序线索遍历二叉树算法endl; cout0.按0退出endl; cout请输入序号（0，1,2,3,4,5,6）：e; coutendl; if(e=1) cout 按先序输入二叉树序列以#表示空节点： endl; CreateBiTree(&T); coutendl; if(e=2) cout 先序遍历递归算法是： endl; PreOrderTraverse(T); coutendl; if(e=3) cout 中序遍

15、历递归算法是： endl; inorderTraverse(T); coutendl; if(e=4) cout后序遍历的非递归算法是： endl; postorder (T); coutendl; if(e=5) printf(n层次遍历二叉树:n); LevelOrder(T); if(e=6) cout 按先序输入二叉树序列以#表示空节点： endl; CreatBiTree_q(T); coutendl; printf(中序线索化二叉树:n); InOrderThreading(&t,T); printf(线索化工作已经完成!中序遍历二叉树n); InorderTraverse_Thr(t); printf(n); return 0; 2参考资料【1】严蔚敏、吴伟民主编 数据结构（C语言版） 清华大学出版社 2002【2】殷人昆等著 数据结构（C+版） 清华大学出版社 2001【3】 金远平著 数据结构（C+描述） 清华大学出版社 2005【4】许卓群等著 数据结构与算法 高等教育出版社 2004【5】Frank M.Carrano 等著 数据结构与+高级教程清华大学出版社 2004 【6】严蔚敏、吴伟民 数据结构习题集（C语言版）清华大学出版社 2002 忽略此处. XI