考研数据结构 04 Binary Search Tree

发布于 2021-09-09  126 次阅读

一、二叉树节点

  这里需要注意的是，如果以模板方法构造二叉树，推荐将内部节点类也声明一个模板，否则类外函数（声明在h文件，实现在cpp文件）的返回类型不能是Node*，使用模板后则可以使用BinaryTree\<elemTYpe>::Node\<elemType>*。

template<typename elemType>
class BinaryTree
{
private:
    /* ===== Member 00 : 二叉树节点 ===== */
    template<typename elemType>
    class Node
    {
    public:
        elemType element;
        Node* left;
        Node* right;

        // 构造函数
        Node(const elemType& p_ele, Node* p_lt, Node* p_rt)
            : element(p_ele), left(p_lt), right(p_rt) { }

        Node(elemType&& p_ele, Node* p_lt, Node* p_rt)
            : element(p_ele), left(p_lt), right(p_rt) { }
    };

    /* ===== Member 01 : 根节点 ===== */
    Node<elemType>* root;
}

二、查找

  遍历在pgExam03中已经写过，这里不再赘述。

2.1 按值查找

template<typename elemType>
BinaryTree<elemType>::Node<elemType>* BinaryTree<elemType>::FindVal(const elemType& ele, Node<elemType>* node)
{
    // 空节点
    if (!node) return nullptr;

    // 是当前节点
    if (node->element == ele) return node;

    // 查左子树
    Node<elemType>* lt = nullptr;
    lt = this->FindVal(ele, node->left);

    if (lt) return lt;

    // 查右子树
    Node<elemType>* rt = nullptr;
    rt = this->FindVal(ele, node->right);

    if (rt) return rt;

    // 无结果
    return nullptr;
}

2.2 查找最值

/* ===== Function 08 : 查找最小值 ===== */
template<typename elemType>
BinaryTree<elemType>::Node<elemType>* BinaryTree<elemType>::FindMin(Node<elemType>* node)
{
    if (!node) return nullptr;

    if (!node->left) return node;

    return FindMin(node->left);
}

/* ===== Function 09 : 查找最大值 ===== */
template<typename elemType>
BinaryTree<elemType>::Node<elemType>* BinaryTree<elemType>::FindMax(Node<elemType>* node)
{
    if (!node) return nullptr;

    if (!node->right) return node;

    return FindMax(node->right);
}

三、插入与删除

3.1 插入

  这里我们逐次比较，找到合适的位置就插入。

template<typename elemType>
void BinaryTree<elemType>::Insert(const elemType& ele, Node<elemType>*& node)
{
    // 有空位插
    if (!node)
    {
        node = new Node<elemType>(ele, nullptr, nullptr);
    }
    // 这个空位有人了，和他比较下，按一定排序准则选择左右，这里以 < 为排序准则。
    else if (ele < node->element)
    {
        this->Insert(ele, node->left);
    }
    else if (node->element < ele)
    {
        this->Insert(ele, node->right);
    }
}

3.2 删除

  找到当前节点的大一值或小一值（中序遍历相邻的值）来替换这个节点

template<typename elemType>
void BinaryTree<elemType>::Remove_val(const elemType& ele, Node<elemType>*& node)
{
    if (!node) return;

    // 不是目标，比较
    if (ele < node->element)
        this->Remove_val(ele, node->left);
    else if (ele > node->element)
        this->Remove_val(ele, node->left);
    // 找到目标
    else if (node->left && node->right)       // 被删除目标有两个节点
    {
        // 可替换左子树的最大值、右子树的最小值（中序向量的两个点，选一）
        node->element = this->FindMin(node->right)->element;
        // 更新删除目标
        Remove_val(node->element, node->right);
    }
    else                                    // 被删除目标只有一个节点或无节点
    {
        Node<elemType>* oldOne = node;
        node = (node->left) ?
            node->left :
            node->right;
        delete oldOne;
    }
}

四、高度与宽度

4.1 高度

template<typename elemType>
int BinaryTree<elemType>::Height(Node<elemType>* node)
{
    if (!node)  return 0;

    return std::max(this->Height(node->left), this->Height(node->right)) + 1;
}

4.2 宽度

  宽度结合层次遍历来判断，完全二叉树的判断也用此种方法。

template<typename elemType>
int BinaryTree<elemType>::Width(Node<elemType>* node)
{
    if (!node)  return 0;

    std::deque<Node<elemType>*> dq;
    dq.push_back(node);

    int maxWidth = 1;
    int currentWidth = 1;

    while (!dq.empty())
    {
        while (currentWidth > 0)
        {
            // 队首出队，将下一层压入队列
            Node<elemType>* head = dq.front();
            dq.pop_front();

            if (head->left)  dq.push_back(head->left);
            if (head->right) dq.push_back(head->right);

            currentWidth--;
        }

        // 下一层的节点数
        currentWidth = dq.size();

        maxWidth = (maxWidth < currentWidth) ?
            currentWidth :
            maxWidth;
    }

    return maxWidth;
}

五、完全、平衡与旋转

5.1 完全二叉树

template<typename elemType>
bool BinaryTree<elemType>::is_Complete(Node<elemType>* node)
{
    if (!node)  return false;

    std::deque<Node<elemType>*> dq;
    dq.push_back(node);

    int currentWidth = 1;
    int currentLevel = 0;

    while (!dq.empty())
    {
        while (currentWidth > 0)
        {
            // 队首出队，将下一层压入队列
            Node<elemType>* head = dq.front();
            dq.pop_front();

            if (head->left)  dq.push_back(head->left);
            if (head->right) dq.push_back(head->right);

            currentWidth--;
        }

        // 下一层的节点数
        currentWidth = dq.size();
        currentLevel++;

        if ((currentWidth != pow(2, currentLevel))&& (currentWidth != 0))
        {
            return false;
        }
    }

    return true;
}

5.2 平衡二叉树

template<typename elemType>
bool BinaryTree<elemType>::is_Avl(Node<elemType>* node, int& height)
{
    if (!node)
    {
        height = 0;
        return true;
    }

    // left height
    int lh(0);
    // left flag
    bool lf = this->is_Avl(node->left, lh);

    // right
    int rh(0);
    bool rf = this->is_Avl(node->right, rh);

    if (lf && rf && abs(lh - rh) <= 1)
    {
        height = std::max(lh, rh) + 1;
    }
    else
    {
        height = std::max(lh, rh) + 1;
        return false;
    }

    return true;
}

5.3 旋转

template<typename elemType>
BinaryTree<elemType>::Node<elemType>* BinaryTree<elemType>::Mirror(Node<elemType>* node)
{
    if (!node)  return nullptr;

    Node<elemType>* lt = this->Mirror(node->left);
    Node<elemType>* rt = this->Mirror(node->right);

    node->left = rt;
    node->right = lt;

    return node;
}