定义:它是一棵树,或者具有以下性质的树。
若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
它的左、右子树也分别为二叉排序树;
#include<stdio.h>
#include<stdlib.h>
typedef int Status;
#define TRUE 1
#define FALSE 0
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/*中序遍历二叉树*/
void InOrderTraverse(BiTree T){
if(T==NULL)
return;
InOrderTraverse(T->lchild);
printf("%d ",T->data);
InOrderTraverse(T->rchild);
}
/*二叉树查找*/
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p){
if(!T){
*p = f;
return FALSE;
}
else if(key==T->data){
*p = T;
return TRUE;
}
else if(key<T->data)
return SearchBST(T->lchild,key,T,p);
else
return SearchBST(T->rchild,key,T,p);
}
/*在二叉树上按左边小右边大的方式插入*/
Status InsertBST(BiTree *T,int key){
BiTree p,s;
if(!SearchBST(*T,key,NULL,&p)){
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild=NULL;
if(!p)
*T = s;
else if(key<p->data)
p->lchild=s;
else
p->rchild=s;
return TRUE;
}
else
return FALSE;
};
void main(){
int i;
int num[] = {62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;
for(i=0;i<10;i++){
InsertBST(&T,num[i]);
}
printf("中序遍历结果:");
InOrderTraverse(T);
printf("/n查找结果:");
BiTree p;
if(SearchBST(T,93,NULL,&p)){ //查找93
printf("%d/n",p->data);
}
};
运行结果: