ep7_11.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:4k
- /*7.11 为二叉树类编写一个拷贝构造函数(采用前序遍历)和拷贝赋值运算符(=)。。*/
- #include<iostream>
- #include<cstdlib>
- using namespace std;
- template<typename T>class BinaryTree;
- template<typename T>class Node{
- Node<T> *lchild,*rchild;
- T info;
- public:
- Node(){lchild=NULL;rchild=NULL;}
- Node(T data,Node<T> *left=NULL,Node<T> *right=NULL){
- info=data;
- lchild=left;
- rchild=right;
- }
- friend class BinaryTree<T>;
- };
- template<typename T>class BinaryTree{
- Node<T> *root; //二叉树的根指针
- void InOrder(Node<T> *Current); //中序遍历
- void PreOrder(Node<T> *Current); //前序遍历
- void PostOrder(Node<T> *Current); //后序遍历
- void Insert(const T &data,Node<T> * &b); //插入结点,参数为引用!
- void Destory(Node<T> * Current); //删除树
- Node<T>* Copy(Node<T> * snode);
- public:
- BinaryTree(){root=NULL;} //空树构造函数
- BinaryTree(BinaryTree<T> &); //拷贝构造函数
- ~BinaryTree(){Destory(root);} //析构函数
- BinaryTree<T>& operator=(BinaryTree<T> &);
- void Destory(){Destory(root);root=NULL;} //删除树后root悬挂,必须赋空
- void Creat(T* data,int n); //建立(排序)二叉树
- void InOrder(){InOrder(root);} //中序遍历,共有函数为接口
- void PreOrder(){PreOrder(root);} //前序遍历,共有函数为接口
- void PostOrder(){PostOrder(root);} //后序遍历,共有函数为接口
- };
- template<typename T> BinaryTree<T>::BinaryTree(BinaryTree<T> & sb){//拷贝构造函数
- root=Copy(sb.root);
- }
- template<typename T> Node<T>* BinaryTree<T>::Copy(Node<T> * snode){
- if(snode==NULL) return NULL;
- Node<T>* p=new Node<T>;
- p->info=snode->info;
- p->lchild=Copy(snode->lchild);
- p->rchild=Copy(snode->rchild);
- return p;
- }
- template<typename T>BinaryTree<T>& BinaryTree<T>::operator=(BinaryTree<T> & sb){
- root=Copy(sb.root);
- return *this;
- }
- template<typename T> void BinaryTree<T>::Destory(Node<T> *Current){
- if(Current!=NULL){
- Destory(Current->lchild);
- Destory(Current->rchild);
- delete Current; //后序释放根结点
- }
- }
- template<typename T>void BinaryTree<T>::Insert(const T &data,Node<T> * &b){
- if(b==NULL){ //已到空树,插入
- b=new Node<T>(data);
- if(b==NULL){
- cout<<"空间不足"<<endl;
- exit(1);
- }
- }
- else if(data<b->info) Insert(data,b->lchild); //小于,向左子树去查
- else Insert(data,b->rchild); //大于等于,向右子树去查
- }
- template<typename T>void BinaryTree<T>::Creat(T* data,int n){ //建立一棵二叉排序树
- for(int i=0;i<n;i++) Insert(data[i],root);
- }
- template<typename T>void BinaryTree<T>::InOrder(Node<T> *Current){
- if(Current!=NULL){ //递归终止条件
- InOrder(Current->lchild); //中序遍历左子树
- cout<<Current->info<<'t'; //访问根结点,注意所放位置
- InOrder(Current->rchild); //中序遍历右子树
- }
- }
- template<typename T>void BinaryTree<T>::PreOrder(Node<T> *Current){
- if(Current!=NULL){
- cout<<Current->info<<'t'; //注意前序访问语句所放位置
- PreOrder(Current->lchild);
- PreOrder(Current->rchild);
- }
- }
- template<typename T>void BinaryTree<T>::PostOrder(Node<T> *Current){
- if(Current!=NULL){
- PostOrder(Current->lchild);
- PostOrder(Current->rchild);
- cout<<Current->info<<'t'; //后序访问根结点
- }
- }
- int main(){
- const int n=15;
- int i,a[n]={10,5,15,8,3,18,13,12,14,16,20,1,4,6,9};
- BinaryTree<int> btree;
- btree.Creat(a,n);
- cout<<"输入数据:"<<endl;
- for(i=0;i<n;i++) cout<<a[i]<<'t';
- cout<<endl<<"中序:"<<endl;
- btree.InOrder(); //中序遍历输出升序
- cout<<endl<<"前序:"<<endl;
- btree.PreOrder();
- BinaryTree<int> btree1(btree),btree2;
- btree2=btree;
- btree.Destory();//删去原树,看是否深拷贝
- cout<<endl<<"拷贝二叉树btree1,中序:"<<endl;//中序和前序决定唯一的树
- btree1.InOrder(); //中序遍历输出升序
- cout<<endl<<"拷贝二叉树btree1,前序:"<<endl;
- btree1.PreOrder();
- cout<<endl<<"拷贝二叉树btree2,中序:"<<endl;//中序和前序决定唯一的树
- btree2.InOrder(); //中序遍历输出升序
- cout<<endl<<"拷贝二叉树btree2,前序:"<<endl;
- btree2.PreOrder();
- cout<<endl;
- return 0;
- }