（1）、若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
（2）、若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
（3）、它的左、右子树也分别为二叉查找树。
二叉查找树插入：
过程如下：
若当前的二叉查找树为空，则插入的元素为根节点；若插入的元素值小于根节点值，则将元素插入到左子树中；若插入的元素值不小于根节点值，则将元素插入到右子树中。 c++实现：
BisearchTreeNode* Insert(BisearchTreeNode* pRoot, int data) { BisearchTreeNode* pNewNode = new BisearchTreeNode; if(pNewNode == NULL) return false; pNewNode->data = data; pNewNode->lchild = NULL; pNewNode->rchild = NULL; BisearchTreeNode* pCurrentNode = pRoot; BisearchTreeNode* pParentNode = pCurrentNode;// 保存父节点的指针 int flag = 0;// 标记插入节点的位置 if(pCurrentNode == NULL) { root = pNewNode; }else{ while(pCurrentNode) { if(data < pCurrentNode->data) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->lchild; flag = 0; }else if(data > pCurrentNode->data){ pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->rchild; flag = 1; } } if(flag == 0) { pParentNode->lchild= pNewNode; }else{ pParentNode->rchild= pNewNode; } } return pParentNode; }
二叉查找树之查找
这个比较简单，要么找到了，要么向左，要么向右。
c++实现:
BisearchTreeNode* search(BisearchTreeNode* node,int value) { BisearchTreeNode *result = NULL; if(node != NULL) { if(value == node->data) result = node; else if(value < node->data) result = search(node->lchild,value); else result = search(node->rchild,value); } return result; }
二叉查找树之搜索最小关键字与最大关键字元素
这个也比较简单，通过从树根开始沿着lchild直到遇到NULL，返回最小关键字元素，类似的沿着rchild直到遇到NULL，返回最大关键字元素
c++实现：
BisearchTreeNode* minimum(BisearchTreeNode* node) { while(node->lchild!=NULL) node=node->lchild; return node; } BisearchTreeNode* maximum(BisearchTreeNode* node) { while(node->rchild!=NULL) node=node->rchild; return node; } 测试代码:
利用中序遍历输出来判断构建的树是否成功。
#include <iostream> using namespace std; typedef struct node { struct node *lchild; struct node *rchild; int data; }BisearchTreeNode; /**根节点作为全局静态变量*/ static BisearchTreeNode *root; void init(BisearchTreeNode *root) { root=NULL; } BisearchTreeNode* Insert(BisearchTreeNode* pRoot, int data) { BisearchTreeNode* pNewNode = new BisearchTreeNode; if(pNewNode == NULL) return false; pNewNode->data = data; pNewNode->lchild = NULL; pNewNode->rchild = NULL; BisearchTreeNode* pCurrentNode = pRoot; BisearchTreeNode* pParentNode = pCurrentNode;// 保存父节点的指针 int flag = 0;// 标记插入节点的位置 if(pCurrentNode == NULL) { root = pNewNode; }else{ while(pCurrentNode) { if(data < pCurrentNode->data) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->lchild; flag = 0; }else if(data > pCurrentNode->data){ pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->rchild; flag = 1; } } if(flag == 0) { pParentNode->lchild= pNewNode; }else{ pParentNode->rchild= pNewNode; } } return pParentNode; } void midOutput(BisearchTreeNode* pRoot) { if(pRoot) { midOutput(pRoot->lchild); cout<<pRoot->data <<" "; midOutput(pRoot->rchild); } } BisearchTreeNode* search(BisearchTreeNode* node,int value) { BisearchTreeNode *result = NULL; if(node != NULL) { if(value == node->data) result = node; else if(value < node->data) result = search(node->lchild,value); else result = search(node->rchild,value); } return result; } BisearchTreeNode* minimum(BisearchTreeNode* node) { while(node->lchild!=NULL) node=node->lchild; return node; } BisearchTreeNode* maximum(BisearchTreeNode* node) { while(node->rchild!=NULL) node=node->rchild; return node; } int main() { int list[8] = {13,15,6,20,14,5,7,18}; init(root); for(int i = 0; i < 8; i++) Insert(root,list[i]); cout<<"中序遍历结果："<<endl; midOutput(root); cout<<endl<<"查找结果："<<endl; BisearchTreeNode* res; res=search(root,6); if(res!=NULL) cout<<res->data<<endl; cout<<"输出最小值："<<endl; BisearchTreeNode* min; min=minimum(root); cout<<min->data<<endl; cout<<"输出最大值："<<endl; BisearchTreeNode* max; max=maximum(root); cout<<max->data<<endl; return 0; }
测试结果:
