数据结构二叉树操作验证实验报告

班级：计算机学号：姓名：成绩：_________实验七二叉树操作验证实验目的⑴掌握二叉树的逻辑结构；⑵掌握二叉树的二叉链表存储结构；⑶掌握基于二叉链表存储的二叉树的遍历操作的实现。。实验内容⑴建立一棵含有n个结点的二叉树，采用二叉链表存储；⑵前序（或中序、后序）遍历该二叉树。设计与编码#include<iostream>usingnamespacestd;template<classT>classBTree;template<classT>//***********************二叉树结点类定义**********************classBTreeNode{friendclassBTree<T>;Tdata;BTreeNode<T>*lchild,*rchild;public:BTreeNode():lchild(NULL),rchild(NULL){}BTreeNode(Td,BTreeNode<T>*l=NULL,BTreeNode<T>*r=NULL):data(d),lchild(l),rchild(r){}Tgetdata(){returndata;}BTreeNode<T>*getleft(){returnlchild;}BTreeNode<T>*getright(){returnrchild;}};//***********************END********************************//***********************二叉树模板类定义*******************template<classT>classBTree{public:BTree(Ta[],intn);voidpreorder(voidvisit(BTreeNode<T>*p));staticvoidpreorder(BTreeNode<T>*p,voidvisit(BTreeNode<T>*p));//递归前序遍历voidinorder(voidvisit(BTreeNode<T>*p));staticvoidinorder(BTreeNode<T>*p,voidvisit(BTreeNode<T>*p));//递归中序遍历voidpostorder(voidvisit(BTreeNode<T>*p));staticvoidpostorder(BTreeNode<T>*p,voidvisit(BTreeNode<T>*p));//递归后序遍历staticvoidfun(BTreeNode<T>*p){cout<<p->data;}//访问结点protected:BTreeNode<T>*root;private:T*a;intn;BTreeNode<T>*build0(inti);};//***********************建树*******************************template<classT>BTreeNode<T>*BTree<T>::build0(inti)//递归建树{BTreeNode<T>*p;intl,r;if((i<=n)&&(a[i-1]!='')){p=newBTreeNode<T>;p->data=a[i-1];l=2*i;r=2*i+1;p->lchild=build0(l);p->rchild=build0(r);return(p);}elsereturn(NULL);}template<classT>BTree<T>::BTree(Ta[],intn){this->a=a;this->n=n;root=build0(1);cout<<"递归建树成功!"<<endl;};//***********************END********************************//***********************遍历*******************************template<classT>voidBTree<T>::preorder(voidvisit(BTreeNode<T>*p))//递归前序遍历{preorder(root,visit);cout<<endl;}template<classT>voidBTree<T>::preorder(BTreeNode<T>*p,voidvisit(BTreeNode<T>*p)){if(p!=NULL){visit(p);preorder(p->lchild,visit);preorder(p->rchild,visit);}}template<classT>voidBTree<T>::inorder(voidvisit(BTreeNode<T>*p)){inorder(root,visit);cout<<endl;}template<classT>voidBTree<T>::inorder(BTreeNode<T>*p,voidvisit(BTreeNode<T>*p)){if(p!=NULL){inorder(p->lchild,visit);visit(p);inorder(p->rchild,visit);}}template<classT>voidBTree<T>::postorder(voidvisit(BTreeNode<T>*p))//递归后序遍历{postorder(root,visit);cout<<endl;}template<classT>voidBTree<T>::postorder(BTreeNode<T>*p,voidvisit(BTreeNode<T>*p)){if(p!=NULL){postorder(p->lchild,visit);postorder(p->rchild,visit);visit(p);}}voidmain(){char*str="abcde";cout<<str<<endl;BTree<char>s(str,6);cout<<endl;cout<<str<<endl;cout<<endl;while(1){cout<<"────────────请选择操作─────────────"<<endl;cout<<"递归的先序遍历：1+回车"<<endl;cout<<"递归的中序遍历：2+回车"<<endl;cout<<"递归的后序遍历：3+回车"<<endl;cout<<"──────────────────────────────"<<endl;cout<<"请选择：";intchoice;cin>>choice;cout<<endl;switch(choice){case1:{if(str){cout<<"递归先序遍历二叉树：";s.preorder(s.fun);cout<<endl;}elsecout<<"二叉树为空！"<<endl;break;}case2:{if(str){cout<<"递归中序遍历二叉树：";s.inorder(s.fun);cout<<endl;}elsecout<<"二叉树为空！"<<endl;break;}case3:{if(str){cout<<"递归后序遍历二叉树：";s.postorder(s.fun);cout<<endl;}elsecout<<"二叉