必威体育Betway必威体育官网
当前位置:首页 > IT技术

二叉排序树

时间:2019-09-06 17:10:00来源:IT技术作者:seo实验室小编阅读:79次「手机版」
 

二叉排序树

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

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);
            }
        }
    }
}

相关阅读

二叉排序树

二叉排序树,也称二叉查找树。它或者是一个空树,或者具有以下性质: 左子树不为空,则左子树的所有结点的值小于它根节点的值 右子树不为

分享到:

栏目导航

推荐阅读

热门阅读