二叉树应用——二叉树基本算法的实现【功能要求】实现Create方法，要求键盘输入二叉树结点序列，创建一棵二叉树（提示：前序递归）实现SwapTree方法，以根结点为参数，交换每个结点的左子树和右子树（提示：前序递归）增加InorderTree方法，采用非递归方法实现二叉树的中序遍历你可以选择：对BinaryTree模板进行功能扩充；自己定义并实现二叉树类要求键盘输入二叉树结点序列结点序列可以是前序，也可以是层次空结点以#表示【代码实现】// 二叉树01.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream>using namespace std;template<class T>class BinaryTreeNode;template<class T>class BinaryTree{public:BinaryTree(){root=0;}BinaryTree(const BinaryTree<T> &Tree ){copy(Tree.root,root);}~BinaryTree(){};bool IsEmpty()const{return ((root)?false:true);}void Creat();bool Root (T&x)const;void MakeTree(const T&element,BinaryTree<T>&left,BinaryTree<T>&right); void BreakTree( T&element,BinaryTree<T>&left,BinaryTree<T>&right); void PreOrder(void (*Visit)(BinaryTreeNode<T>*u)){PreOrder(Visit,root);}void InOrder(void (*Visit)(BinaryTreeNode<T>*u)){InOrder(Visit,root);}void PostOrder(void (*Visit)(BinaryTreeNode<T>*u)){PostOrder(Visit,root);}void LevelOrder(void(*Visit)(BinaryTreeNode<T>*u));void PreOutput(){PreOrder(Output,root);cout<<endl;}void InOutput(){InOrder(Output,root);cout<<endl;}void Postput(){PostOrder(Output,root);cout<<endl;}void LevelOutPut(){LevelOrder(Output);cout<<endl;}void Delete(){PostOrder(Free,root);root=0;}int Height()const{return Height(root);}int Size()const{return Size(root);}BinaryTreeNode<T>*iCreat();bool equal(BinaryTree<T>&Tree){return compare(root,Tree.root);}void swap(){swap(root);}int leave(){return leave(root);}int noleave(){return noleave(root);}private:BinaryTreeNode<T>*root;void PreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);void InOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);void PostOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);static void Output(BinaryTreeNode<T>* t){cout<<t->data <<" ";}static void Free(BinaryTreeNode<T>*t){delete t;}int Height(BinaryTreeNode<T>*t)const;int Size(BinaryTreeNode<T>*t)const;bool compare(BinaryTreeNode<T>*t1,BinaryTreeNode<T>*t2);void copy(const BinaryTreeNode<T>*t1,BinaryTreeNode<T>*&t2);void swap(BinaryTreeNode<T>*t);int leave(BinaryTreeNode<T>*t);int noleave(BinaryTreeNode<T>*t);};template<class T>class LinkedQueue;template<class T>class Node{friend LinkedQueue<T>;private:T data;Node<T>*link;};template<class T>class LinkedQueue{public:LinkedQueue(){front=rear=0;}~LinkedQueue();bool IsEmpty()const{return ((front)?false:true);}bool IsFull()const;T First()const;T Last()const;LinkedQueue<T>&Add(const T &x);LinkedQueue<T>&Delete(T&x); private:Node<T>*front;Node<T>*rear;};template<class T>bool BinaryTree<T>::Root(T&x)const {if(root){x=root->data;return true;}else return false;}template<class T>void BinaryTree<T>::MakeTree(const T &element ,BinaryTree<T>&left,BinaryTree<T>&right){root=new BinaryTreeNode<T>(element,left.root,right.root);left.root=right.root=0;}template<class T>voidBinaryTree<T>::BreakTree(T&element ,BinaryTree<T>&left,BinaryTree<T>&right) {element=root->data;left.root=root->LeftChild;right.root=root->RightChild;delete root;root=0;}template<class T>voidBinaryTree<T>::PreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T> *t){if(t){Visit(t);PreOrder(Visit,t->LeftChild);PreOrder(Visit,t->RightChild);}}template<class T>voidBinaryTree<T>::InOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>* t){if(t){InOrder(Visit,t->LeftChild);Visit(t);InOrder(Visit,t->RightChild);}}template<class T>voidBinaryTree<T>::PostOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T >*t){if(t){PostOrder(Visit,t->LeftChild);PostOrder(Visit,t->RightChild);Visit(t);}}template<class T>void BinaryTree<T>::LevelOrder(void(*Visit)(BinaryTreeNode<T>*u)){LinkedQueue<BinaryTreeNode<T>*> Q;BinaryTreeNode<T>*t;t=root;while(t){Visit(t);if(t->LeftChild) Q.Add(t->LeftChild);if(t->RightChild) Q.Add(t->RightChild);if(Q.IsEmpty()) return ;else Q.Delete(t);}}template<class T>int BinaryTree<T>::Height(BinaryTreeNode<T>*t)const{if(!t) return 0;int hl=Height(t->LeftChild);int hr=Height(t->RightChild);if(hl>hr) return ++hl;else return ++hr;}template<class T>int BinaryTree<T>::Size(BinaryTreeNode<T>*t)const{if(!t) return 0;int sl=Size(t->LeftChild);int sr=Size(t->RightChild);return (1+sl+sr);}template<class T>BinaryTreeNode<T>*BinaryTree<T>::iCreat( ){T ch;cin>>ch;BinaryTreeNode<T> * root;if(ch=='#'){root=NULL;}else{root=new BinaryTreeNode<T>;root->data=ch;root->LeftChild=this->iCreat();root->RightChild=this->iCreat();}return root;}template<class T>void BinaryTree<T>::Creat(){this->root = iCreat();}template<class T>bool BinaryTree<T>::compare(BinaryTreeNode<T> *t1, BinaryTreeNode<T> *t2) {if (t1==NULL&&t2==NULL) return true;else if (t1!=NULL&&t2==NULL) return false;else if (t1==NULL&&t2!=NULL) return false;else if (t1->data!=t2->data) return false;elsereturn(compare(t1->leftChild,t2->leftChild)&&compare(t1->RightChild,t2->RightChi ld));}template<class T>void BinaryTree<T>::copy(const BinaryTreeNode<T>*t1,BinaryTreeNode<T>*&t2) {if(t1){t2=new BinaryTreeNode<T>;t2->data=t1->data;copy(t1->LeftChild,t2->LeftChild);copy(t1->RightChild,t2->RightChild);}}template<class T>void BinaryTree<T>::swap(BinaryTreeNode<T> *t){BinaryTreeNode<T> *temp;if(!t) return;else{temp=t->LeftChild;t->LeftChild=t->RightChild;t->RightChild=temp;swap(t->leftChild);swap(t->RightChild);}}template<class T>int BinaryTree<T>::leave(BinaryTreeNode<T>*t){if(!t) return 0;if(t->LeftChild==0&&t->RightChild==0)return 1;int leafl=leave(t->LeftChild);int leafr=leave(t->RightChild);return leafl+leafr;}template<class T>int BinaryTree<T>::noleave(BinaryTreeNode<T> *t){if(!t) return 0;if(!t->LeftChild&&!t->RightChild)return 0;int leafl=noleave(t->LeftChild);int leafr=noleave(t->RightChild);return leafl+leafr+1;}template<class T>class BinaryTree;template<class T>class BinaryTreeNode{friend BinaryTree<T>;public:BinaryTreeNode(){LeftChild=RightChild=0;}BinaryTreeNode(const T&e){data=e;LeftChild=RightChild=0;}BinaryTreeNode(const T&e,BinaryTreeNode *l,BinaryTreeNode *r) {data=e;LeftChild=l;RightChild=r;}private:T data;BinaryTreeNode<T>*LeftChild,*RightChild;};template<class T>LinkedQueue<T>::~LinkedQueue(){Node<T>*next;while(front){next=front->link;delete front;front=next;}}template<class T>LinkedQueue<T>&LinkedQueue<T>::Add(const T &x) {Node<T>*p=new Node<T>;p->data=x;p->link=0;if (front) rear->link=p;else front=p;rear=p;return *this;}template<class T>LinkedQueue<T>&LinkedQueue<T>::Delete(T&x) {x=front->data;Node<T>*p=front;front=front->link;delete p;return*this;}template<class T>bool LinkedQueue<T>::IsFull()const{Node<T>*p;try{p=new Node<T>;delete p;return false;}catch (NoMem) {return true;}}template <class T>T LinkedQueue<T>::First()const{if(IsEmpty()) throw OutOfBounds;return front->data;}template<class T>T LinkedQueue<T>::Last()const{if(IsEmpty()) throw OutOfBounds;return rear->data;}BinaryTree<int> a,x,y,z;void main(){cout<<"输入二叉树:"<<endl;BinaryTree<char> Tree;Tree.Creat();cout<<"前序遍历："<<" ";Tree.PreOutput();cout<<"后序遍历："<<" ";Tree.Postput();cout<<"中序遍历："<<endl;Tree.InOutput();cout<<"层序遍历："<<" ";Tree.LevelOutPut();。