学步园

介绍二叉查找树，又称二叉搜索树、有序二叉树、排序二叉树。它是特殊的二叉树，对于二叉树，假设x为二叉树中的任意一个结点，x结点包含关键字key，结点x的key值记为key[ x ]。如果y是x的左子树中的一个结点，则key[ y ] <= key[ x ]；如果y是x的右子树中的一个结点，则key[ y ] >= key[ x ]；那么，这棵树就是二叉查找树，如下图所示：

二叉查找树具有以下性质：

1）若任意结点的左子树非空，则左子树上所有结点的值均小于它的根节点的值2）若任意结点的右子树非空，则右子树上所有结点的值均大于它的根节点的值3）任意结点的左、右子树叶分别为二叉查找树4）没有键值相等的结点

算法实现结点和二叉查找树的定义

template<class T>class BSTNode{public: T key;// 关键字（键值） BSTNode *left;// 左孩子 BSTNode *right;// 右孩子 BSTNode *parent;// 父结点 BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r): key(value),parent(p),left(l),right(r) {} };

template<class T>class BSTree{private: BSTNode<T> *root;// 根结点 public: BSTree(){}; ~BSTree(){}; // 前序遍历 void preOrder(); // 中序遍历 void inOrder(); // 后序遍历 void postOrder(); // （递归实现）查找二叉树中键值为key的结点 BSTNode<T>* search(T key); // （非递归实现） 查找二叉树中键值为key的结点 BSTNode<T>* iterativeSearch(T key); // 查找最小结点（返回键值） T minimum(); // 查找最大结点（返回键值） T maximum(); // 找结点（x）的后继结点。即查找二叉树中键值大于该结点的最小结点 BSTNode<T>* successor(BSTNode<T> *x); // 找结点（x）的前驱结点。即查找二叉树中键值小于该结点的最大结点 BSTNode<T>* predecessor(BSTNode<T> *x); // 将键值为key的结点插入到二叉树中 void insert(T key); // 删除键值为key的结点 void remove(T key); // 销毁二叉树 void destroy(); // 打印二叉树 void print(); private: // 重载函数，提供内部接口 // 前序遍历 void preOrder(BSTNode<T> *tree) const; // 中序遍历 void inOrder(BSTNode<T> *tree) const; // 后序遍历 void postOrder(BSTNode<T> *tree) const; // （递归实现）查找二叉树中键值为key的结点 BSTNode<T>* search(BSTNode<T> *x, T key) const; // （非递归实现） 查找二叉树中键值为key的结点 BSTNode<T>* iterativeSearch(BSTNode<T> *x, T key) const; // 查找最小结点（返回键值） BSTNode<T>* minimum(BSTNode<T> *tree); // 查找最大结点（返回键值） BSTNode<T>* maximum(BSTNode<T> *tree); // 将结点z插入到二叉树tree中 void insert(BSTNode<T>* &tree, BSTNode<T> *z); // 删除二叉树中的结点z，并返回该结点 BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z); // 销毁二叉树 void destroy(BSTNode<T>* &tree); // 打印二叉树 void print(BSTNode<T>* &tree, T key, int direction);};

遍历

前序遍历

template<class T>void BSTree<T>::preOrder(BSTNode<T> *tree) const{if(tree!=NULL){ cout<<tree->key<<" "; preOrder(tree->left); preOrder(tree->right);} }

template<class T>void BSTree<T>::preOrder(){preOrder(root);}

中序遍历

template<class T>void BSTree<T>::inOrder(BSTNode<T> *tree) const{if(tree!=NULL){ inOrder(tree->left); cout<<tree->key<<" "; inOrder(tree->right);} }

template<class T>void BSTree<T>::inOrder(){inOrder(root);}

后序遍历

template<class T>void BSTree<T>::postOrder(BSTNode<T> *tree) const{if(tree!=NULL){ postOrder(tree->left); postOrder(tree->right); cout<<tree->key<<" ";} }

template<class T>void BSTree<T>::postOrder(){postOrder(root);}

查找

递归方式进行查找

template<class T>BSTNode<T>* BSTree<T>::search(BSTNode<T>* x, T key) const{if(x==NULL || x->key==key) return x;if(key<x->key) search(x->left, key);else search(x->right, key);}

template<class T>BSTNode<T>* BSTree<T>::search(T key){search(root, key);}

非递归方式进行查找

template<class T>BSTNode<T>* BSTree<T>::interativeSearch(BSTNode<T>* x, T key) const{while(x!=NULL && x->key!=key){ if(key<x->key) x = x->left; else x = x->right;}return x;}

template<class T>BSTNode<T>* BSTree<T>::interativeSearch(T key){interativeSearch(root, key);}

最大值和最小值

查找最大值

template<class T>BSTNode<T>* BSTree<T>::maximum(BSTNode<T> *tree){if(tree==NULL) return NULL;while(tree->right!=NULL) tree = tree->right;return tree;}

template<class T>T BSTree<T>::maximum(){BSTNode<T> *p = maximum(root);if(p!=NULL) return p->key;return (T)NULL;}

查找最小值

template<class T>BSTNode<T>* BSTree<T>::minimum(BSTNode<T> *tree){if(tree==NULL) return NULL;while(tree->left!=NULL) tree = tree->left;return tree;}

template<class T>T BSTree<T>::minimum(){BSTNode<T> *p = minimum(root);if(p!=NULL) return p->key;return (T)NULL;}

前驱和后继

查找前驱

template<class T>BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x){// 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。if(x->left!=NULL) return maximum(x->left);// 如果x没有左孩子。则x有以下两种可能： // (1) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。 // (2) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。 BSTNode<T> *p = x->parent; while(p!=NULL && x==p->left) { x = p; p = p->parent;}return p;}

查找后继

template<class T>BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x){// 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。if(x->right!=NULL) return minimum(x->right);// 如果x没有右孩子。则x有以下两种可能： // (1) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。 // (2) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。 BSTNode<T> *p = x->parent; while(p!=NULL && x==p->right) { x = p; p = p->parent;}return p;}

插入

template<class T>void BSTree<T>::insert(BSTNode<T>* &tree, BSTNode<T> *z){BSTNode<T> *y = NULL;BSTNode<T> *x = tree;// 查找z的插入位置while(x!=NULL){ y = x; if(z->key < x->key) x = x->left; else// else if(z->key > x->key) x = x->right;// 若禁止插入相同键值// else// {// free(z)；// 释放之前分配的结点 // return;// }}z->parent = y;if(y==NULL) tree = z;else if(z->key<y->key) y->left = z;else y->right = z;}

template<class T>void BSTree<T>::insert(T key){BSTNode<T> *z = NULL;// 如果新建结点失败，则返回if((z=new BSTNode<T>(key,NULL,NULL,NULL))==NULL) return; insert(root,z); }

删除

template<class T>BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z){BSTNode<T> *x = NULL;BSTNode<T> *y = NULL;if(z->left==NULL || z->right==NULL) y = z;else y = successor(z);if(y->left!=NULL) x = y->left;else x = y->right;if(x!=NULL) x->parent = y->parent; if(y->parent==NULL) tree = x;else if(y==y->parent->left) y->parent->left = x;else y->parent->right = x; if(y!=z) z->key = y->key;return y;}

template<class 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<class T>void BSTree<T>::print(BSTNode<T> *tree, T key, int direction){if(tree!=NULL){ if(direction==0) cout<<setw(2)<<tree->key<<"is root"<<endl; else cout<<setw(2)<<tree->key<<"is"<<setw(2)<<key<<"'s"<<setw(12)<<(direction==1 ? "right child":"left child")<<endl; print(tree->left,tree->key,-1); print(tree->right,tree->key,1);}}

template<class T>void BSTree<T>::print(){if(root!=NULL) print(root,root->key,0);}

销毁

template<class T>void BSTree<T>::destroy(BSTNode<T> *&tree){if(tree==NULL) return ;if(tree->left!=NULL) return destroy(tree->left);if(tree->right!=NULL) return destroy(tree->right);delete tree;tree=NULL;}

template<class T>void BSTree<T>::destroy(){destroy(root);}

二叉查找树完整实现：BSTree.h

#ifndef BINARY_SEARCH_TREE#define BINARY_SEARCH_TREE

#include<iomanip>#include<iostream>using namespace std;

template<class T>class BSTNode{public: T key;// 关键字（键值） BSTNode *left;// 左孩子 BSTNode *right;// 右孩子 BSTNode *parent;// 父结点 BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r): key(value),parent(p),left(l),right(r) {} };

template<class T>class BSTree{private: BSTNode<T> *root;// 根结点 public: BSTree() {}; ~BSTree() {}; // 前序遍历 void preOrder(); // 中序遍历 void inOrder(); // 后序遍历 void postOrder(); // （递归实现）查找二叉树中键值为key的结点 BSTNode<T>* search(T key); // （非递归实现） 查找二叉树中键值为key的结点 BSTNode<T>* iterativeSearch(T key); // 查找最小结点（返回键值） T minimum(); // 查找最大结点（返回键值） T maximum(); // 找结点（x）的后继结点。即查找二叉树中键值大于该结点的最小结点 BSTNode<T>* successor(BSTNode<T> *x); // 找结点（x）的前驱结点。即查找二叉树中键值小于该结点的最大结点 BSTNode<T>* predecessor(BSTNode<T> *x); // 将键值为key的结点插入到二叉树中 void insert(T key); // 删除键值为key的结点 void remove(T key); // 销毁二叉树 void destroy(); // 打印二叉树 void print(); private: // 重载函数，提供内部接口 // 前序遍历 void preOrder(BSTNode<T> *tree) const; // 中序遍历 void inOrder(BSTNode<T> *tree) const; // 后序遍历 void postOrder(BSTNode<T> *tree) const; // （递归实现）查找二叉树中键值为key的结点 BSTNode<T>* search(BSTNode<T> *x, T key) const; // （非递归实现） 查找二叉树中键值为key的结点 BSTNode<T>* iterativeSearch(BSTNode<T> *x, T key) const; // 查找最小结点（返回键值） BSTNode<T>* minimum(BSTNode<T> *tree); // 查找最大结点（返回键值） BSTNode<T>* maximum(BSTNode<T> *tree); // 将结点z插入到二叉树tree中 void insert(BSTNode<T>* &tree, BSTNode<T> *z); // 删除二叉树中的结点z，并返回该结点 BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z); // 销毁二叉树 void destroy(BSTNode<T>* &tree); // 打印二叉树 void print(BSTNode<T>* &tree, T key, int direction);};

template<class T>void BSTree<T>::preOrder(BSTNode<T> *tree) const{if(tree!=NULL){ cout<<tree->key<<" "; preOrder(tree->left); preOrder(tree->right);} }

template<class T>void BSTree<T>::preOrder(){preOrder(root);}

template<class T>void BSTree<T>::inOrder(BSTNode<T> *tree) const{if(tree!=NULL){ inOrder(tree->left); cout<<tree->key<<" "; inOrder(tree->right);} }

template<class T>void BSTree<T>::inOrder(){inOrder(root);}

template<class T>void BSTree<T>::postOrder(BSTNode<T> *tree) const{if(tree!=NULL){ postOrder(tree->left); postOrder(tree->right); cout<<tree->key<<" ";} }

template<class T>void BSTree<T>::postOrder(){postOrder(root);}

template<class T>BSTNode<T>* BSTree<T>::search(BSTNode<T>* x, T key) const{if(x==NULL || x->key==key) return x;if(key<x->key) return search(x->left, key);else return search(x->right, key);}

template<class T>BSTNode<T>* BSTree<T>::search(T key){search(root, key);}

template<class T>BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T>* x, T key) const{while(x!=NULL && x->key!=key){ if(key<x->key) x = x->left; else x = x->right;}return x;}

template<class T>BSTNode<T>* BSTree<T>::iterativeSearch(T key){iterativeSearch(root, key);}

template<class T>BSTNode<T>* BSTree<T>::maximum(BSTNode<T> *tree){if(tree==NULL) return NULL;while(tree->right!=NULL) tree = tree->right;return tree;}

template<class T>T BSTree<T>::maximum(){BSTNode<T> *p = maximum(root);if(p!=NULL) return p->key;return (T)NULL;}

template<class T>BSTNode<T>* BSTree<T>::minimum(BSTNode<T> *tree){if(tree==NULL) return NULL;while(tree->left!=NULL) tree = tree->left;return tree;}

template<class T>T BSTree<T>::minimum(){BSTNode<T> *p = minimum(root);if(p!=NULL) return p->key;return (T)NULL;}

template<class T>BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x){// 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。if(x->left!=NULL) return maximum(x->left);// 如果x没有左孩子。则x有以下两种可能： // (1) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。 // (2) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。 BSTNode<T> *p = x->parent; while(p!=NULL && x==p->left) { x = p; p = p->parent;}return p;}

template<class T>BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x){// 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。if(x->right!=NULL) return minimum(x->right);// 如果x没有右孩子。则x有以下两种可能： // (1) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。 // (2) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。 BSTNode<T> *p = x->parent; while(p!=NULL && x==p->right) { x = p; p = p->parent;}return p;}

template<class T>void BSTree<T>::insert(BSTNode<T>* &tree, BSTNode<T> *z){BSTNode<T> *y = NULL;BSTNode<T> *x = tree;// 查找z的插入位置while(x!=NULL){ y = x; if(z->key < x->key) x = x->left; else// else if(z->key > x->key) x = x->right;// 若禁止插入相同键值// else// {// free(z)；// 释放之前分配的结点 // return;// }}z->parent = y;if(y==NULL) tree = z;else if(z->key<y->key) y->left = z;else y->right = z;}

template<class T>void BSTree<T>::insert(T key){BSTNode<T> *z = NULL;// 如果新建结点失败，则返回if((z=new BSTNode<T>(key,NULL,NULL,NULL))==NULL) return; insert(root,z); }

template<class T>BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z){BSTNode<T> *x = NULL;BSTNode<T> *y = NULL;if(z->left==NULL || z->right==NULL) y = z;else y = successor(z);if(y->left!=NULL) x = y->left;else x = y->right;if(x!=NULL) x->parent = y->parent; if(y->parent==NULL) tree = x;else if(y==y->parent->left) y->parent->left = x;else y->parent->right = x; if(y!=z) z->key = y->key;return y;}

template<class 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<class T>void BSTree<T>::print(BSTNode<T> *&tree, T key, int direction){if(tree!=NULL){ if(direction==0) cout<<setw(2)<<tree->key<<"is root"<<endl; else cout<<setw(2)<<tree->key<<"is"<<setw(2)<<key<<"'s"<<setw(12)<<(direction==1 ? "right child":"left child")<<endl; print(tree->left,tree->key,-1); print(tree->right,tree->key,1);}}

template<class T>void BSTree<T>::print(){if(root!=NULL) print(root,root->key,0);}

template<class T>void BSTree<T>::destroy(BSTNode<T> *&tree){if(tree==NULL) return ;if(tree->left!=NULL) return destroy(tree->left);if(tree->right!=NULL) return destroy(tree->right);delete tree;tree=NULL;}

template<class T>void BSTree<T>::destroy(){destroy(root);}

#endif

测试代码：BSTreeTest.cpp

#include<iostream>#include "BSTree.h"using namespace std;

static int arr[] = {1,5,4,3,2,6};

int main(){int i,len;BSTree<int> *tree = new BSTree<int>();cout<<"依次添加：";len = sizeof(arr)/sizeof(arr[0]);for(i=0;i<len;++i){ cout<<arr[i]<<" "; tree->insert(arr[i]);}cout<<"\n前序遍历：";tree->preOrder();cout<<"\n中序遍历：";tree->inOrder();cout<<"\n后序遍历：";tree->postOrder();cout<<endl;cout<<"最小值："<<tree->minimum()<<endl;cout<<"最大值："<<tree->maximum()<<endl;cout<<"树的详细信息："<<endl;tree->print();cout<<" \n删除根节点："<<arr[3];tree->remove(arr[3]);cout<<"\n中序遍历：";tree->inOrder();cout<<endl;// 销毁二叉树tree->destroy();

return 0; }

本文永久更新链接地址：http://www.xuebuyuan.com/Linux/2017-01/139796.htm

以上就上有关二叉查找树解析及其C++实现的全部内容，学步园全面介绍编程技术、操作系统、数据库、web前端技术等内容。