数据结构实验+二叉树的操作.doc

文档介绍：实验三二叉树的操作1、实验目的1、掌握二叉树的逻辑结构;2、掌握二叉树的二叉链表存储结构;3、掌握基于二叉链表存储的二叉树的遍历操作的实现。2、实验内容1、采用二叉链表存储建立一棵含有n个结点的二叉树;2、前序打印该二叉树的所有叶子结点;3、统计该二叉树的结点个数;4、计算该二叉树的深度;5、交换该二叉树的所有左右子树。3、程序实现1、<classT>structBiNode{Tdata;BiNode<T>*lchild,*rchild;};2、<classT>structBiNode{Tdata;BiNode<T>*lchild,*rchild;};template<classT>classBiTree{public:BiTree();      //构造函数,初始化一棵二叉树,其前序序列由键盘输入~BiTree();    //析构函数,释放二叉链表中各结点的存储空间BiNode<T>*Getroot(); //获得指向根结点的指针voidPreOrder(BiNode<T>*root);  //前序遍历二叉树voidInOrder(BiNode<T>*root);   //中序遍历二叉树voidPostOrder(BiNode<T>*root);  //后序遍历二叉树voidLevelOrder(BiNode<T>*root); //层序遍历二叉树private:BiNode<T>*root;    //指向根结点的头指针BiNode<T>*Creat();  //有参构造函数调用voidRelease(BiNode<T>*root); //析构函数调用};template<classT>BiTree<T>::BiTree(){cout<<"请按前根序输入该二叉树的各个结点(#号表示为空):\n";this->root=Creat();}template<classT>BiNode<T>*BiTree<T>::Creat(){BiNode<T>*root;Tch;cin>>ch;if(ch=='#')root=NULL;else{root=newBiNode<T>;   //生成一个结点root->data=ch;root->lchild=Creat();  //递归建立左子树root->rchild=Creat();  //递归建立右子树}returnroot;}template<classT>BiTree<T>::~BiTree(){Release(root);}template<classT>BiNode<T>*BiTree<T>::Getroot(){returnroot;}template<classT>voidBiTree<T>::PreOrder(BiNode<T>*root){if(root==NULL) return;else{    cout<<root->data<<"";PreOrder(root->lchild);PreOrder(root->rchild);}}template<classT>voidBiTree<T>::InOrder(BiNode<T>*root){if(root==NULL) return;   //递归调用的结束条件       else{  InOrder(root->lchild);  //中序递归遍历root的左子树cout<<root->data<<"";  //访问根结点的数据域InOrder(root->rchild);  //中序递归遍历root的右子树}}template<classT>voidBiTree<T>::PostOrder(BiNode<T>*root){if(root==NULL) return;   //递归调用的结束条件else{  PostOrder(root->lchild);  //后序递归遍历root的左子树PostOrder(root->rchild);  //后序递归遍历root的右子树cout<<root->data<<"";   //访问根结点的数据域}}template<classT>voidBiTree<T>::LevelOrder(BiNode<T>*root){constintMaxSize=100;intfront=0;intrear=0; //采用顺序队列,并假定不会发生上溢BiNode<T>*Q[MaxSize];BiNode<T>*q;if(root==NULL)return;else{Q[rear++]=root;while(front!=rear){q=Q[front++];cout<<q->data<<