《数据结构》课程设计报告学号姓名班级指导教师安徽工业大学计算机学院2010年6月建立二叉树和线索二叉树1.问题描述：分别用以下方法建立二叉树并用图形显示出来：1）用先序遍历的输入序列2）用层次遍历的输入序列3）用先序和中序遍历的结果2.设计思路：分三个方式去实现这个程序的功能，第一个实现先序遍历的输入数列建立二叉树；第二个是用层次遍历的方法输入序列；第三个是用先序和后序遍历的结果来建立二叉树；三种方法建立二叉树后都进行输出。

关键是将这三个实现功能的函数写出来就行了；最后对所建立的二叉树进行中序线索化，并对此线索树进行中序遍历（不使用栈）。

3.数据结构设计：该程序的主要目的就是建立二叉树和线索二叉树，所以采用树的存储方式更能完成这个程序；结点的结构如下：typedef struct bnode {DataType data;int ltag,rtag;struct bnode *lchild, *rchild;} Bnode, *BTree;4.功能函数设计：BTree CreateBinTree()用先序遍历的方法讲二叉树建立；BTree CREATREE()用队列实现层次二叉树的创建；void CreatBT()；用先序和中序遍历的结果建立二叉树；void InThread(BTree t,BTree pre)中序线索化；5.编码实现：#include<iostream.h>#include<stdlib.h>#define max 100typedef struct bnode{char data;int ltag,rtag;struct bnode *lchild,*rchild;}Bnode,*BTree;BTree Q[max];BTree CREATREE(){char ch;int front=1,rear=0;BTree root,s;root=NULL;cout<<"'@'表示'空','#'表示'结束'"<<endl;cin>>ch;while(ch!='#'){s=NULL;if(ch!='@'){s=(BTree)malloc(sizeof(Bnode));s->data=ch;s->lchild=NULL;s->rchild=NULL;}rear++;Q[rear]=s;if(rear==1) root=s;else{if(s&&Q[front])if(rear%2==0) Q[front]->lchild=s;else Q[front]->rchild=s;if(rear%2==1) front++;}cin>>ch;}return root;}int search(char ino[],char pre)//在中序序列中查找先序中该元素所在位置{int i=0;while(ino[i]!=pre&&ino[i])i++;if(ino[i]==pre)return i;elsereturn -1;}void CreatBT(BTree &T,char pre[],char ino[],int ps,int is,int n){int k;if(n==0)T=NULL;elsek=search(ino,pre[ps]);if(k==-1)cout<<"error!";else{T=(Bnode*)malloc(sizeof(Bnode));T->data=pre[ps];if(k==is)T->lchild=NULL;elseCreatBT(T->lchild,pre,ino,ps+1,is,k-is);if(k==is+n-1)T->rchild=NULL;elseCreatBT(T->rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1);}}}BTree CreateBinTree(){BTree T;char ch;cin>>ch;if(ch=='#') T=NULL;else{T=(BTree)malloc(sizeof(Bnode));T->data=ch;T->ltag=T->rtag=0;T->lchild=CreateBinTree();T->rchild=CreateBinTree();}return T;}void Preorder(BTree T){if(T){cout<<T->data<<" ";Preorder(T->lchild);Preorder(T->rchild);}void Inorder(BTree T){if(T){Inorder(T->lchild);cout<<T->data<<" ";Inorder(T->rchild);}}void Postorder(BTree T){if(T){Postorder(T->lchild);Postorder(T->rchild);cout<<T->data<<" ";}}void InThread(BTree t,BTree pre)//中序线索化{if(t){InThread(t->lchild,pre);if(t->lchild==NULL){t->ltag=1;t->lchild=pre;}if(t->rchild==NULL)t->rtag=1;if((pre)&&(pre->rtag==1))pre->rchild=t;pre=t;InThread(t->rchild,pre);}}BTree InPostNode(BTree p){BTree post;post=p->rchild;if(p->rtag==1)return post;else while(post->ltag==0)post=post->lchild;return post;}void InOrderTh(BTree t)//中序线索化遍历{BTree p;if(t){p=t;while(p->ltag==0)p=p->lchild;while(p){cout<<p->data;p=InPostNode(p);}}}void main(){BTree T;int choice1,choice2;cout<<"建立二叉树的方式："<<endl;cout<<"-----------------------"<<endl;cout<<"1、先序遍历的输入序列："<<endl;cout<<"2、层次遍历的输入序列："<<endl;cout<<"3、先序和中序遍历的结果："<<endl;cout<<"0、退出"<<endl;cout<<"-----------------------"<<endl;while(1){cout<<"你的选择:";cin>>choice1;switch(choice1){case 1:cout<<"请输入结点的信息："<<endl;T=CreateBinTree();do{cout<<endl;cout<<"请选择：1.先序遍历 2.中序遍历 3.后序遍历(输入0结束)"<<endl;cin>>choice2;switch(choice2){case 1:Preorder(T); break;case 2:Inorder(T); break;case 3:Postorder(T);break;case 0:break;}}while(choice2!=0);cout<<endl;cout<<"中序线索化的实现："<<endl;InThread(T,NULL);InOrderTh(T);cout<<endl;break;case 2:BTree tree;tree=CREATREE();do{cout<<endl;cout<<"请选择：1.先序遍历 2.中序遍历 3.后序遍历(输入0结束)"<<endl;cin>>choice2;switch(choice2){case 1:Preorder(tree); break;case 2:Inorder(tree); break;case 3:Postorder(tree);break;case 0:break;}}while(choice2!=0);cout<<endl;break;case 3:char pre[max],ino[max];cout<<"输入先序序列：(提示：ABDECF)";cin>>pre;cout<<"输入中序序列：(提示：DBEAFC)";cin>>ino;BTree TR;TR=NULL;CreatBT(TR,pre,ino,0,0,7);cout<<"先序遍历的二叉树：";Preorder(TR);cout<<endl;cout<<"中序遍历的二叉树：";Inorder(TR);cout<<endl;cout<<"后序遍历的二叉树：";Postorder(TR);cout<<endl;break;case 0:exit(0);}}}6.运行与测试：选择1.用先序遍历的输入序列选择2.用层次遍历的输入序列选择3.用先序和中序遍历的结果学生成绩查询系统1.问题描述：编写程序完成学生成绩记录的查询若按学号进行顺序查找，例如：输入99070103，则输出该学生的信息；按学号排序后对学号进行折半查找；随机输入以学号为关键字的学生信息并构建二叉排序树，对学号进行二叉排序树查找。