[数据结构与算法]C++STL模板平衡二叉树（自动调节平衡、非递归遍历、合并复制删除、横竖打印树、树的复制等方法）

#include <iostream>
#include <queue>
#include <stack>
#include <climits>
#include <cstring>
#include <iomanip>

#define ArraySize 2048

/***二叉查找树***/
using namespace std;

enum EF {
    LH = 1, EH = 0, RH = -1
};

template<typename T>
class Node {
public:
    Node<T> *left, *right;
    T data;

    //平衡因子
    int EF{};

    Node() {
        left = right = nullptr;
    }

    explicit Node(const T &data, Node<T> *left = nullptr, Node<T> *right = nullptr) {
        this->data = data;
        this->right = right;
        this->left = left;
    }
};

template<typename T>
class BSTree {
protected:
    Node<T> *root;

    void clearHelp(Node<T> *r);

    void recursiveInsertHelp(Node<T> **p, const T &e);

    T *searchHelp(Node<T> *p, const T &e) const;

    //递归查找
    T *recursiveSearchHelp(Node<T> *p, const T &e) const;

    void preorderHelp(Node<T> *r);

    void inorderHelp(Node<T> *r);

    void postorderHelp(Node<T> *r);

    virtual void visit(Node<T> *p) {
        cout << p->data << ' ';
    }

    void deleteByMerging(Node<T> **node);

    void deleteByCopying(Node<T> **node);

    int heightHelp(Node<T> *r);

    void LRotate(Node<T> **n);

    void RRotate(Node<T> **n);

    bool LBalance(Node<T> **n);

    bool RBalance(Node<T> **n);

    bool Insert(Node<T> **n, T d, bool *taller);

    //复制树
    Node<T> *CopyHelp(const Node<T> *r);

public:
    BSTree() {
        root = nullptr;
    }

    ~BSTree() {
        clear();
    }

    void clear() {
        clearHelp(root);
        root = nullptr;
    }

    void isEmpty() {
        return root == nullptr;
    }

    void preorder() {
        preorderHelp(root);
    }

    void inorder() {
        inorderHelp(root);
    }

    void postorder() {
        postorderHelp(root);
    }

    void insert(const T &e);

    //递归插入
    void recursiveInsert(const T &e) {
        recursiveInsertHelp(&root, e);
    }

    void BSTInsert(T d);

    T *search(const T &e) const {
        return searchHelp(root, e);
    }

    T *recursiveSearch(const T &e) const {
        return searchHelp(root, e);
    }

    void balance(T *, int first, int last);

    Node<T> *getRoot() {
        return root;
    }

    void findAndDeleteByMergingOrCopy(const T &e);

    void findAndDeleteCopying(const T &e);

    void PrintBSTree();

    //获取树深度
    int getHeight() {
        return heightHelp(root);
    }

    BSTree(const BSTree<T> &source);

    BSTree<T> &operator=(const BSTree<T> &source);
};

template<typename T>
void DisplayWithTreeShape(const Node<T> *r, int level = 0);

template<typename T>
bool isBSTree(Node<T> *root);

template<typename T>
void BSTree<T>::insert(const T &e) {
    Node<T> *p = root, *prev;
    while (p) {
        prev = p;
        if (e < p->data)p = p->left;
        else p = p->right;
    }
    if (!root) {
        root = new Node<T>(e);
    } else if (e < prev->data) {
        prev->left = new Node<T>(e);
    } else {
        prev->right = new Node<T>(e);
    }
}

template<typename T>
void BSTree<T>::recursiveInsertHelp(Node<T> **p, const T &e) {
    if (p != nullptr)(*p) = new Node<T>(e);
    else if (e < (*p)->data)recursiveInsertHelp(&(*p)->left, e);
    else recursiveInsertHelp(&(*p)->right, e);
}

template<typename T>
void BSTree<T>::balance(T data[], int first, int last) {
    if (first <= last) {
        int middle = (first + last) / 2;
        insert(data[middle]);
        //左子树
        balance(data, first, middle - 1);
        //右子树
        balance(data, middle + 1, last);
    }
}

template<typename T>
void BSTree<T>::clearHelp(Node<T> *r) {
    if (r == nullptr)return;
    clearHelp(r->left);
    clearHelp(r->right);
    delete r;
}

template<typename T>
T *BSTree<T>::searchHelp(Node<T> *p, const T &e) const {
    while (p) {
        if (e == p->data)return &p->data;
        else if (e < p->data)p = p->left;
        else p = p->right;
    }
    return false;
}

template<typename T>
T *BSTree<T>::recursiveSearchHelp(Node<T> *p, const T &e) const {
    if (p) {
        if (e == p->data)return &p->data;
        else if (e < p->data)return recursiveSearchHelp(p->left, e);
        else return recursiveSearchHelp(p->right, e);
    }
    return false;
}

//合并删除指定节点
template<typename T>
void BSTree<T>::deleteByMerging(Node<T> **node) {
    Node<T> *temp = *node;
    if (*node) {
        //如果为叶子节点,或者度为1的节点将node置空或指向该节点孩子节点,删除该节点
        if (!(*node)->right)(*node) = (*node)->left;
        else if (!(*node)->left)(*node) = (*node)->right;
            //node节点有左右孩子
        else {
            //临时指针temp指向左孩子
            temp = (*node)->left;
            //temp向右遍历
            while (temp->right) {
                temp = temp->right;
            }
            //因为左子树中最大的元素在最右侧
            //然后将左子树最右侧孩子指向node节点右孩子,右孩子树中元素值均比左侧树大
            temp->right = (*node)->right;
            //temp指向node
            temp = (*node);
            //node变为node的左孩子即删除节点的父节点的子节点由node变为node的左孩子
            *node = (*node)->left;
        }
        //此时temp指向待删除节点
        delete temp;
    }
}

/*复制删除,即将删除节点的左子树最右侧的值附给当前节点,然后删除最右节点
将删除节点的左子树交给父节点的右子树,相当于删除node节点
并把删除节点的右子树放到左子树最右侧*/
template<typename T>
void BSTree<T>::deleteByCopying(Node<T> **node) {
    Node<T> *prev, *temp = *node;
    //该节点为叶子节点或者度为1的节点,将该节点的父节点的左或右孩子指针指向该节点的子节点或者置空
    if (!(*node)->right)(*node) = (*node)->left;
    else if (!(*node)->left)(*node) = (*node)->right;
    else {
        //存在左右孩子,temp指向左孩子
        temp = (*node)->left;
        prev = (*node);
        //将temp指向左子树最右即最大元素
        while (temp->right) {
            //prev为最大元素的父节点
            prev = temp;
            temp = temp->right;
        }
        //将左子树最大元素赋值给node节点
        (*node)->data = temp->data;
        //将temp节点去除树结构并删除
        //如果prev == node即temp不存在右子树,直接将node节点的左指针指向temp的左子树
        if (prev == (*node)) {
            prev->left = temp->left;
            //如果左子树存在最右节点,prev指向待删除节点的父节点,将待删除节点的左孩子指向父节点的右孩子
        } else prev->right = temp->left;
    }
    //删除temp节点
    delete temp;
}

//查找合并删除
template<typename T>
void BSTree<T>::findAndDeleteByMergingOrCopy(const T &e) {
    Node<T> *node = root, *prev;
    //查找值为e的节点
    while (node) {
        if (e == node->data)break;
        //前驱节点
        prev = node;
        if (e < node->data)node = node->left;
        else node = node->right;
    }
    //查找成功
    if (node && node->data == e) {
        if (node == root)deleteByMerging(&root);
        else if (prev->left == node)deleteByMerging(&prev->left);
        else deleteByMerging(&prev->right);
    } else if (root) {
        cout << "key " << e << " is not in the tree" << endl;
    } else cout << "the tree is empty" << endl;
}

template<typename T>
void BSTree<T>::preorderHelp(Node<T> *r) {
    if (r == nullptr)return;
    Node<T> *cur = r;
    stack<Node<T> *> st;
    st.push(cur);

    while (!st.empty()) {
        cur = st.top();
        st.pop();
        visit(cur);
        if (cur->right)st.push(cur->right);
        if (cur->left)st.push(cur->left);
    }
}

template<typename T>
void BSTree<T>::inorderHelp(Node<T> *r) {
    Node<T> *cur = r, *prev;
    stack<Node<T> *> st;
    //当前指针存在,栈非空
    while (cur || (!st.empty())) {
        //遍历放入左孩子
        if (cur) {
            st.push(cur);
            cur = cur->left;
        } else {
            //按照中序访问
            prev = st.top();
            visit(prev);
            st.pop();
            //指向右孩子
            cur = prev->right;
        }
    }
}

template<typename T>
void BSTree<T>::postorderHelp(Node<T> *r) {
    if (r == nullptr)return;
    Node<T> *cur = r, *prev;
    stack<Node<T> *> st;
    st.push(cur);
    prev = st.top();

    while (!st.empty()) {
        //cur->left存在且左右孩子均不为前驱指针
        if (cur->left && prev != cur->left && prev != cur->right) {
            st.push(cur->left);
        } else if (cur->right && prev != cur->right) {
            st.push(cur->right);
        } else {
            cur = st.top();
            visit(cur);
            st.pop();
            prev = cur;
        }
        if (!st.empty())cur = st.top();
    }
}

template<typename T>
void BSTree<T>::LRotate(Node<T> **n) {
    Node<T> *temp = (*n)->right;
    (*n)->right = temp->left;
    temp->left = *n;
    *n = temp;
}

template<typename T>
void BSTree<T>::RRotate(Node<T> **n) {
    Node<T> *temp = (*n)->left;
    (*n)->left = temp->right;
    temp->right = *n;
    *n = temp;
}

template<typename T>
bool BSTree<T>::LBalance(Node<T> **n) {
    Node<T> *l = (*n)->left;
    switch (l->EF) {
        case LH: {
            (*n)->EF = l->EF = EH;
            RRotate(n);
        }
            break;
        case RH: {
            Node<T> *lr = l->right;
            lr->EF = (*n)->EF = l->EF = EH;
            LRotate(&(*n)->left);
            RRotate(n);
            break;
        }
    }
    return true;
}

template<typename T>
bool BSTree<T>::RBalance(Node<T> **n) {
    Node<T> *r = (*n)->right;
    switch (r->EF) {
        case RH:
            (*n)->EF = r->EF = EH;
            LRotate(n);
            break;
        case LH: {
            Node<T> *rl = r->left;
            rl->EF = r->EF = (*n)->EF = EH;
            RRotate(&(*n)->right);
            LRotate(n);
            break;
        }
    }
    return true;
}

template<class T>
void BSTree<T>::PrintBSTree() {
    if (root != nullptr) {
        int depth = getHeight();                  //二叉排序树深度
        int h = depth;

        int a[ArraySize];                            //每一层除第一个结点外每个结点距离前一个结点的距离
        int c[ArraySize];                            //存储各结点投影在X轴上的坐标
        memset(a, 0, sizeof(a));
        for (int i = 0; i < depth; i++)                     //设置二叉树第i(从0开始)层最左的结点的坐标为2^(depth-i-1)
        {                                            //其中depth为二叉树的深度(从1开始)
            a[(1L << i) - 1] = (int) (1L << (depth - i - 1));
            c[(1L << i) - 1] = (int) (1L << (depth - i - 1));
            for (int j = (int) (1L << i); j < ((1L << (i + 1)) - 1); j++) {
                a[j] = 2 * a[(1L << i) - 1];                 //每一层除第一个结点外每个结点距离前一个结点的距离为第一个结点的两倍
                c[j] = c[j - 1] + a[j];
            }
        }

        int b[ArraySize];                         //以满二叉树为标准，比较二叉排序树在对应的位置是否存在结点,存在时标为1，不存在时标为-1
        memset(b, 0, sizeof(b));
        queue<Node<T> *> Q;                      //创建一个类型为SBTreeNode<T>* 的队列Q
        Node<T> *ptr = root;                      //根结点
        Q.push(ptr);                                  //根结点进入队列
        b[0] = 1;
        for (int i = 1; i < ((1L << depth) - 1);) {
            if (b[i] == -1) {
                if ((2 * i + 1) < ((1L << depth) - 1)) b[2 * i + 1] = -1;
                if ((2 * i + 2) < ((1L << depth) - 1)) b[2 * i + 2] = -1;
            } else if (b[i] == 0) {
                if (!Q.empty()) {
                    ptr = Q.front();
                    Q.pop();
                    if (ptr->left != nullptr) {
                        Q.push(ptr->left);
                        b[i] = 1;
                    } else {
                        b[i] = -1;
                        if ((2 * i + 1) < ((1L << depth) - 1)) b[2 * i + 1] = -1;
                        if ((2 * i + 2) < ((1L << depth) - 1)) b[2 * i + 2] = -1;
                    }
                    if (ptr->right != nullptr) {
                        Q.push(ptr->right);
                        b[i + 1] = 1;
                    } else {
                        b[i + 1] = -1;
                        if ((2 * i + 3) < ((1L << depth) - 1)) b[2 * i + 3] = -1;
                        if ((2 * i + 4) < ((1L << depth) - 1)) b[2 * i + 4] = -1;
                    }
                }
            }
            i = i + 2;
        }

        queue<Node<T> *> S;                      //创建一个类型为SBTreeNode<T>* 的队列S
        Node<T> *q = root;                      //根结点
        S.push(q);                                  //根结点进入队列
        for (int i = 0; i < ((1L << depth) - 1); i++) {
            if (b[i] == 1) {
                if (!S.empty()) {
                    q = S.front();
                    S.pop();
                    cout << setfill(' ') << setw(a[i] * 2) << q->data;
                    if (q->left != nullptr) S.push(q->left);
                    if (q->right != nullptr) S.push(q->right);
                }
            } else if (b[i] == -1) {
                cout << setfill(' ') << setw(a[i] * 2) << ' ';
            }
            //当a[i]>a[i+1]时，换行
            if (a[i] > a[i + 1]) {
                cout << endl;
                cout << endl;
            }
        }
        cout << endl;
    } else {
        cout << "二叉排序树为空！" << endl;
        return;
    }
}

template<typename T>
int BSTree<T>::heightHelp(Node<T> *r) {
    return r == nullptr ? 0 : max(heightHelp(r->left), heightHelp(r->right)) + 1;
}

template<typename T>
bool BSTree<T>::Insert(Node<T> **n, T d, bool *taller) {
    //当前节点为空
    if ((*n) == nullptr) {
        (*n) = new Node<T>(d, nullptr, nullptr);
        *taller = true;
        (*n)->EF = EH;
        return true;
    }
    //如果当前值已经存在
    if ((*n)->data == d) {
        cout << "this data is existed, please input again" << endl;
        *taller = false;
        return false;
    }
    //递归找到合适位置存左子树
    if ((*n)->data > d) {
        //插入失败
        if (!Insert(&(*n)->left, d, taller))return false;
        //插入成功
        if (*taller) {
            switch ((*n)->EF) {
                case LH: {
                    //当前节点左比右高1，再插入一个失去平衡左调整
                    LBalance(n);
                    //平衡
                    *taller = false;
                }
                    break;
                case EH: {
                    (*n)->EF = LH;
                    //不平衡
                    *taller = true;
                }
                    break;
                case RH: {
                    (*n)->EF = EH;
                    *taller = false;
                }
                    break;

            }
        }
    } else {
        if (!Insert(&(*n)->right, d, taller))return false;
        if (*taller) {
            switch ((*n)->EF) {
                case LH: {
                    (*n)->EF = EH;
                    *taller = false;
                }
                    break;
                case EH: {
                    (*n)->EF = RH;
                    *taller = true;
                }
                    break;
                case RH: {
                    RBalance(n);
                    *taller = false;
                }
                    break;
            }
        }
    }
    return true;
}

template<typename T>
void BSTree<T>::BSTInsert(T d) {
    //标识符判断树是否增高，导致不平衡
    bool taller = false;
    Insert(&root, d, &taller);
}

template<typename T>
Node<T> *BSTree<T>::CopyHelp(const Node<T> *r) {
    if (r == nullptr)return nullptr;
    auto *left = CopyHelp(r->left);
    auto *right = CopyHelp(r->right);
    auto *copy = new Node<T>(r->data, left, right);
    copy->EF = r->EF;
    return copy;
}

template<typename T>
BSTree<T>::BSTree(const BSTree<T> &source) {
    root = CopyHelp(source.root);
}

template<typename T>
BSTree<T> &BSTree<T>::operator=(const BSTree<T> &source) {
    if (&source != this) {
        root = CopyHelp(source.root);
    }
    return *this;
}


//中序遍历判断是否是二叉排序树,排序树中序为递增
template<typename T>
bool isBSTree(Node<T> *root) {
    stack<Node<T> *> st;
    //INT_MIN最小负整数 -2^31 climits 包下
    long long prev = (long long) INT_MIN - 1;

    while (root || !st.empty()) {
        if (root) {
            st.push(root);
            root = root->left;
        } else {
            root = st.top();
            st.pop();
            if (root->data <= prev)return false;
            prev = root->data;
            root = root->right;
        }
    }
    return true;
}

//方法二 递归判断
template<typename T>
bool help(Node<T> *root, long long lower, long long upper) {
    if (root == nullptr)return true;
    if (root->data <= lower || root->data >= upper)return false;
    return help(root->left, lower, root->data) && help(root->right, root->data, upper);
}

template<typename T>
bool isBSTTreeRecursive(Node<T> *root) {
    return help(root, LONG_MIN, LONG_MAX);
}

template<typename T>
void DisplayWithTreeShape(const Node<T> *r, int level) {
    if (!r)return;
    DisplayWithTreeShape(r->right, level + 1);
    cout << endl;
    for (int i = 0; i < level; ++i) {
        cout << "     ";
    }
    cout << r->data;

    DisplayWithTreeShape(r->left, level + 1);
}


int main() {
    BSTree<int> bt;
    for (int i = 1; i < 11; ++i) {
        bt.BSTInsert(i);
    }
    bt.PrintBSTree();
    cout << endl;
    cout << endl;
    cout << endl;
    BSTree<int> copy = bt;
    copy.PrintBSTree();
    return 0;
}