欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉排序树

程序员文章站 2022-06-05 16:44:50
...

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

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);
            }
        }
    }
}
相关标签: 二叉排序树