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

。实验三 二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容题目一：二叉树的基本操作实现 （必做题）[问题描述]建立一棵二叉树，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树 T；对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；求二叉树的深度/结点数目/叶结点数目；(选做)将二叉树每个结点的左右子树交换位置。（选做）[基本要求]从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），[测试数据]如输入：ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA层序：ABCDEFG[选作内容]采用非递归算法实现二叉树遍历。三、 算法设计1、 主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后用指针对树进行操作，重点掌握二叉树的结构和性质。2、 本程序包含四个模块：（1）结构体定义精选资料，欢迎下载。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;}elsereturnOK;}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{Q.push(T);while(!Q.empty()){T=Q.front();Q.pop();cout<<T->data;if(T->lchild!=NULL)Q.push(T->lchild);if(T->rchild!=NULL)Q.push(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>=rchilddeep?lchilddeep+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;cout<<" 二叉树深度为："<<FindTreeDeep(T)<<endl;cout<<