实验三、二叉树的基本操作

实验三、二叉树的基本操作实验三、二叉树的基本操作实验三、二叉树的基本操作xxx公司实验三、二叉树的基本操作文件编号：文件日期：修订次数：第1.0次更改批准审核制定方案设计，管理制度实验三二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容题目一：二叉树的基本操作实现（必做题）[问题描述]建立一棵二叉树，试编程实现二叉树的如下基本操作：

1.按先序序列构造一棵二叉链表表示的二叉树T；

2.对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；

3.求二叉树的深度/结点数目/叶结点数目；(选做)

4.将二叉树每个结点的左右子树交换位置。（选做）[基本要求]从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），[测试数据]如输入：ABCффDEфGффFффф（其中ф表示空格字符）

则输出结果为先序：ABCDEGF

中序：CBEGDFA

后序：CGEFDBA层序：ABCDEFG[选作内容]采用非递归算法实现二叉树遍历。算法设计主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后用指针对树进行操作，重点掌握二叉树的结构和性质。本程序包含四个模块：结构体定义（2）创建二叉树（3）对树的几个操作（4）主函数调试分析这是一个比较简单程序，调试过程中并没有出现什么问题，思路比较清晰实验结果总结此次上机实验对二叉树进行了以一次实际操作，让我对二叉树有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。七、源程序#include<iostream>#include<queue>usingnamespacestd;#defineTElemTypechar#defineStatusint#defineOK1#defineERROR0typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;StatusCreateBiTree(BiTree&T){ TElemTypech; cin>>ch; if(ch=='#') T=NULL; else { if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } returnOK;}StatusPreOrderTraverse(BiTreeT){ if(T) { cout<<T->data; if(PreOrderTraverse(T->lchild)) if(PreOrderTraverse(T->rchild)) returnOK; returnERROR; } else returnOK;}StatusInOrderTraverse(BiTreeT){ if(T) { InOrderTraverse(T->lchild); cout<<T->data; InOrderTraverse(T->rchild); } returnOK;}StatusPostOrderTraverse(BiTreeT){ if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data; } returnOK;}StatusleOrderTraverse(BiTreeT){ std::queue<BiTree>Q; if(T==NULL)returnERROR; else{ (T); while(!()) { T=(); (); cout<<T->data; if(T->lchild!=NULL) (T->lchild); if(T->rchild!=NULL) (T->rchild); } } returnOK;}Statuschange(BiTreeT){ BiTreetemp=NULL; if(T->lchild==NULL&&T->rchild==NULL) returnOK; else{ temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; } if(T->lchild) change(T->lchild); if(T->rchild) change(T->rchild); returnOK;}intFindTreeDeep(BiTreeT){ intdeep=0; if(T){ intlchilddeep=FindTreeDeep(T->lchild); intrchilddeep=FindTreeDeep(T->rchild); deep=lchilddeep>=rchilddeeplchilddeep+1:rchilddeep+1; } returndeep;}intmain(){ BiTreeT; CreateBiTree(T); cout<<"先序遍历顺序为："; PreOrderTraverse(T); cout<<endl; cout<<"中序遍历顺序为："; InOrderTraverse(T); cout<<endl; cout<<"后序遍历顺序为："; PostOrderTraverse(T); cout<<endl; cout<<"层序遍历顺序为："; leOrderTraverse(T); cout<<endl;