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

《实验三、二叉树的基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验三二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容题目一：二叉树的基本操作实现（必做题）[问题描述]建立一棵二叉树，试编程实现二叉树的如下基本操作：1.按先序序列构造一棵二叉链表表示的二叉树T；2.对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3.求二叉树的深度/结点数目/叶结点数目；(选做)4.将二叉树每个结点的左右子树交换位置。（选做）[基本要求]从键盘接受输入（先序），以二叉链表作为存储

2、结构，建立二叉树（以先序来建立），[测试数据]如输入：ABCффDEфGффFффф（其中ф表示空格字符）　　则输出结果为先序：ABCDEGF　　中序：CBEGDFA　　后序：CGEFDBA层序：ABCDEFG[选作内容]采用非递归算法实现二叉树遍历。三、算法设计1、主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后用指针对树进行操作，重点掌握二叉树的结构和性质。2、本程序包含四个模块：（1）结构体定义（2）创建二叉树（3）对树的几个操作（4）主函数三、调试分析这是一个比较简单程序，调试过

3、程中并没有出现什么问题，思路比较清晰四、实验结果五、总结此次上机实验对二叉树进行了以一次实际操作，让我对二叉树有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。七、源程序#include#includeusingnamespacestd;#defineTElemTypechar#defineStatusint#defineOK1#defineERROR0typedefstructBiTNode{TElem

4、Typedata;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);}returnO

5、K;}StatusPreOrderTraverse(BiTreeT){if(T){cout<data;if(PreOrderTraverse(T->lchild))if(PreOrderTraverse(T->rchild))returnOK;returnERROR;}elsereturnOK;}StatusInOrderTraverse(BiTreeT){if(T){InOrderTraverse(T->lchild);cout<data;InOrderTraverse(T->r

6、child);}returnOK;}StatusPostOrderTraverse(BiTreeT){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout<data;}returnOK;}StatusleOrderTraverse(BiTreeT){std::queueQ;if(T==NULL)returnERROR;else{Q.push(T);while(!Q.empty()){T=Q.

7、front();Q.pop();cout<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=te

8、mp;}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:rchilddee