15.5二叉排序树原理及建树实战

#include<stdio.h>
#include<stdlib.h>


typedef int KeyType;
typedef struct BSTNode{
    KeyType key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;

//非递归的创建二叉查找数
int BST_Insert(BiTree &T,KeyType k)
{
    BiTree TreeNew=(BiTree) calloc(1,sizeof (BSTNode));//新节点申请空间
    TreeNew->key=k;  //把值放入
    if(NULL==T)      //树为空，新结点作为树的根
    {
        T=TreeNew;
        return 0;
    }
    BiTree p=T,parent;   //用来查找树
    while (p)
    {
        parent=p;    //parent用来存p的父亲
        if(k>p->key)
        {
            p=p->rchild;
        } else if(k<p->key)
        {
            p=p->lchild;
        } else
        {
            return -1;   //相等元素不放入查找树
        }
    }
    //判断放到父亲左边还是右边
    if(k>parent->key)
    {
        parent->rchild=TreeNew;
    } else{
        //放到父亲左边
        parent->lchild=TreeNew;
    }
    return 0;
}


void Creat_BST(BiTree &T,KeyType *str,int len)
{
    int i;
    for (i = 0; i < len; i++) {
        BST_Insert(T,str[i]);    // 把某一个结点放入二叉查找树
    }
}

void InOrder(BiTree T)
{
    if(T!=NULL)
    {
        InOrder(T->lchild);
        printf("%3d",T->key);
        InOrder(T->rchild);
    }
}

BiTree BST_Search(BiTree T,KeyType k,BiTree &parent)
{
    parent=NULL;
    while (T!=NULL&&k!=T->key)
    {
        parent=T;
        if(k>T->key)
        {
            T=T->rchild;
        } else{
            T=T->lchild;
        }
    }
    return T;
}
//二叉排序树的创建，中序遍历，查找
int main() {
    BiTree T = NULL;   //树根
    KeyType str[7] = {54, 20, 66, 40, 28, 79, 58};  //将要进入二叉排序树的元素值
    Creat_BST(T, str, 7);
    InOrder(T);    //中序二叉查找树，由小到大
    printf("\n");
    BiTree search, parent;
    search = BST_Search(T, 40, parent);
    if (search)
    {
        printf("find key %d\n",search->key);
    } else{
        printf("not find\n");
    }
    return 0;
}