[数据结构与算法]数据结构---二叉排序树

//
//  排序二叉树
//



# include<iostream>
# include<stdio.h>
# include<math.h>
using namespace std;
# define numm 9
typedef int Elemtype;

typedef struct BSTNode{
    Elemtype data;
    BSTNode *lchild,*rchild;

}BSTNode,*BiTree;

int n = numm;
int num[25] = {8,3,6,7,2,1,4,9,5};

void printTree(BSTNode *p){
    printf("%d  ",p->data);
}

void inOrder(BiTree &T){
    if(T!=NULL){
        printTree(T);
        inOrder(T->lchild);
        inOrder(T->rchild);
    }
}


BSTNode *BST_Search(BiTree T,Elemtype key){     //查找操作
    while(T!=NULL && T->data!=key){
        if(T->data > key)
            T = T->lchild;
        else
            T = T->rchild;
    }

    return T;

}


int BST_Insert(BiTree &T,Elemtype k){    //插入操作
    if(T==NULL){
        T = (BSTNode*)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    else if(T->data == k)  //如果有相同的节点，则插入失败
        return 0;
    else if(k < T->data)
        return BST_Insert(T->lchild,k);
    else if(k > T->data)
        return BST_Insert(T->rchild,k);
}


void create_BST(BiTree &T)
{
    T = NULL;
    int i = 0;
    while(i<n){
        BST_Insert(T,num[i]);
        i++;
    }
}


int main(void){
    BiTree T;
    BSTNode *p,*q;
    create_BST(T);
    inOrder(T);
    p = BST_Search(T,6);
    q = p->rchild;
    p = p->lchild;

    printf("\n%d %d",p->data,q->data);


    return 0;
}