二叉排序树是一种便于查找的一种有序树。其中二叉排序树的左子树均小于其根结点的值,右子树均大于其根结点的值。所以二叉排序树是一种递归的方式建立和查询以及插入。由于二叉树的删除有点儿复杂,所以没有给出代码。删除大体上是三种情况:1.直接删除叶子结点2.删除只带有一个分支的结点,让其分支节点直接代替其根结点3.删除多个分支的结点,让删除结点的中序序列直接后继代替被删结点。下面请看详细的代码:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct BSTNode{
int data;
struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;
//二叉排序树的插入
int BST_Insert(BiTree &T,int key){
if(T==NULL){
T = (BSTNode*)malloc(sizeof(BSTNode));
T->data = key;
T->lchild = T->rchild = NULL;
return 1;
}
else if(key == T->data){
return 0;
}
else if(key > T->data){
return BST_Insert(T->rchild,key);
}
else{
return BST_Insert(T->lchild,key);
}
}
//二叉排序树的查找
BSTNode* BST_Search(BiTree T,int key){
if(T==NULL){
return NULL;
}
else if(key > T->data){
return BST_Search(T->rchild);
}
else{
return BST_Search(T->lchild);
}
}
//构造二叉排序树
void Create_BST(BiTree &T,int num[],int n){
T = NULL;
int i = 0;
while(i<n){
BST_Insert(T,num[i]);
i++;
}
}
int main(int argc, char** argv) {
int num[] = {1,2,3,4,5};
BiTree T;
Create_BST(T,num,5);
BST_Search(T,3);
return 0;
}