二叉查找树

2280阅读　0评论2014-04-28　qinchaowhut
分类：C/C++


  1. #ifndef __BINARYSEARCHTREE_H__
  2. #define __BINARYSEARCHTREE_H__

  4. //template<typename int>
  5. class BinarySearchTree
  6. {
  7.     private:
  8.         struct BinaryNode
  9.         {
  10.             int element;
  11.             BinaryNode *left;
  12.             BinaryNode *right;
  13.             BinaryNode(const int &theElement,BinaryNode *lt,BinaryNode *rt):element(theElement),left(lt),right(rt)
  14.             {
  15.             }
  16.         };
  17.         BinaryNode *root;

  19.         void insert(const int &x,BinaryNode * &t)const;
  20.         void remove(const int& x,BinaryNode *&t)const;
  21.         BinaryNode *findMin(BinaryNode *t)const;
  22.         BinaryNode *findMax(BinaryNode *t)const;
  23.         bool contains(const int &x,BinaryNode *t)const;
  24.         void makeEmpty(BinaryNode* & t);
  25.         void printTree(BinaryNode *t)const;
  26.     //    BinaryNode *clone(BinaryNode *t)const;
  27.         int deep(BinaryNode *t);
  28.     
  29.     
  30.     public:
  31.         BinarySearchTree();
  32.         BinarySearchTree(const BinarySearchTree &rhs);
  33.         ~BinarySearchTree();

  35.         const int &findMin()const;
  36.         const int &findMax()const;
  37.         bool contains(const int &x)const;
  38.         bool isEmpty()const;
  39.         void printTree()const;

  41.         void makeEmpty();
  42.         void insert(const int &x);
  43.         void remove(const int &x);
  44.     //    const BinarySearchTree& operator=(const BinarySearchTree& rhs);
  45.         int deep()
  46.         {
  47.             return deep(root);
  48.         }
  49. };

  51. #endif

点击(此处)折叠或打开

  1. #include"BinarySearchTree.h"
  2. #include<iostream>
  3. using std::cout;

  5. BinarySearchTree::BinarySearchTree():root(NULL)
  6. {
  7. }

  9. bool BinarySearchTree::contains(const int& x)const
  10. {
  11.     return contains(x,root);
  12. }

  14. bool BinarySearchTree::contains(const int &x,BinaryNode *t)const
  15. {
  16.     if(t==NULL)
  17.         return false;
  18.     else if(x < t->element)
  19.         return contains(x,t->left);
  20.     else if(x > t->element)
  21.         return contains(x,t->right);
  22.     else
  23.         return true;
  24. }

  26. void BinarySearchTree::insert(const int &x)
  27. {
  28.     insert(x,root);
  29. }

  31. void BinarySearchTree::insert(const int &x,BinaryNode *&t)const
  32. {
  33.     if(t==NULL)
  34.         t=new BinaryNode(x,NULL,NULL);
  35.     else if(x<t->element)
  36.         insert(x,t->left);
  37.     else if(x>t->element)
  38.         insert(x,t->right);
  39.     else
  40.         ;//Duplicate;do nothing。即如果x已经存在二叉树中，则插入操作终止。
  41. }

  43. void BinarySearchTree::remove(const int &x)
  44. {
  45.     remove(x,root);
  46. }

  48. void BinarySearchTree::remove(const int &x,BinaryNode * &t)const
  49. {
  50.     if(t==NULL)
  51.         return ;
  52.     if(x<t->element)
  53.         remove(x,t->left);
  54.     else if(x>t->element)
  55.         remove(x,t->right);
  56.     else if(t->left!=NULL && t->right!=NULL)
  57.     {
  58.         t->element=findMin(t->right)->element;
  59.         remove(t->element,t->right);
  60.     }
  61.     else
  62.     {
  63.         BinaryNode *oldNode=t;
  64.         t=(t->left!=NULL)? t->left : t->right;
  65.         delete oldNode;
  66.     }
  67. }

  69. BinarySearchTree::BinaryNode* BinarySearchTree::findMin(BinaryNode *t)const
  70. {
  71.     if(t==NULL)
  72.         return NULL;
  73.     if(t->left==NULL)
  74.         return t;
  75.     return findMin(t->left);
  76. }

  78. BinarySearchTree::BinaryNode* BinarySearchTree::findMax(BinaryNode *t)const
  79. {
  80.     if(t!=NULL)
  81.         while(t->right!=NULL)
  82.             t=t->right;
  83.     return t;
  84. }

  86. void BinarySearchTree::makeEmpty()
  87. {
  88.     makeEmpty(root);
  89. }
  90. void BinarySearchTree::makeEmpty(BinaryNode* &t)
  91. {
  92.     if(t!=NULL)
  93.     {
  94.         makeEmpty(t->left);
  95.         makeEmpty(t->right);
  96.         delete t;
  97.     }
  98.     t=NULL;
  99. }

  101. BinarySearchTree::~BinarySearchTree()
  102. {
  103.     makeEmpty();
  104. }

  106. void BinarySearchTree::printTree()const
  107. {
  108.     printTree(root);
  109. }
  110. void BinarySearchTree::printTree(BinaryNode *t)const
  111. {
  112.     if(t==NULL)
  113.         return ;
  114.     else
  115.         cout<<t->element<<',';
  116.     //    printf("%d",t->element);
  117.     printTree(t->left);
  118.     printTree(t->right);
  119. }


  122. //BinarySearchTree::operator =(const BinarySearchTree &rhs)
  123. //{

  125. //}
  126. int BinarySearchTree::deep(BinaryNode *t)//求二叉树的深度。
  127. {
  128.     int lm,rm;
  129.     if(t==NULL)
  130.         return -1;
  131.     lm=deep(t->left);
  132.     rm=deep(t->right);
  133.     return 1+(lm>rm? lm:rm);
  134. }


点击(此处)折叠或打开

  1. #include"BinarySearchTree.h"
  2. #include<iostream>
  3. using namespace std;

  5. int main()
  6. {
  7.     BinarySearchTree bt;
  8.     bt.insert(6);
  9.     bt.insert(2);
  10.     bt.insert(1);
  11.     bt.insert(4);
  12.     bt.insert(3);
  13.     bt.insert(8);

  15.     cout<<bt.deep()<<endl;
  16.     bt.printTree();
  17.     cout<<endl;
  18.     bt.remove(2);
  19.     bt.printTree();
  20.     cout<<endl;
  21.     cout<<bt.deep()<<endl;
  22.     bt.remove(1);
  23.     bt.remove(3);
  24.     cout<<bt.deep()<<endl;
  25.     return 0;
  26. }


上一篇：静态二维数组与动态二维数组的内存布局
下一篇：MFC thunk技术模拟