数据结构之二叉树查找
数据结构之--二叉树查找
定义：它是一棵树，或者具有以下性质的树。
若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
它的左、右子树也分别为二叉排序树；
图解：
#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);
}
};
运行结果：
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
