转载

二叉查找树 C++实现（含完整代码）

一般二叉树的查找是通过遍历整棵二叉树实现，效率较低。二叉查找树是一种特殊的二叉树，可以提高查找的效率。二叉查找树又称为二叉排序树或二叉搜索树。

二叉查找树的定义

二叉排序树（Binary Search Tree）又称二叉排序树（Binary Sort Tree）,或者是一颗空二叉树，或者是具有一下特性的二叉树：

  1. 若它的左子树不为空，则左子树上的所有结点的值均小于根节点的值。
  2. 若它的右子树不为空，则右子树上的所有结点的值均小于根节点的值。
  3.       它的左右子树又分别是二叉排序树。

由定义可知，二叉查找树中结点的值不允许重复。图a是一棵二叉查找树。当加入结点90后如图b，图b的二叉树不是二叉查找树，因其不满足二叉排序树的特性1.

二叉查找树 C++实现（含完整代码） 二叉查找树 C++实现（含完整代码）

图a                                                               图b

   二叉树的C++实现

  1. 二叉查找树的结点结构 
template<typename T> //树结点结构 class BSTNode{ public:  T _key; //关键在字（键值）  BSTNode *_lchild; //左孩  BSTNode *_rchild; //右孩  BSTNode *_parent; // 双亲  //构造函数  BSTNode(T key ,BSTNode *lchild,BSTNode *rchild,BSTNode *parent):  _key(key),_lchild(lchild),_rchild(rchild),_parent(parent){}; };

结点结构BSTNode中含有三个指针域，分别是：

  1. _lchild，指向结点的左孩子。
  2. _rchild，指向结点的右孩子。
  3. _parent，指向结点的双亲。

包含一个数据域 _key，为结点的关键字值。

使用构造函数初始化表列对以上四个数据进行初始化。

2.二叉查找树的操作 

template<typename T> class BSTree{ private:  BSTNode<T> *_Root ;  //根结点 public:  BSTree():_Root(NULL){};  ~BSTree(){};  void insert (T key);//二叉树的插入   BSTNode<T>* search (T key)  ;//二叉树的查找  void preOrder()  ;  //先序输出  void inOrder() ;   //中序输出  void postOrder() ; //后序输出   BSTNode<T>* minimumNode();//查找最小的节点  BSTNode<T>* maximumNode ();//查找最大的节点    T minimumKey();//查找最小的键值  T maximumKey();//查找最小的键值  void print();//打印二叉树  void remove(T key);  BSTNode<T>* predecessor(BSTNode<T>* x);//查找某个结点的前驱  BSTNode<T>* sucessor(BSTNode<T>* x); //查找某个结点的后继  void destory ();  //内部使用函数，供外部接口调用 private:  void insert(BSTNode<T>* &tree,BSTNode<T>* z);  BSTNode<T>* search(BSTNode<T>* &tree,T key) const;  void preOrder(BSTNode<T>*&tree) const;  void inOrder(BSTNode<T>*&tree) const;  void postOrder(BSTNode<T>*&tree) const;  BSTNode<T>* minimumNode(BSTNode<T> *&tree);  BSTNode<T>* maximumNode (BSTNode<T> *&tree);  void print(BSTNode<T>*& tree);  BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);  void destory(BSTNode<T>*& tree); };

BSTree类包含了一个BSTNode指针数据成员，代表二叉查找树的根结点。类种封装了二叉查找树常用的操作接口，包括：

  1. 插入操作：也是建立二叉查找树的方法。
  2. 遍历算法：包括前序、中序、后序（递归实现）。
  3. 查找操作：包括查找某个结点、查找最小结点、查找最大结点、查找最小值、查找最大值。
  4. 删除操作。
  5. 销毁操作。
  6. 打印操作：打印说明二叉树的结构。

BSTree类大部分的函数都有两个重载版本，一个仅供类内部使用（privata声明），另一个则为类用户使用的公用接口（public声明）。

2.1二叉查找树的遍历

2.1.1遍历二叉树

  遍历二叉树 是指从根结点出发，按照某种次序访问二叉树所有结点，使得每个结点被且仅被访问一次，这里的访问可以是输出、比较、更新、查看结点信息等各种操作。遍历是二叉树的一类重要操作，也是二叉树的其他一些操作和各种应用算法的基本框架。用V表示根节点，用L表示左孩子，用R表示右孩子，且规定先L后R的访问顺序，则有VLR（前序）、LVR（中序）、LRV（后续）三种遍历算法。对于图a中的二叉树，其遍历结果为：

二叉查找树 C++实现（含完整代码）

前序遍历：88 47 19 55 50 98

中序遍历：19 47 50 55 88 98 

后序遍历：19 50 55 47 98 88

下面来看BSTtree提供的三种遍历接口：

前序遍历：

        1. 访问根节点。
        2. 遍历访问左子树。
        3. 遍历访问右子树。 
/* * *前序遍历算法 *BSTree类内部调用函数 * */ template<typename T> void BSTree<T>::preOrder(BSTNode<T>*&tree) const {  if(tree)  {   cout<<tree->_key<<" ";   preOrder(tree->_lchild);   preOrder(tree->_rchild);  } } /* *接口 * */template<typename T> void BSTree<T>::postOrder() {  postOrder(_Root); }

中序遍历：

      1. 遍历访问左子树
      2. 访问根节点。
      3. 遍历访问右子树。 
/* * *中序遍历算法 *类内部调用函数 * */ template <typename T> void BSTree<T>::inOrder(BSTNode<T>*&tree) const {  if(tree)  {   inOrder(tree->_lchild);   cout<<tree->_key<<" ";   inOrder(tree->_rchild);  } } /* * *接口 * */ template<typename T> void BSTree<T>::inOrder() {  inOrder(_Root); }

后序遍历：

      1. 遍历访问左子树。
      2. 遍历访问右子树。
      3. 访问根节点。 
/* * *后序遍历算法 *类内部调用函数 * */ template <typename T> void BSTree<T>::postOrder(BSTNode<T>*&tree) const {  if(tree)  {   postOrder(tree->_lchild);   postOrder(tree->_rchild);   cout<<tree->_key<<" ";  } } /* * *接口 * */ template<typename T> void BSTree<T>::postOrder() {  postOrder(_Root); }

2.2二叉查找树的插入

构建查找二叉树通过二叉查找树的插入操作来进行。插入时严格按照查找二叉树的定义来进行，其插入算法的基本过程可以分解为：

    1. 根结点为空则进行插入。
    2. 值比根结点小，在根结点的左子树进行插入。
    3. 值比根结点大，在根节点的右子树进行插入。

本文采用非递归算法实现插入操作。

/* *插入操作 *非递归实现 *内部使用函数 */ template<typename T> void BSTree<T> ::insert(BSTNode<T>* &tree,BSTNode<T>* z) {  BSTNode<T>* parent = NULL;  BSTNode<T>* temp = tree;  //寻找插入点  while(temp!=NULL)  {   parent= temp;   if(z->_key>temp->_key)    temp= temp->_rchild;   else     temp=temp->_lchild;  }  z->_parent = parent;  if(parent==NULL) //如果树本来就是空树，则直接把z节点插入根节点   tree = z;  else if(z->_key>parent->_key) //如果z的值大于其双亲，则z为其双亲的右孩   parent->_rchild = z;  else           parent->_lchild = z; } /* * *接口 */ template <typename T> void BSTree<T>::insert(T key) {  //创建一个新的节点，使用构造函数初始化  BSTNode<T>* z= new BSTNode<T>(key,NULL,NULL,NULL);  if(!z) //如果创建失败则返回   return ;  //调用内部函数进行插入  insert(_Root,z); }

2.3 二叉查找树的查找

2.3.1 查找某个值的结点

这里提供递归与非递归算法实现查找操作。

/* *查找操作 *非递归实现 *内部使用函数 */ template <typename T> BSTNode<T>*  BSTree<T>::search(BSTNode<T>* &tree,T key) const {  BSTNode<T>* temp = tree;  while(temp != NULL)  {   if(temp->_key == key)    return temp;   else if(temp->_key>key)    temp = temp->_lchild;   else    temp = temp->_rchild;  }  return NULL; } ////查找算法的递归实现 //template<typename T> //BSTNode<T>* BSTree<T>::search( BSTNode<T>* &tree,T key) const //{ // if(!tree) // { //  if(tree->_key==key) //   return tree; //  if(tree->_key>key) //   return search(tree->_lchild,key); //  if(tree->_key<z->_key) //   return search(tree->_rchild,key); // } // return NULL; //} /* *接口 */ template <typename T> BSTNode<T> * BSTree<T>::search(T key)  {  return search(_Root,key); }

2.3.2查找二叉查找树值最小的结点

/* * *查找最小的结点 *内部调用函数 * */ template <typename T> BSTNode<T>* BSTree<T>::minimumNode(BSTNode<T>*&tree) {  BSTNode<T>* temp = tree;  while(temp->_lchild)  {   temp= temp->_lchild;  }  return temp; } /* *接口 */ template<typename T> BSTNode<T>* BSTree<T>::minimumNode() {  return minimumNode(_Root); }

2.3.3查找二叉查找树中值最大的结点

/* * *查找键值最大的节点 *内部调用函数 *非递归实现 */ template<typename T> BSTNode<T>* BSTree<T>::maximumNode(BSTNode<T>* &tree) {  BSTNode<T>* temp=tree;  while(temp->_rchild)  {   temp= temp->_rchild;  }  return temp; } /* *接口 */ template<typename T> BSTNode<T>* BSTree<T>::maximumNode() {  return maximumNode(_Root); }

2.3.4查找二叉查找树中最小的值

/* * *查找最小的键值 *外部接口函数 *调用内部函数minimumNode实现 */ template<typename T> T BSTree<T>::minimumKey() {     BSTNode<T> *temp = minimumNode(_Root);     return temp->_key; }

2.4.5查找二叉查找树中最大的值

/* * *查找最大的键值 *外部接口函数 *调用内部函数maximumKey */ template<typename T> T BSTree<T>::maximumKey() {     BSTNode<T> *temp = maximumNode(_Root);     return temp->_key; }

2.3打印查找二叉树

该操作把二叉树中每个结点的父结点、左右孩子结点的信息描述出来。

/* * *打印函数 *打印出平衡二叉树 *BStree内部函数 */ template<typename T> void BSTree<T>::print(BSTNode<T>*& tree) {  if(tree) //如果tree不为空  {   if(tree->_lchild) //结点有左孩子   {    cout<<"节点"<<tree->_key<<"有左孩子为"<<tree->_lchild->_key<<endl;   }   else     cout<<"节点"<<tree->_key<<"无左孩子"<<endl;   if(tree->_rchild)   {    cout<<"节点"<<tree->_key<<"有右孩子为"<<tree->_rchild->_key<<endl;   }   else     cout<<"节点"<<tree->_key<<"无右孩子"<<endl;   print(tree->_lchild);   print(tree->_rchild);  } } /* *接口 */ template<typename T> void BSTree<T>::print() {  print(_Root); }

2.4查找给定结点的前驱结点

/* *查找某个节点x的前驱 * *接口 * */ template <typename T> BSTNode<T>* BSTree<T>::predecessor(BSTNode<T>* x) {  //如果x是最小的结点，则它没有前驱  if(x->_key == minimumNode(_Root)->_key)   return NULL;  //否则  //先获取二叉树中键值与x的键值相同的结点y  BSTNode <T> * y = NULL;  y = search(_Root,x->_key);  if(y==NULL) return NULL;  //如果y有左孩子，则x的前驱为“以x的左孩为根的子树的最大结点”  if(y->_lchild!=NULL)   return maximumNode(y->_lchild);  //如果y没有左孩子，则x有两种可能：  //1.y是一个右孩子，此时x的前驱为其双亲节点  BSTNode<T>* parent = y->_parent;  if(parent->_rchild == y)   return parent;  //2.y是一个左孩子，则其前驱为其双亲结点中“第一个拥有右孩子结点”的结点  while(parent!=NULL&&parent->_rchild==NULL)  {   parent=parent->_parent;  }  return parent; }

2.5查找给定结点的后继结点

/* *查找某个节点x的后继 * *外部调用接口 * */ template <typename T> BSTNode<T>* BSTree<T>::sucessor(BSTNode<T>* x) {  //如果x是键值最大的，则x没有后继结点  if(x->_key==maximumNode(_Root)->_key)   return NULL;  //获取x在二叉树中的结点y  BSTNode<T>* y  = NULL;  y = search(_Root,x->_key);  if(!y)     //若二叉树没有此结点   return NULL;  //如果y有右孩子，则y的后继为其右孩子的最小结点  if(y->_rchild!=NULL)   return minimumNode(y->_rchild);  //如果y没有右孩子，则可分为两种情况：  //1.y 是左孩子。此时y的后继为y的父结点  BSTNode <T>* parent = y->_parent;  if(y->_parent->_lchild == y)   return parent;  //2.y是右孩子。此时y的后继结点为“第一个拥有左孩且不是y的直接双亲”的结点  while(parent!=NULL)  {   if(parent->_lchild!=NULL&&parent!=y->_parent)    return parent;   parent=parent->_parent;  }  return NULL; }

2.6 删除结点

/* * *删除结点 *BSTree类内部调用函数 * */ template <class T> BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z) {  BSTNode<T> *x=NULL;  BSTNode<T> *y=NULL;  if ((z->_lchild == NULL) || (z->_rchild == NULL) )   y = z;  else   y = sucessor(z);  if (y->_lchild != NULL)   x = y->_lchild;  else   x = y->_rchild;  if (x != NULL)   x->_parent = y->_parent;  if (y->_parent == NULL)   tree = x;  else if (y == y->_parent->_lchild)   y->_parent->_lchild = x;  else   y->_parent->_rchild= x;  if (y != z)    z->_key = y->_key;  return y; } /* * 接口 */ template<typename T> void BSTree<T>::remove(T key) {  BSTNode<T> *z, *node;   if ((z = search(_Root, key)) != NULL)   if ( (node = remove(_Root, z)) != NULL)    delete node; }

2.7销毁二叉查找树

/* * *销毁查找二叉树 *内部调用函数 * */ template<typename T> void BSTree<T>::destory(BSTNode<T>*& tree) {  if(tree->_lchild!=NULL)   destory(tree->_lchild);  if(tree->_rchild!=NULL)   destory(tree->_rchild);  if(tree->_lchild==NULL&&tree->_rchild==NULL)  {   delete(tree);   tree = NULL;  } } /* *接口 */ template<typename T> void BSTree<T>::destory() {  destory(_Root); }
二叉查找树的C++实现（完整源码）
二叉查找树 C++实现（含完整代码） 
#ifndef _BINARY_SEARCH_TREE_ #define _BINARY_SEARCH_TREE_ #include <iostream> using namespace std; template<typename T> //树结点结构 class BSTNode{ public:  T _key; //关键在字（键值）  BSTNode *_lchild; //左孩  BSTNode *_rchild; //右孩  BSTNode *_parent; // 双亲  //构造函数  BSTNode(T key ,BSTNode *lchild,BSTNode *rchild,BSTNode *parent):  _key(key),_lchild(lchild),_rchild(rchild),_parent(parent){}; }; template<typename T> class BSTree{ private:  BSTNode<T> *_Root ;  //根结点 public:  BSTree():_Root(NULL){};  ~BSTree(){};  void insert (T key);//二叉树的插入   BSTNode<T>* search (T key)  ;//二叉树的查找  void preOrder()  ;  //先序输出  void inOrder() ;   //中序输出  void postOrder() ; //后序输出   BSTNode<T>* minimumNode();//查找最小的节点  BSTNode<T>* maximumNode ();//查找最大的节点    T minimumKey();//查找最小的键值  T maximumKey();//查找最小的键值  void print();//打印二叉树  void remove(T key);  BSTNode<T>* predecessor(BSTNode<T>* x);//查找某个结点的前驱  BSTNode<T>* sucessor(BSTNode<T>* x); //查找某个结点的后继  void destory ();  //内部使用函数，供外部接口调用 private:  void insert(BSTNode<T>* &tree,BSTNode<T>* z);  BSTNode<T>* search(BSTNode<T>* &tree,T key) const;  void preOrder(BSTNode<T>*&tree) const;  void inOrder(BSTNode<T>*&tree) const;  void postOrder(BSTNode<T>*&tree) const;  BSTNode<T>* minimumNode(BSTNode<T> *&tree);  BSTNode<T>* maximumNode (BSTNode<T> *&tree);  void print(BSTNode<T>*& tree);  BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);  void destory(BSTNode<T>*& tree); }; /* *插入操作 *非递归实现 *内部使用函数 */ template<typename T> void BSTree<T> ::insert(BSTNode<T>* &tree,BSTNode<T>* z) {  BSTNode<T>* parent = NULL;  BSTNode<T>* temp = tree;  //寻找插入点  while(temp!=NULL)  {   parent= temp;   if(z->_key>temp->_key)    temp= temp->_rchild;   else     temp=temp->_lchild;  }  z->_parent = parent;  if(parent==NULL) //如果树本来就是空树，则直接把z节点插入根节点   tree = z;  else if(z->_key>parent->_key) //如果z的值大于其双亲，则z为其双亲的右孩   parent->_rchild = z;  else           parent->_lchild = z; } /* * *接口 */ template <typename T> void BSTree<T>::insert(T key) {  //创建一个新的节点，使用构造函数初始化  BSTNode<T>* z= new BSTNode<T>(key,NULL,NULL,NULL);  if(!z) //如果创建失败则返回   return ;  //调用内部函数进行插入  insert(_Root,z); } /* *查找操作 *非递归实现 *内部使用函数 */ template <typename T> BSTNode<T>*  BSTree<T>::search(BSTNode<T>* &tree,T key) const {  BSTNode<T>* temp = tree;  while(temp != NULL)  {   if(temp->_key == key)    return temp;   else if(temp->_key>key)d    temp = temp->_lchild;   else    temp = temp->_rchild;  }  return NULL; } ////查找算法的递归实现 //template<typename T> //BSTNode<T>* BSTree<T>::search( BSTNode<T>* &tree,T key) const //{ // if(!tree) // { //  if(tree->_key==key) //   return tree; //  if(tree->_key>key) //   return search(tree->_lchild,key); //  if(tree->_key<z->_key) //   return search(tree->_rchild,key); // } // return NULL; //} /* *接口 */ template <typename T> BSTNode<T> * BSTree<T>::search(T key)  {  return search(_Root,key); } /* * *前序遍历算法 *外部使用接口 * */ template<typename T> void BSTree<T>::preOrder(BSTNode<T>*&tree) const {  if(tree)  {   cout<<tree->_key<<" ";   preOrder(tree->_lchild);   preOrder(tree->_rchild);  } } template <typename T> void BSTree<T>::inOrder(BSTNode<T>*&tree) const {  if(tree)  {   inOrder(tree->_lchild);   cout<<tree->_key<<" ";   inOrder(tree->_rchild);  } } template <typename T> void BSTree<T>::postOrder(BSTNode<T>*&tree) const {  if(tree)  {   postOrder(tree->_lchild);   postOrder(tree->_rchild);   cout<<tree->_key<<" ";  } } /* *遍历算法 *分别为前序、中序、后序 *BSTree 类外部接口函数 * */ template<typename T> void BSTree<T>::preOrder() {  preOrder(_Root); } template<typename T> void BSTree<T>::inOrder() {  inOrder(_Root); } template<typename T> void BSTree<T>::postOrder() {  postOrder(_Root); } /* * *查找最小的结点 *内部调用函数 * */ template <typename T> BSTNode<T>* BSTree<T>::minimumNode(BSTNode<T>*&tree) {  BSTNode<T>* temp = tree;  while(temp->_lchild)  {   temp= temp->_lchild;  }  return temp; } /* *接口 */ template<typename T> BSTNode<T>* BSTree<T>::minimumNode() {  return minimumNode(_Root); } /* * *查找键值最大的节点 *内部调用函数 *非递归实现 */ template<typename T> BSTNode<T>* BSTree<T>::maximumNode(BSTNode<T>* &tree) {  BSTNode<T>* temp=tree;  while(temp->_rchild)  {er   temp= temp->_rchild;  }  return temp; } /* *接口 */ template<typename T> BSTNode<T>* BSTree<T>::maximumNode() {  return maximumNode(_Root); } /* * *查找最小的键值 *外部接口函数 *调用内部函数minimumNode实现 */ template<typename T> T BSTree<T>::minimumKey() {  BSTNode<T> *temp = minimumNode(_Root);  return temp->_key; } /* *  *查找最大的键值 *外部接口函数 *调用内部函数maximumKey */ template<typename T> T BSTree<T>::maximumKey() {  BSTNode<T> *temp = maximumNode(_Root);  return temp->_key; } /* * *打印函数 *打印出平衡二叉树 *BStree内部函数 */ template<typename T> void BSTree<T>::print(BSTNode<T>*& tree) {  if(tree) //如果tree不为空  {   if(tree->_lchild) //结点有左孩子   {    cout<<"节点"<<tree->_key<<"有左孩子为"<<tree->_lchild->_key<<endl;   }   else     cout<<"节点"<<tree->_key<<"无左孩子"<<endl;   if(tree->_rchild)   {    cout<<"节点"<<tree->_key<<"有右孩子为"<<tree->_rchild->_key<<endl;   }   else     cout<<"节点"<<tree->_key<<"无右孩子"<<endl;   print(tree->_lchild);   print(tree->_rchild);  } } /* *接口 */ template<typename T> void BSTree<T>::print() {  print(_Root); } /* *查找某个节点x的前驱 * *外部函数调用 * */ template <typename T> BSTNode<T>* BSTree<T>::predecessor(BSTNode<T>* x) {  //如果x是最小的结点，则它没有前驱  if(x->_key == minimumNode(_Root)->_key)   return NULL;  //否则  //先获取二叉树中键值与x的键值相同的结点y  BSTNode <T> * y = NULL;  y = search(_Root,x->_key);  if(y==NULL) return NULL;  //如果y有左孩子，则x的前驱为“以x的左孩为根的子树的最大结点”  if(y->_lchild!=NULL)   return maximumNode(y->_lchild);  //如果y没有左孩子，则x有两种可能：  //1.y是一个右孩子，此时x的前驱为其双亲节点  BSTNode<T>* parent = y->_parent;  if(parent->_rchild == y)   return parent;  //2.y是一个左孩子，则其前驱为其双亲结点中“第一个拥有右孩子结点”的结点  while(parent!=NULL&&parent->_rchild==NULL)  {   parent=parent->_parent;  }  return parent; } /* *查找某个节点x的后继 * *外部调用接口 * */ template <typename T> BSTNode<T>* BSTree<T>::sucessor(BSTNode<T>* x) {  //如果x是键值最大的，则x没有后继结点  if(x->_key==maximumNode(_Root)->_key)   return NULL;  //获取x在二叉树中的结点y  BSTNode<T>* y  = NULL;  y = search(_Root,x->_key);  if(!y)     //若二叉树没有此结点   return NULL;  //如果y有右孩子，则y的后继为其右孩子的最小结点  if(y->_rchild!=NULL)   return minimumNode(y->_rchild);  //如果y没有右孩子，则可分为两种情况：  //1.y 是左孩子。此时y的后继为y的父结点  BSTNode <T>* parent = y->_parent;  if(y->_parent->_lchild == y)   return parent;  //2.y是右孩子。此时y的后继结点为“第一个拥有左孩且不是y的直接双亲”的结点  while(parent!=NULL)  {   if(parent->_lchild!=NULL&&parent!=y->_parent)    return parent;   parent=parent->_parent;  }  return NULL; } /* * *删除结点 *BSTree类内部调用函数 * */ template <class T> BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z) {  BSTNode<T> *x=NULL;  BSTNode<T> *y=NULL;  if ((z->_lchild == NULL) || (z->_rchild == NULL) )   y = z;  else   y = sucessor(z);  if (y->_lchild != NULL)   x = y->_lchild;  else   x = y->_rchild;  if (x != NULL)   x->_parent = y->_parent;  if (y->_parent == NULL)   tree = x;  else if (y == y->_parent->_lchild)   y->_parent->_lchild = x;  else   y->_parent->_rchild= x;  if (y != z)    z->_key = y->_key;  return y; } /* * 接口 */ template<typename T> void BSTree<T>::remove(T key) {  BSTNode<T> *z, *node;   if ((z = search(_Root, key)) != NULL)   if ( (node = remove(_Root, z)) != NULL)    delete node; } /* * *销毁查找二叉树 *内部调用函数 * */ template<typename T> void BSTree<T>::destory(BSTNode<T>*& tree) {  if(tree->_lchild!=NULL)   destory(tree->_lchild);  if(tree->_rchild!=NULL)   destory(tree->_rchild);  if(tree->_lchild==NULL&&tree->_rchild==NULL)  {   delete(tree);   tree = NULL;  } } /* *接口 */ template<typename T> void BSTree<T>::destory() {  destory(_Root); } #endif
BSTree.h
主函数 测试数据
二叉查找树 C++实现（含完整代码） 
// BSTree.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include <iostream> #include "BSTree.h" using namespace std; int main() {  BSTree<int> s ;  int a ;  cout<<"请输入二叉树结点以构造二叉查找树："<<endl;  while(cin>>a )   s.insert(a);  cin.clear();  cout<<"前序遍历二叉查找树:"<<endl;  s.postOrder();  cout<<endl;  cout<<"中序遍历二叉查找树:"<<endl;  s.inOrder();  cout<<endl;  cout<<"后序遍历二叉查找树:"<<endl;  s.postOrder();  cout<<endl;  cout<<"打印二叉查找树"<<endl;  s.print();  cout<<"请输入要查找的数："<<endl;  while(cin>>a)  {   BSTNode<int>* findnode = s.search(a);   if(!findnode)   {    cout<<"查找失败"<<endl;    s.insert(a);    cout<<"已经将"<<a<<"插入二叉查找树,现在二叉查找树为："<<endl;    s.inOrder();    cout<<endl;   }   else   {    cout<<findnode->_key<<"查找成功"<<endl;   }  }  cin.clear();  cout<<"请输入结点以查找其前驱节点"<<endl;  BSTNode<int>* findPreNode= new BSTNode<int>(1,NULL,NULL,NULL);  while(cin>>findPreNode->_key)  {   BSTNode<int>* preNode ;   if((preNode= s.predecessor(findPreNode))!=NULL)   {    cout<<"其前驱结点为：";    cout<<preNode->_key<<endl;   }   else     cout<<"没有前驱结点"<<endl;   if((preNode= s.sucessor(findPreNode))!=NULL)   {    cout<<"其后继结点为：";    cout<<preNode->_key<<endl;   }   else     cout<<"没有后继结点"<<endl;  }  cin.clear();  cout<<"请输入要删除的结点："<<endl;  while(cin >>a)  {   s.remove(a);   cout<<"删除后的二叉排序树："<<endl;   s.inOrder();  }  BSTNode<int>* maxNode =  s.minimumNode();  if(!maxNode)   cout<<"最小的节点为："<<maxNode->_key<<endl;  BSTNode<int>* minNode = s.maximumNode();  if(!minNode)   cout<<"最大的节点为："<<minNode->_key<<endl;  cout<<"销毁二叉树"<<endl;  s.destory();  s.inOrder();  system("pause");  return 0; }
View Code

运行结果：

二叉查找树 C++实现（含完整代码）

=========================================================================================================================================完。

正文到此结束
所属分类： 编程技术

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 java-demo Maven教程 springcloud-demo hibernate教程 Docker 教程 memcached教程 Quartz指南 Hive教程 ANTLR教程 SpringCloud Ant教程 java实例教程 Hazelcast教程 XStream教程 Elastic-Job-Lite 深入浅出MyBatis ibaties教程 SVN教程 rabittmq教程 Hadoop教程 solr教程 WebService CXF学习 JPA教程 ActiveMQ中文指南 Java内存模型 dubbo教程 python3-demo Linux入门视频教程
近期评论
  1. 1 使用 Docker 打包和运行 Vue 应用
  2. 2 Dependency Check命令行方式扫描jar包的安全漏洞
  3. 3 maven使用Dependency-Check来扫描安全漏洞
  4. 4 使用sonarqube分析代码质量
  5. 5 使用screw来对比数据库表和字段差异
  6. 6 Spring Boot 实现防盗链功能
  7. 7 在Spring Boot中的实现国际化（i18n）
  8. 8 一个用于 SMB/CIFS 网络的 Java 库-JCIFS
  9. 9 Spring Boot 3.x嵌入MongoDB 进行测试
  10. 10 java如何解析和生成yaml文件？
网站信息
  • 文章总数：82,737 篇
  • 文件总数：284,312 个
  • 标签总数：2,416 个
  • 分类总数：85 个
  • 留言数量：2,559 条
  • 在线人数：623 人
  • 运行天数：4,439天
  • 最后更新：2024年12月22日15点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG