【数据结构】 二叉排序树的建立与查找

"Btree.h"

#ifndef BTREE_H_INCLUDED
#define BTREE_H_INCLUDED
 typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
 }BiTNode,*BiTree;

int PreorderTraverse(BiTree T);
int InorderTraverse(BiTree T);
int PostorderTraverse(BiTree T);
int InsertBST(BiTree *T,int key);
int SearchBST(BiTree T,int key,BiTree f,BiTree *p);
#endif // BTREE_H_INCLUDED

"Btree.c"

树的查找：

int SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
    if(!T)
    {
        *p = f;
        printf("空\n");
        return 0;
    }
    else if(key == T->data)
    {
        *p =T;
        printf("==\n");
        return 1;
    }
    else if(key < T->data)
    {
        printf("<\n");
        return SearchBST(T->lchild,key,T,p);
    }
    else
    {
        printf(">\n");
        return SearchBST(T->rchild,key,T,p);
    }
}

树的建立与插入：

int InsertBST(BiTree *T,int key)
{
    BiTree p,s;
    if(!SearchBST(*T,key,NULL,&p))
    {
        s = (BiTree) malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = NULL;
        s->rchild = NULL;
        if(!p)
            *T = s;
        else if(key < p->data)
            p->lchild = s;
        else
            p->rchild = s;
        return 1;
    }
    else
        return 0;
}

树的三种遍历：

//先序遍历
int PreorderTraverse(BiTree T){
    if(T == NULL)return 1;
    else{
        printf("%d ",T->data);
        PreorderTraverse(T->lchild);
        PreorderTraverse(T->rchild);
    }
}
//中序遍历
int InorderTraverse(BiTree T){
    if(T == NULL) return 1;
    else{
        InorderTraverse(T->lchild);
        printf("%d ",T->data);
        InorderTraverse(T->rchild);
    }
}
//后序遍历
int PostorderTraverse(BiTree T){
    if(T == NULL) return 1;
    else{
        PostorderTraverse(T->lchild);
        PostorderTraverse(T->rchild);
        printf("%d ",T->data);

    }
}

"main.c"

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Btree.h"
#define MAXSIZE 20
int main()
{
    int a[MAXSIZE] = {0};
    int i;
    int find;
    int rec;
    BiTree T = NULL;
    BiTree p = NULL;
    srand((unsigned)time(NULL));
    for(i=1;i<MAXSIZE+1;i++)
    {
        a[i] = rand()%50+1;
        while(SearchBST(T,a[i],NULL,&p)==1)
            a[i]=rand()%10+1;
        InsertBST(&T,a[i]);
    }
　　
    printf("先序: ");
    PreorderTraverse(T);
    printf("\n");
    printf("中序: ");
    InorderTraverse(T);
    printf("\n");
    printf("后序: ");
    PostorderTraverse(T);
    printf("\n");

//print_List(a,MAXSIZE);
    while(1)
    {
        printf("你想查找的数据为：");
        scanf("%d",&find);
        rec = SearchBST(T,find,NULL,&p);
        if(rec == 1)
            printf("找到了!\n");
        else
            printf("没找到\n");
    }
}

一个测试:

我们知道

先序： 根 左 右

中序： 左 根 右

后序： 左 右 根

尝试画出这个树：