ep7_11.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:4k
源码类别:

书籍源码

开发平台:

Visual C++

  1. /*7.11  为二叉树类编写一个拷贝构造函数(采用前序遍历)和拷贝赋值运算符(=)。。*/
  2. #include<iostream>
  3. #include<cstdlib>
  4. using namespace std;
  5. template<typename T>class BinaryTree;
  6. template<typename T>class Node{
  7. Node<T> *lchild,*rchild;
  8. T info;
  9. public:
  10. Node(){lchild=NULL;rchild=NULL;}
  11. Node(T data,Node<T> *left=NULL,Node<T> *right=NULL){
  12. info=data;
  13. lchild=left;
  14. rchild=right;
  15. }
  16. friend class BinaryTree<T>;
  17. };
  18. template<typename T>class BinaryTree{
  19. Node<T> *root;                  //二叉树的根指针
  20. void InOrder(Node<T> *Current);                //中序遍历
  21. void PreOrder(Node<T> *Current); //前序遍历
  22. void PostOrder(Node<T> *Current); //后序遍历
  23. void Insert(const T &data,Node<T> * &b); //插入结点,参数为引用!
  24. void Destory(Node<T> * Current);        //删除树
  25. Node<T>* Copy(Node<T> * snode);
  26. public:
  27. BinaryTree(){root=NULL;} //空树构造函数
  28. BinaryTree(BinaryTree<T> &); //拷贝构造函数
  29. ~BinaryTree(){Destory(root);} //析构函数
  30. BinaryTree<T>& operator=(BinaryTree<T> &);
  31. void Destory(){Destory(root);root=NULL;}        //删除树后root悬挂,必须赋空
  32. void Creat(T* data,int n);                    //建立(排序)二叉树
  33. void InOrder(){InOrder(root);}                //中序遍历,共有函数为接口
  34. void PreOrder(){PreOrder(root);}       //前序遍历,共有函数为接口
  35. void PostOrder(){PostOrder(root);}   //后序遍历,共有函数为接口
  36. };
  37. template<typename T> BinaryTree<T>::BinaryTree(BinaryTree<T> & sb){//拷贝构造函数
  38. root=Copy(sb.root);
  39. }
  40. template<typename T> Node<T>* BinaryTree<T>::Copy(Node<T> * snode){
  41. if(snode==NULL) return NULL;
  42. Node<T>* p=new Node<T>;
  43. p->info=snode->info;
  44. p->lchild=Copy(snode->lchild);
  45. p->rchild=Copy(snode->rchild);
  46. return p;
  47. }
  48. template<typename T>BinaryTree<T>& BinaryTree<T>::operator=(BinaryTree<T> & sb){
  49. root=Copy(sb.root);
  50. return *this;
  51. }
  52. template<typename T> void BinaryTree<T>::Destory(Node<T> *Current){
  53. if(Current!=NULL){
  54. Destory(Current->lchild);
  55. Destory(Current->rchild);
  56. delete Current;   //后序释放根结点
  57. }
  58. }
  59. template<typename T>void BinaryTree<T>::Insert(const T &data,Node<T> * &b){
  60. if(b==NULL){ //已到空树,插入
  61. b=new Node<T>(data);
  62. if(b==NULL){
  63. cout<<"空间不足"<<endl;
  64. exit(1);
  65. }
  66. }
  67. else if(data<b->info) Insert(data,b->lchild); //小于,向左子树去查
  68.      else Insert(data,b->rchild); //大于等于,向右子树去查
  69. }
  70. template<typename T>void BinaryTree<T>::Creat(T* data,int n){ //建立一棵二叉排序树
  71. for(int i=0;i<n;i++) Insert(data[i],root);
  72. }
  73. template<typename T>void BinaryTree<T>::InOrder(Node<T> *Current){
  74. if(Current!=NULL){ //递归终止条件
  75. InOrder(Current->lchild); //中序遍历左子树
  76. cout<<Current->info<<'t'; //访问根结点,注意所放位置
  77. InOrder(Current->rchild); //中序遍历右子树
  78. }
  79. }
  80. template<typename T>void BinaryTree<T>::PreOrder(Node<T> *Current){
  81. if(Current!=NULL){
  82. cout<<Current->info<<'t'; //注意前序访问语句所放位置
  83. PreOrder(Current->lchild);
  84. PreOrder(Current->rchild);
  85. }
  86. }
  87. template<typename T>void BinaryTree<T>::PostOrder(Node<T> *Current){
  88. if(Current!=NULL){
  89. PostOrder(Current->lchild);
  90. PostOrder(Current->rchild);
  91. cout<<Current->info<<'t';   //后序访问根结点
  92. }
  93. }
  94. int main(){
  95. const int n=15;
  96. int i,a[n]={10,5,15,8,3,18,13,12,14,16,20,1,4,6,9};
  97. BinaryTree<int> btree;
  98. btree.Creat(a,n);
  99. cout<<"输入数据:"<<endl;
  100. for(i=0;i<n;i++) cout<<a[i]<<'t';
  101. cout<<endl<<"中序:"<<endl;
  102. btree.InOrder();    //中序遍历输出升序
  103. cout<<endl<<"前序:"<<endl;
  104. btree.PreOrder();
  105.     BinaryTree<int> btree1(btree),btree2;
  106. btree2=btree;
  107. btree.Destory();//删去原树,看是否深拷贝
  108. cout<<endl<<"拷贝二叉树btree1,中序:"<<endl;//中序和前序决定唯一的树
  109. btree1.InOrder();    //中序遍历输出升序
  110. cout<<endl<<"拷贝二叉树btree1,前序:"<<endl;
  111. btree1.PreOrder();
  112. cout<<endl<<"拷贝二叉树btree2,中序:"<<endl;//中序和前序决定唯一的树
  113. btree2.InOrder();    //中序遍历输出升序
  114. cout<<endl<<"拷贝二叉树btree2,前序:"<<endl;
  115. btree2.PreOrder();
  116. cout<<endl;
  117. return 0;
  118. }