二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1、每一个节点都有一个作为搜索依据的关键码，所有节点的关键码互不相同。

2、左子树上所有节点的关键码都小于跟节点的关键码。

3、右子树上所有节点的关键码都大于跟节点的关键码。

4、左右子树都是二叉树搜索树。

#include<iostream>usingnamespacestd;template<typenameT>structTreeNode{TData;TreeNode<T>*left;TreeNode<T>*right;TreeNode<T>*parent;TreeNode(Tdata):left(NULL),right(NULL),Data(data),parent(NULL){}};template<typenameT>classBStree{public:BStree(){}~BStree(){}BStree(T*arr,size_tsz);voidInsert(Tdata){TreeNode<T>*tmp=newTreeNode<T>(data);InsertBStree(_root,tmp);}voidSearch(Tdata){TreeNode<T>*tmp=newTreeNode<T>(data);tmp=SearchBStree(_root,tmp);if(tmp)cout<<'Y'<<endl;elsecout<<'N'<<endl;}voidMin(){TreeNode<T>*node=MinBStree(_root);cout<<node->Data<<endl;}voidMax(){TreeNode<T>*node=MaxBStree(_root);cout<<node->Data<<endl;}voidMaxLeft(){TreeNode<T>*node=MaxLeftBStree(_root);cout<<node->Data<<endl;}voidMinRight(){TreeNode<T>*node=MinRightBStree(_root);cout<<node->Data<<endl;}voidPrevNode(Tdata){TreeNode<T>*tmp=newTreeNode<T>(data);tmp=SearchBStree(_root,tmp);if(tmp)tmp=prevBStree(tmp);cout<<tmp->Data<<endl;}voidPostNode(Tdata){TreeNode<T>*tmp=newTreeNode<T>(data);tmp=SearchBStree(_root,tmp);if(tmp)tmp=postBStree(tmp);cout<<tmp->Data<<endl;}voidDeleteNode(Tdata){TreeNode<T>*tmp=newTreeNode<T>(data);tmp=SearchBStree(_root,tmp);if(tmp)DeleteBStree(tmp);}voidDestroy(){DestroyBStree(_root);}voidMid(){MidOrder(_root);}voidMidOrder(TreeNode<T>*Root){if(Root==NULL)return;MidOrder(Root->left);cout<<Root->Data<<"";MidOrder(Root->right);}protected:voidInsertBStree(TreeNode<T>*root,TreeNode<T>*Node);TreeNode<T>*SearchBStree(TreeNode<T>*Root,TreeNode<T>*Node);TreeNode<T>*MinBStree(TreeNode<T>*Root);TreeNode<T>*MaxBStree(TreeNode<T>*Root);TreeNode<T>*MaxLeftBStree(TreeNode<T>*Root);TreeNode<T>*MinRightBStree(TreeNode<T>*Root);TreeNode<T>*prevBStree(TreeNode<T>*Node);TreeNode<T>*postBStree(TreeNode<T>*Node);voidDeleteBStree(TreeNode<T>*Node);voidDestroyBStree(TreeNode<T>*Root);private:TreeNode<T>*_root;};template<typenameT>BStree<T>::BStree(T*arr,size_tsz){_root=newTreeNode<T>(arr[0]);for(inti=1;i<sz;i++){TreeNode<T>*tmp=newTreeNode<T>(arr[i]);InsertBStree(_root,tmp);}}template<typenameT>voidBStree<T>::InsertBStree(TreeNode<T>*root,TreeNode<T>*Node){if(root==NULL)root=Node;else{TreeNode<T>*cur=NULL;while(root){cur=root;if(root->Data>Node->Data){root=root->left;}else{root=root->right;}}if(Node->Data>cur->Data){cur->right=Node;Node->parent=cur;}else{cur->left=Node;Node->parent=cur;}}}template<typenameT>TreeNode<T>*BStree<T>::SearchBStree(TreeNode<T>*Root,TreeNode<T>*Node){TreeNode<T>*cur=Root;while(cur&&cur->Data!=Node->Data){if(cur->Data>Node->Data){cur=cur->left;}else{cur=cur->right;}}if(cur)returncur;elsereturnNULL;}template<typenameT>TreeNode<T>*BStree<T>::MinBStree(TreeNode<T>*Root){TreeNode<T>*cur=Root;while(cur->left){cur=cur->left;}returncur;}template<typenameT>TreeNode<T>*BStree<T>::MaxBStree(TreeNode<T>*Root){TreeNode<T>*cur=Root;while(cur->right){cur=cur->right;}returncur;}template<typenameT>TreeNode<T>*BStree<T>::MaxLeftBStree(TreeNode<T>*Root){if(Root->left==NULL)returnNULL;TreeNode<T>*cur=Root->left;while(cur->right){cur=cur->right;}returncur;}template<typenameT>TreeNode<T>*BStree<T>::MinRightBStree(TreeNode<T>*Root){if(Root->right==NULL)returnNULL;TreeNode<T>*cur=Root->right;while(cur->left){cur=cur->left;}returncur;}template<typenameT>TreeNode<T>*BStree<T>::prevBStree(TreeNode<T>*Node){if(Node->left)returnMaxLeftBStree(Node);TreeNode<T>*P=Node->parent;if(Node->left==NULL&&Node==P->right){returnNode->parent;}while(P&&Node==P->left){Node=P;P=P->parent;}returnP;}template<typenameT>TreeNode<T>*BStree<T>::postBStree(TreeNode<T>*Node){if(Node->right)returnMinRightBStree(Node);TreeNode<T>*P=Node->parent;if(Node->right==NULL&&Node==P->left){returnNode->parent;}while(P&&Node==P->right){Node=P;P=P->parent;}returnP;}template<typenameT>voidBStree<T>::DeleteBStree(TreeNode<T>*Node){TreeNode<T>*cur=Node->parent;if(Node->left==NULL&&Node->right==NULL){if(Node==cur->left){deleteNode;cur->left=NULL;}else{deleteNode;cur->right=NULL;}}elseif(Node->left==NULL&&Node->right){TreeNode<T>*child=Node->right;if(Node==cur->left){deleteNode;cur->left=child;}else{deleteNode;cur->right=child;}}elseif(Node->right==NULL&&Node->left){TreeNode<T>*child=Node->left;if(Node==cur->left){deleteNode;cur->left=child;}else{deleteNode;cur->right=child;}}else{TreeNode<T>*tmp=postBStree(Node);Node->Data=tmp->Data;DeleteBStree(tmp);}}template<typenameT>voidBStree<T>::DestroyBStree(TreeNode<T>*Root){if(Root==NULL)return;if(Root->left)DestroyBStree(Root->left);if(Root->right)DestroyBStree(Root->right);deleteRoot;Root=NULL;}voidTest(){intarr[]={5,3,4,1,7,8,2,6,0,9};intsz=sizeof(arr)/sizeof(arr[0]);BStree<int>BS(arr,sz);/*BS.Mid();BS.Insert(10);BS.Mid();*//*BS.Max();BS.Min();BS.MaxLeft();BS.MinRight();BS.Search(6);*///BS.PrevNode(9);//BS.PostNode(4);BS.DeleteNode(5);BS.Mid();//BS.Destroy();//BS.Mid();}intmain(){Test();return0;}