题目：建立二叉树和二叉树的基本操作
姓名： 学号：
一、程序功能：（如图）
二、详细设计
1. 元素类型、结点类型和指针类型
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct QNode{
char data;
struct QNode *next;
}QNode,*QueuePtr;
2．几个基本操作的函数
1.
BiTNode *Makenode(char ch){
BiTNode *p;
p=(BiTNode*)malloc(sizeof(BiTNode));
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;
return p;
}
2.
BiTree Creat(){
BiTree p;
char ch;
scanf("%c",&ch);
if(ch=='#')
return NULL;
else
p=(BiTNode*)malloc(sizeof(BiTNode));
p->data=ch;
p->lchild=Creat();
p->rchild=Creat();
return p;
}
3.
void exchange(BiTree bt){//交换左右子树
BiTNode *p;
p=(BiTNode*)malloc(sizeof(BiTNode));
if(!bt) return;
p=bt->lchild;
bt->lchild=bt->rchild;
bt->rchild=p;
exchange(bt->lchild);
exchange(bt->rchild);
}
4.
void level(BiTree bt,int lev){//层次遍历
if(!bt) return;
lev++;
printf("%c%d",bt->data,lev);
printf("\n");
level(bt->lchild,lev);
level(bt->rchild,lev);
}
3. 主函数
void main(){
int n,m,u,mune;
add: printf("先序建立二叉树(请输入)：\n");
BiTree bt,p;
bt=Creat();
while(1)
{printf("\n");
printf("0--退出\n");
printf("1--先序遍历\n");
printf("2--中序遍历\n");
printf("3--后续遍历\n");
printf("4--复制\n");
printf("5--结点数\n");
printf("6--叶子树\n");
printf("7--高度\n");
printf("8--层次遍历\n");
printf("9--交换左右子树\n");
printf("10--销毁\n");
printf("请选择：0-10");
printf("\n");
scanf("%d",&mune);
switch(mune){
case 0:
return;
case 1:
preorder(bt);
break;
case 2:
inorder(bt);
break;
case 3:
postorder(bt);
break;
case 7:
m=height(bt);
printf("高度为：%d",m);
break;
case 5:
n=Number(bt);
printf("节点数为：%d",n);
break;
case 6:
u=Leafs(bt);
printf("叶子树为：%d",u);
break;
case 8:
level(bt,0);
break;
case 9:
exchange(bt);
preorder(bt);
printf("\n");
inorder(bt);
printf("\n");
postorder(bt);
printf("\n");
break;
case 4:
CopyTree(bt,p);
preorder(p);
break;
case 10:
destory(bt);
break;
default :
printf("error");
printf("\n");
goto add; }
}
}
分析体会：
1.编写程序时最好先明确思路，二叉树程序多是递归调用，体现了结构决定功能，因此要掌握并熟练运用递归调用。
2.二叉树对创建时输入要求高，要先想好再输入。我在调制时，有时输入错误会进入死循环，无法操作，只能关闭程序重新打开。为此我使用goto语句，跳出死循环。
3.收获了一些技巧，编写时要注意细节，比如C++不识别汉字字符（；和;是有区别的）。
4. 刚开始时，忽略了一些变量参数的标识"&",使调试程序时费了不少功夫。应注重确定参数的变量和属性。
总结：
通过两次实验收获了许多知识，积累到很多经验。无论从编写程序的难度还是质量都比以前有了很大的提升，在编写程序时已基本避免语句错误。在二叉树运算器中多次用到了递归调用。在编写程序过程中懂得了从系统的角度出发，按照合理的步骤和方法，提高编译效率。
操作截图
第二篇：实验二 二叉树实验报告
实验二 二叉树实验报告
110228 刘宇 11021199
1. 实验目的
掌握二叉树的存储结构
2. 实验内容
1．对给定二叉树用链式存储结构；利用队列与栈对二叉树进行运算。
2．按层次输出所有结点。
3．输出所有叶子结点。
4．将所有左右子树值交换。
3. 实验步骤和要求
1．分别编制实验内容中题2、3、4的三个子程序。
2．以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。
（1）输入二叉树用链式结构存储；
（2）调用题2的子程序，并输出结果；
（3）调用题3的子程序，并输出结果；
（4）调用题4的子程序，并输出结果；
3．自行设计一棵二叉树，重复步骤2。
4．整理程序清单与所有结果，并写出实验报告。
4. 方法说明
（1）二叉树的链式存储结构
二叉树的每一个结点i有三个域：值域V（i），左链域L（i），右链域R（i）。我们分别用三个一维数组表示它们，并用头指针HBT指向二叉树的根结点。具体存储方案由读者自行考虑。
（2）按层次输出所有结点
为了达到按层次扫描结点的目的，需要设置一个容量足够大的循环队列（可以用一个首尾相接的一维数组模拟）。初始时，将根结点序号入队。然后每次从队列中退出一个结点序号，将此结点的值及左右链指针输出，且依次将此结点的左右链指针入队。
（3）输出所有叶子结点
叶子结点的左右指针域均为零。因此，为了输出所有叶子结点，需要设置一个容量足够大的栈S（ 可以用一个一维数组模拟它，栈底在数组的第一个元素处）。具体过程是：从根结点开始扫描二叉树，如果扫描的当前结点的左右均为零，则输出次叶子结点；否则将非零的右指针和左指针值推入堆栈。然后从栈中退出一个结点序号重新进行这个过程，直至栈空为止。
（4）将所有左右子树值交换
这个问题的处理和输出所有叶子结点的问题很类似，只要将非叶子结点的左右指针交换即可，其算法如下：
五、程序代码：
#include<iostream> #include<fstream> using namespace std; struct tnode //链式存储节点 { int data,lv; tnode *left,*right; }; struct lnode //单向链表节点 用来实现队列和栈 { tnode* data; lnode *next; }; class myList // 列表类 提供初始化，插入，读取，删除，清除方法 { private: lnode *rear,*last; public: void Linit() //
{ rear = (lnode *)malloc(sizeof(lnode)); last = rear; last->next = NULL; last->data = NULL; } bool Lempty() //judging afterward required { if(last==rear) return true; else return false; } void insert(tnode* d) { lnode *p; p = (lnode *)malloc(sizeof(lnode)); p->data = d; last->next=p; p->next=NULL; last = p; } lnode* read() { lnode *p; p = rear; if(rear->next) rear = rear->next; else cout<<"The list is empty!\n"; return p; } }; class myStack // 栈类 提供初始化，压栈，出栈，销毁方法 { private: lnode *top; public: void Sinit() { top = (lnode *)malloc(sizeof(lnode)); top->data=NULL; top->next=NULL; } void push(tnode* d) { lnode *p; p = (lnode *)malloc(sizeof(lnode)); p->data = d; p->next = top; top = p; } lnode* pop() { lnode *p; if(top->next) { p=top; top=top->next;
return p; } else { cout<<"The Stack is Empty!\n"; return NULL; } } bool Sempty() { if(top->next==NULL) return true; return false; } }; class biTree // 二叉树类 提供初始化，先序建树，按层读取，交换等方法 { private: tnode *r,*p; public: tnode* getRoot() { return r; } void Tinit() { r = (tnode *)malloc(sizeof(tnode)); r->data = -1; r->left = NULL; r->right = NULL; r->lv=0; } tnode* firstCreate(tnode *t,int l) { int ad; t = (tnode *)malloc(sizeof(tnode)); cin>>ad; t->data = ad; t->lv=l; if(ad!=0) { t->left=firstCreate(t->left,l+1); t->right=firstCreate(t->right,l+1); } return t; } void lvlRead(tnode *t) { tnode *q; lnode *p; myList ml; ml.Linit(); ml.insert(t); //ml.read(); do { p=ml.read(); p=p->next;
q=p->data; if(q->data) { cout<<q->data<<' '; ml.insert(q->left); ml.insert(q->right); } else { if(ml.Lempty()) break; } }while(!ml.Lempty()); } void leafRead(tnode *t) { tnode *q,*l,*r; lnode *p; myStack ms; ms.Sinit(); ms.push(t); do { p=ms.pop(); q=p->data; l=q->left; r=q->right; if(l->data==0 && r->data==0) cout<<q->data<<' '; else { if(r->data!=0) ms.push(r); if(l->data!=0) ms.push(l); } }while(!ms.Sempty()); } void allReverse(tnode *t) { tnode *q,*l,*r,*tmp; lnode *p; myStack ms; ms.Sinit(); ms.push(t); do { p=ms.pop(); q=p->data; l=q->left; r=q->right; if(l->data!=0 || r->data!=0) { tmp = q->left; q->left = q->right; q->right = tmp; } if(l->data!=0) ms.push(l); if(r->data!=0) ms.push(r); }while(!ms.Sempty()); } void firstTrav(tnode *t)
{ int m; tnode *l,*r; l=t->left; r=t->right; m=t->data; if(m) { cout<<m<<' '; if(l->data) firstTrav(l); if(r->data) firstTrav(r); } } void midTrav(tnode *t) { int m; tnode *l,*r; l=t->left; r=t->right; m=t->data; if(m) { if(l->data) firstTrav(l); cout<<m<<' '; if(r->data) firstTrav(r); } } }; int main() { int i,j,n; tnode *rt; biTree bt; rt=bt.getRoot(); //使用rt指针记录指向二叉树的根节点 //使用firstCreate函数以先序序列建立二叉树，0表示结束节点 rt=bt.firstCreate(rt,0); //先序打印所有节点 cout<<"先序打印二叉树：\n"; bt.firstTrav(rt); cout<<endl; //使用lvlRead()方法按层打印所有节点 cout<<"按层打印二叉树：\n"; bt.lvlRead(rt); cout<<endl; //使用leafRead()方法打印所有叶节点 cout<<"打印二叉树所有叶子节点：\n"; bt.leafRead(rt); cout<<endl; //使用leafRead()方法交换所有左右节点 bt.allReverse(rt); cout<<"二叉树交换后先序打印：\n"; bt.firstTrav(rt); //先序打印所有节点 //system("pause"); return 0; }
六、结果分析
编制实验内容中题2、3、4的三个子程序。
按先序输入以上二叉树15 98 20 30 0 0 40 0 0 10 0 0 6 0 45 0 60 70 0 0 0,其中0代表结尾。存入链式存储结构。
1、 分别按先序打印二叉树；
2、 按层打印二叉树；
2．以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。
（1）输入二叉树用链式结构存储；
（2）调用题2的子程序，并输出结果；
（3）调用题3的子程序，并输出结果；
（4）调用题4的子程序，并输出结果；
3．自行设计一棵二叉树，重复步骤2。
如图，先序序列为13 5 4 1 0 0 12 0 0 0 21 0 31 0 0
结果：
七、实验反思：
本次实验中使用链式结构直观的构造了二叉树数据结构，同时，构造了一维的队列和栈对二叉树的搜索和遍历进行辅助存储。其中实现二叉树时，以特殊符号标记结束节点，方便输入和建立二叉树，
使得使用唯一确定的先序序列即可表
达二叉树。递归建立二叉树时，需要注意返回二叉树子树的根节点地址给上级节点左右子节点记录。实现队时，使用单向链表，在堆动态分配存储空间，空间效率更高。基于面向对象思想，设计了二叉树类，具体实现了初始化，先序遍历，按层遍历，交换左右节点的接口，可扩展性较强。