转载

数据结构之二叉树查找

数据结构之--二叉树查找

定义:它是一棵树,或者具有以下性质的树。

若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;

若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;

它的左、右子树也分别为二叉排序树;

图解:

数据结构之二叉树查找

#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);

}

};

运行结果:

数据结构之二叉树查找

正文到此结束
Loading...