二叉排序树

二叉排序树，也叫二叉搜索树，也叫二叉查找树，是一种重要的数据结构。

1.定义

二叉排序树要么是一颗空树，要么具有以下性质：
- 若左子树不空，左子树上的节点的值小于或等于根节点的值；
- 若右子树不空，左子树上的节点的值大于或等于根节点的值；
- 左右子树也均为二叉排序树。

class BSTree
{
public:
    BSTree(int idata)
    {
        data = idata;
        lChild = rChild = NULL;
    }
    ~BSTree(){}
    int data;
    BSTree *lChild,*rChild;
};

2.二叉排序树的基本操作

二叉排序树的基本操作包括插入节点、删除节点、遍历排序树（前序、中序、后序）等。

2.1 遍历

2.1.1前序遍历

///前序遍历
vector<int> preOrder(BSTree* node)
{
    vector<int> result;
    if(node == NULL)
        return result;
    //根节点
    result.push_back(node->data);

    //遍历左子树
    vector<int> tempResult = preOrder(node->lChild);
    result.insert(result.end(),tempResult.begin(),tempResult.end());

    //遍历右子树
    tempResult = preOrder(node->rChild);
    result.insert(result.end(),tempResult.begin(),tempResult.end());

    return result;
}

2.1.2中序遍历

///中序遍历
vector<int> midOrder(BSTree* node)
{
    vector<int> result;
    if(node == NULL)
        return result;

    //遍历左子树
    vector<int> tempResult = midOrder(node->lChild);
    result.insert(result.end(),tempResult.begin(),tempResult.end());

    //根节点
    result.push_back(node->data);

    //遍历右子树
    tempResult = midOrder(node->rChild);
    result.insert(result.end(),tempResult.begin(),tempResult.end());

    return result;
}

#endif //BSTREE_H

2.1.3后序遍历

///后序遍历
vector<int> rearOrder(BSTree* node)
{
    vector<int> result;
    if(node == NULL)
        return result;

    //遍历左子树
    vector<int> tempResult = rearOrder(node->lChild);
    result.insert(result.end(),tempResult.begin(),tempResult.end());

    //遍历右子树
    tempResult = rearOrder(node->rChild);
    result.insert(result.end(),tempResult.begin(),tempResult.end());

    //根节点
    result.push_back(node->data);

    return result;
}

2.2插入节点

///插入节点
void insertNode(int iData,BSTree* header)
{
    if(header == NULL)
    {
        header = (BSTree*)malloc(sizeof(BSTree));
        if(header == NULL)
        {
            printf("malloc failure!");
            return;
        }
        header->data = iData;
        header->lChild = header->rChild = NULL;
        return;
    }
    else
    {
        if(iData>header->data)
            insertNode(iData,header->rChild);
        else
            insertNode(iData,header->lChild);
    }
}

2.3删除节点

删除节点分为4种情况：

1. 该节点是叶子节点；
2. 该节点只有左子树；
3. 该节点只有右子树；
4. 该节点同时有左子树和右子树。

对应的解决办法分别为：
①直接删除叶子节点；②用该节点的左子树取代该节点；③用该节点的右子树取代该节点；④用该节点的右子树的值最小的节点取代该节点；

///删除节点
BSTree* deleteNode(int iData,BSTree* header)
{
    if(header == NULL)
        return NULL;
    else
    {
        if(iData>header->data)
            return deleteNode(iData,header->rChild);
        else if(iData<header->data)
            return deleteNode(iData,header->rChild);
        else
        {
            ///删除节点有两个孩子
            if(iheader->lChild != NULL && header->rChild != NULL)
            {
                BSTree *tempNode = header->rChild;
                while(tempNode->lChild!=NULL)
                    tempNode = tempNode->lChild;
                header->data = tempNode->data;
                return deleteNode(iData,tempNode);
            }
            ///删除节点有1个孩子或者没有孩子
            else if(header->lChild==NULL || header->rChild == NULL)
            {
                BSTree *tempNode = header;
                header = (header->lChild == NULL)?header->rChild:header->lChild;
                free(tempNode);
            }
        }
    }
}