算法读书笔记第3章-1

二叉查找树（BST）：首先是一棵二叉树，任意节点的值都大于其左子树的值，小于其右子树的值

主要操作就是插入和查找，二者的实现差不多，主要是插入。

关键思想：二分，插入值为value，value 大于key 向右子树出发，小于则向左子树出发

注意：BST不允许有相等的值出现

核心代码：

typedef struct bst
{
    int nValue;
    struct bst *pLeft;
    struct bst *pRight;
}BST;

void AddNode(BST **pTree,int nNum)
{
    BST *pTemp = NULL;
    pTemp = (BST*)malloc(sizeof(BST));
    pTemp->nValue = nNum;
    pTemp->pLeft = NULL;
    pTemp->pRight = NULL;

    //空树
    if(*pTree == NULL)
    {
        *pTree = pTemp;
        return;
    }

    BST *pNode = *pTree;

    while(pNode)
    {
        if(pNode->nValue > nNum)
        {
            //左侧
            if(pNode->pLeft == NULL)
            {
                pNode->pLeft = pTemp;
                return;
            }
            pNode = pNode->pLeft;
        }
        else if(pNode->nValue < nNum)
        {
            //右侧
            if(pNode->pRight == NULL)
            {
                pNode->pRight = pTemp;
                return;
            }
            pNode = pNode->pRight;
        }
        else
        {
            //相等
            printf("data error.\n");
            free(pTemp);
            pTemp = NULL;
            return;
        }
    }
}

BST *CreateBST(int arr[],int nLength)
{
    if(arr == NULL || nLength <= 0)return NULL;

    int i;
    BST *pTree = NULL;
    for(i = 0;i<nLength;i++)
    {
        AddNode(&pTree,arr[i]);
    }

    return pTree;
}