一般二叉树的查找是通过遍历整棵二叉树实现,效率较低。二叉查找树是一种特殊的二叉树,可以提高查找的效率。二叉查找树又称为二叉排序树或二叉搜索树。
二叉排序树(Binary Search Tree)又称二叉排序树(Binary Sort Tree),或者是一颗空二叉树,或者是具有一下特性的二叉树:
由定义可知,二叉查找树中结点的值不允许重复。图a是一棵二叉查找树。当加入结点90后如图b,图b的二叉树不是二叉查找树,因其不满足二叉排序树的特性1.
图a 图b
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中含有三个指针域,分别是:
包含一个数据域 _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指针数据成员,代表二叉查找树的根结点。类种封装了二叉查找树常用的操作接口,包括:
BSTree类大部分的函数都有两个重载版本,一个仅供类内部使用(privata声明),另一个则为类用户使用的公用接口(public声明)。
2.1二叉查找树的遍历
2.1.1遍历二叉树
遍历二叉树 是指从根结点出发,按照某种次序访问二叉树所有结点,使得每个结点被且仅被访问一次,这里的访问可以是输出、比较、更新、查看结点信息等各种操作。遍历是二叉树的一类重要操作,也是二叉树的其他一些操作和各种应用算法的基本框架。用V表示根节点,用L表示左孩子,用R表示右孩子,且规定先L后R的访问顺序,则有VLR(前序)、LVR(中序)、LRV(后续)三种遍历算法。对于图a中的二叉树,其遍历结果为:
前序遍历:88 47 19 55 50 98
中序遍历:19 47 50 55 88 98
后序遍历:19 50 55 47 98 88
下面来看BSTtree提供的三种遍历接口:
前序遍历:
/* * *前序遍历算法 *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); }
中序遍历:
/* * *中序遍历算法 *类内部调用函数 * */ 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); }
后序遍历:
/* * *后序遍历算法 *类内部调用函数 * */ 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二叉查找树的插入
构建查找二叉树通过二叉查找树的插入操作来进行。插入时严格按照查找二叉树的定义来进行,其插入算法的基本过程可以分解为:
本文采用非递归算法实现插入操作。
/* *插入操作 *非递归实现 *内部使用函数 */ 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); }
#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); } #endifBSTree.h
// 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
运行结果:
=========================================================================================================================================完。