小甲鱼来看看AVL树的问题

柠“萌”圆

我按你的教程敲的代码(虽然是C++的),测试正常,不过我前序遍历树时,根据遍历结果画出来的树不是AVL树,求解决

#ifndef AVL_H_INCLUDED
#define AVL_H_INCLUDED

#include <memory>
#include <initializer_list>
#include <iostream>


template <class Type>
class AVL{
    enum BF{RH = -1, EH, LH};

    struct BiTreeNode {
        Type _data;
        BF _bf;
        std::shared_ptr<BiTreeNode> _lChild;
        std::shared_ptr<BiTreeNode> _rChild;
    };

    typedef std::shared_ptr<BiTreeNode> Tree;

public:
    typedef size_t size_type;
    typedef Type value_type;
    typedef value_type& reference;
    typedef const reference const_reference;

    AVL(const AVL<Type>&) = delete;
    AVL<Type>& operator=(const AVL<Type>&) = delete;

    AVL() = default;
    AVL(const std::initializer_list<Type>& li) : AVL(li.begin(), li.end()) {}
    template <class In> AVL(In first, In last);

    AVL<Type>& push(const Type&);
//    AVL<Type>& pop(const Type&);
    bool find(const Type&)const;
    size_type size()const { return _size; }
    bool empty()const { return _size == 0; }
    const_reference root() const { return _root ->_data; }
    void show()const { show(_root); }

private:
    bool push(Tree& root, const Type&, bool& taller);
    void left_balance(Tree& root);
    void left_rotate(Tree& root); // 左旋操作
    void right_balance(Tree& root);
    void right_rotate(Tree& root); // 右旋操作
    bool find(const Tree&, const Type&)const;
    void show(const Tree&)const;

    Tree _root;
    size_type _size = 0;
};

template <class Type>
bool AVL<Type>::push(Tree& root, const Type& item, bool& taller)
{
    if (!root) {
        root = std::make_shared<BiTreeNode>();
        root ->_bf = EH;
        root ->_data = item;
        taller = true;
        ++_size;
    }
    else if (item == root ->_data)
        return taller = false;
    else if (item < root ->_data) {

        if (!push(root ->_lChild, item, taller))
            return false;

        if (taller) { // 树的高度增加了
            switch (root ->_bf) {

            case LH: // 未插入时左子树比右子树高
                     // 形成不平衡局面
                left_balance(root); // 调整
                taller = false; // 平衡后树的高度不增加
                break;

            case EH: // 未插入时树左右一样高
                root ->_bf = LH; // 插入后左子树比右子树高
                taller = true; // 树的高度增加了
                break;

            case RH: // 未插入时右子树高
                root ->_bf = EH; // 插入后左右子树一样高
                taller = false; // 树的高度未增加
                break;
            }
        }
        else { // 没有成功地插入左子树

            if (!push(root ->_rChild, item, taller))
                return false;

            if (taller) {
                switch (root ->_bf) {

                case LH:
                    root ->_bf = EH;
                    taller = false;
                    break;

                case EH:
                    root ->_bf = RH;
                    taller = true;
                    break;

                case RH:
                    right_balance(root);
                    taller = false;
                    break;
                }
            }
        }
    }
    else {
        if (!push(root ->_rChild, item, taller))
            return false;

        if (taller) {
            switch (root ->_bf) {

            case LH:
                root ->_bf = EH;
                taller = false;
                break;

            case EH:
                root ->_bf = RH;
                taller = true;
                break;

                case RH:
                right_balance(root);
                taller = false;
                break;
                }
            }
        else {
        if (!push(root ->_lChild, item, taller))
            return false;

        if (taller) {
            switch (root ->_bf) {

            case LH:

                left_balance(root);
                taller = false;
                break;

            case EH:
                root ->_bf = LH;
                taller = true;
                break;

            case RH:
                root ->_bf = EH;
                taller = false;
                break;
                }
            }
        }
    }
    return false;
}

template <class Type>
void AVL<Type>::left_balance(Tree& root)
{
    Tree l = root ->_lChild, lr;

    switch (l ->_bf) {

    case LH: // 若左子树比右子树高
        root ->_bf = l ->_bf = EH;
        right_rotate(root); // 右旋
        break;

    case RH:
        lr = l ->_rChild;

        switch (lr ->_bf) {

        case LH:
            root ->_bf = RH;
            l ->_bf = EH;
            break;

        case EH:
            root ->_bf = l ->_bf = EH;
            break;

        case RH:
            root ->_bf = EH;
            l ->_bf = LH;
            break;
        }
        lr ->_bf = EH;
        left_rotate(root ->_lChild); // 双旋处理
        right_rotate(root);

        break;
    }
}

template <class Type>
void AVL<Type>::right_rotate(Tree& root)
{
    Tree l = root ->_lChild;

    root ->_lChild = l ->_rChild;
    l ->_rChild = root;
    root = l;
}

template <class Type>
void AVL<Type>::left_rotate(Tree& root)
{
    Tree r = root ->_rChild;

    root ->_rChild = r ->_lChild;
    r ->_lChild = root;
    root = r;
}

template <class Type>
void AVL<Type>::right_balance(Tree& root)
{
    Tree l = root ->_lChild, lr;

    switch (l ->_bf) {

    case RH:// 若右子树比左子树高
        root ->_bf = l ->_bf = EH;
        left_rotate(root);
        break;

    case LH:
        lr = l ->_rChild;

        switch (lr ->_bf) {

        case LH:
            root ->_bf = RH;
            l ->_bf = EH;
            break;

        case EH:
            root ->_bf = l ->_bf = EH;
            break;

        case RH:
            root ->_bf = EH;
            l ->_bf = LH;
            break;
        }
        lr ->_bf = EH;
        right_rotate(root ->_rChild); // 双旋处理
        left_rotate(root);

        break;
    }
}

template <class Type>
AVL<Type>& AVL<Type>::push(const Type& item)
{
    bool taller;
    push(_root, item, taller);
    return *this;
}


template <class Type>
template <class In>
AVL<Type>::AVL(In first, In last)
{
    while (first != last)
        push(*first++);
}

template <class Type>
bool AVL<Type>::find(const Type& item)const
{
    return find(_root, item);
}

template <class Type>
bool AVL<Type>::find(const Tree& root, const Type& item)const
{
    if (root) {
        if (root ->_data == item)
            return true;
        if (item < root ->_data)
            return find(root ->_lChild, item);
        else
            return find(root ->_rChild, item);
    }

    return false;
}

template <class Type>
void AVL<Type>::show(const Tree& root)const
{
    if (root) {
        std::cout << "root:\n";
        std::cout << root ->_data << '\n';


        std::cout << "lChild:\n";
        show(root ->_lChild);

        if (root == _root)
            std::cout << "真*根节点";

        std::cout << "rChild:\n";
        show(root ->_rChild);

        if (!root ->_lChild && !root ->_rChild)
            std::cout << "*************************\n";
    }
}

#endif // AVL_H_INCLUDED

测试代码

#include "AVL.h"
#include <iostream>

int main()
{
    AVL<int> avl {5,7,8,9,3,0,1,2,4,1,5};

    std::cout << "size: " << avl.size() << "\nfind(5) = " << avl.find(5) << "\nfind(1) = " << avl.find(1)
    << "\nfind(8) = " << avl.find(8) << "\nfind(10) = " << avl.find(10) << "\nfind(0) = " << avl.find(0)
    << "\nfind(4) = " << avl.find(4) << "\nfind(3) = " << avl.find(3) << "\nfind(2) = " << avl.find(2) << "\nfind(7) = "
    << avl.find(7) << "\nfind(9) = " << avl.find(9) << "\n";
    avl.show();
    avl.push(10);
    std::cout << "\nfind(10) = " << avl.find(10) << "\n";
    return 0;
}