大师兄的数据结构学习笔记(六）:树的应用

一、二叉搜索树(Binary Search Tree)

1. 什么是二叉搜索树

一棵二叉树，可以为空。
如果不为空，满足以下性质：

1) 非空左子树的所有键值小于其根结点的键值。
2) 非空右子树的所有键值大于其根结点的键值。
3) 左、右子树都是二叉搜索树。

2. 特殊函数：

函数	描述
BSDNode Find(ElementType X,BSTree BST)	从二叉搜索树BST中查找元素X,返回器所在结点的地址。
BSDNode FindMin(BSTree BST)	从二叉搜索树BST中查找并返回最小元素所在结点的地址。
BSDNode FindMax(BSTree BST)	从二叉搜索树BST中查找并返回最大元素所在结点的地址。
BSTree Insert(ElementType X,BSTree BST)	插入结点
BSTree Delete(ElementType X,BSTree BST)	删除结点

3. 实现二叉搜索树

#ifndef BINARYSEARCHTREE
#define BINARYSEARCHTREE
using namespace std;

template<typename T>
class BSTNode
{
    ////结点结构
public:
    T _key;             //key
    BSTNode* _lchild;   //leftchild
    BSTNode* _rchild;   //rightchild
    BSTNode* _parent;   //parent
    
    //构造函数
    BSTNode(
        T key,
        BSTNode* lchild,
        BSTNode* rchild,
        BSTNode* parent
        ) :
        _key(key),
        _lchild(lchild),
        _rchild(rchild),
        _parent(parent){};
};

template<typename T>
class BSTree
{
public:
    BSTree() :_Root(NULL) {};                       //构造函数
    ~BSTree() {};                                   //析构函数
    BSTNode<T> Find(BSTNode<T>* &tree,T key) const; //查找结点
    BSTNode<T> FindMin(BSTNode<T>* &tree);          //查找最小结点
    BSTNode<T> FindMax(BSTNode<T>* &tree);          //查找最大结点
    void Insert(BSTNode<T>* &tree, BSTNode<T>* z);  //插入结点
    BSTNode<T> Delete(BSTNode<T>* &tree, T key);    //删除结点
private:
    BSTNode<T>* _Root;                              //根节点
};
#endif

#include "BinarySearchTree.h"
using namespace std;

template<typename T>
// 查找结点
BSTNode<T> BSTree<T>::Find(BSTNode<T>* &tree, T key) const
{
    BSTNode<T>* temp = tree;
    
    while (temp != nullptr)
    {
        if (temp->_key == key)
            return temp;
        else if (temp->_key > key)
            temp = temp->_lchild;
        else
            temp = temp->_rchild;
    }
}

template<typename T>
// 查找最小结点
BSTNode<T> BSTree<T>::FindMin(BSTNode<T>* &tree)
{
    BSTNode<T>* temp = tree;
    while (temp->_lchild)
    {
        temp = temp->_lchild;
    }
    return temp;
}

template<typename T>
// 查找最大结点
BSTNode<T> BSTree<T>::FindMax(BSTNode<T>* &tree)
{
    BSTNode<T>* temp = tree;
    while (temp->_rchild)
    {
        temp = temp->_rchild;
    }
    return temp;
}

template<typename T>
// 插入结点
void BSTree<T>::Insert(BSTNode<T>* &tree, BSTNode<T>* z)
{
    BSTNode<T>* parent = nullptr;
    BSTNode<T>* temp = tree;

    // 寻找插入点
    while (temp != nullptr)
    {
        parent = temp;
        if (z->_key > temp->_key)
            temp = temp->_rchild;
        else
            temp = temp->_left;
    }
    z->_parent = parent;
}

template<typename T>
//删除结点
BSTNode<T> BSTree<T>::Delete(BSTNode<T>* &tree, T key)
{
    BSTNode<T> temp = nullptr;
    if (!tree)
        printf("未找到要删除的元素");
    else if (key < tree->_key)
        tree->_lchild = Delete(tree->_lchild,key); // 左子树递归删除
    else if (key > tree->_key)
        tree->_rchild = Delete(tree->_rchild,key); // 右子树递归删除
    else  // 如果找到了元素
        if (tree->_lchild && tree->_rchild) // 包含左右两个结点
        {
            temp = FindMin(tree->_rchild); // 找到右子树中最小的元素用来填充结点
            tree->_key = temp->_key;
            tree->_rchild = Delete(tree->_rchild, tree->_key);
        }
        else // 只有一个结点或无子节点
        {
            temp = tree;
            if (!tree->_lchild)
                tree = tree->_rchild;
            else if (!tree->_rchild)
                tree = tree->_lchild;
        }
    return tree;
}

二、平衡二叉树 AVL树(Balance Binary Tree)

由于二叉查找树的查找效率取决于二叉排序树的形态，而构造一棵形态均匀的二叉查找树与节点插入的次序有关，而插入的顺序往往是不可预测的。
二叉查找树形态越均匀，查找效率越高，介于 $O(logN)和O(n)之间$ 。
所以需要找到一种动态平衡的方法，对于任意的插入序列都能构造一棵形态均匀、平衡的二叉查找树,即平衡二叉树。

1. 关于平衡二叉树

任一结点左右子树高度差的绝对值不超过1 $|BF(T)|\leqslant1$ 。
根节点的左子树和右子树都是一颗平衡二叉树。

2. 关于平衡因子

每个结点的平衡因子是该结点的左子树与右子树的深度之差。

3. 平衡二叉树的调整

在向平衡二叉树插入结点时，需要检查插入后是否破坏了树的平衡性，如破坏则需要对树进行调整，主要有以下四种调整方式：

1) RR型

新插入的结点是插在结点A的右子树的右子树上，需要RR旋转（右单旋）。

2) LL型

新插入的结点是插在结点A的左子树的左子树上，需要LL旋转（左单旋）。

3) LR型

新插入的结点是插在结点A的左子树的右子树上，需要LR旋转(先向左，再向右)。

4) RL型

新插入的结点是插在结点A的右子树的左子树上，需要RL旋转(先向右，再向左)。

4. 实现平衡二叉树

#ifndef AVLTREE
#define AVLTREE
using namespace std;

template<class DataType>
//结点结构
struct Node
{
    DataType data;
    struct Node* lChild;
    struct Node* rChild;
    int balanceFactor; //平衡因子
};

template<class DataType>
class AVLTree
{
public:
    AVLTree(Node<DataType>*& T);                                                        //构造函数
    ~AVLTree() { destroy(root); };                                                      //析构函数
    void insert(Node < DataType>*& T, Node < DataType>* S);                             // 插入结点
    void createBalanceBiTreeFromArray(Node<DataType>*& T, DataType A[], int n);         //创建AVL
    void destroy(Node < DataType>*& T);                                                 // 销毁二叉树
    void deleteNode(Node < DataType>*& T, DataType x);                                  // 删除结点
    void LLAdjust(Node < DataType>*& T, Node < DataType>*& p, Node < DataType>*& f);    //LL调整
    void RRAdjust(Node < DataType>*& T, Node < DataType>*& p, Node < DataType>*& f);    //RR调整
    void LRAdjust(Node < DataType>*& T, Node < DataType>*& p, Node < DataType>*& f);    //LR调整
    void RLAdjust(Node < DataType>*& T, Node < DataType>*& p, Node < DataType>*& f);    //RL调整
    void AllAdjust(Node<DataType>*& T);                                                 // 调整AVL
    void nodeFactorIsTwoFather(Node<DataType>*& T, Node<DataType>*& f);                 //获得平衡因子为2或-2的节点的父节点
    void nodeFactorIsTwo(Node<DataType>*& T, Node<DataType>*& p);                       //获得平衡因子为2或-2的节点
    int getNodeFactor(Node < DataType>* T);                                             //求结点的平衡因子
    void factorForTree(Node<DataType>*& T);                                             //求树的平衡因子
    int BiTreeDepth(Node < DataType>* T);                                               //求树的高度
    Node<DataType>* getElementFatherPointer(Node <DataType>*& T, Node <DataType>*& f, DataType x); //获取父指针
    void preOrderTraverse(Node<DataType>* T, int level);                                //先序遍历输出
    void search(Node<DataType>*& T, Node<DataType>*& p, DataType x);                    // 查找元素
private:
    Node<DataType>* root;                                                               //根结点
};
#endif

#include <iostream>
#include "AVLTree.h"
using namespace std;

template< class DataType>
AVLTree<DataType>::AVLTree(Node<DataType>*& T)
{
    T = NULL;
}

template<class DataType>
//插入结点
void AVLTree<DataType>::insert(Node < DataType>*& T, Node < DataType>* S)
{
    if (T == nullptr)
    {
        T = S;
    }
    else if (S->data < T->data)
    {
        insert(T->lChild, S);
    }
    else
    {
        insert(T->rChild, S);
    }
}

template<class DataType>
//创建AVL
void AVLTree<DataType>::createBalanceBiTreeFromArray(Node<DataType>*& T, DataType A[], int n)
{
    Node<DataType>* S, * p;
    int i = 1;
    T = new Node<DataType>;
    T->balanceFactor = 0;
    T->lChild = nullptr;
    T->rChild = nullptr;
    p = T;
    T->data = A[0];
    n = n - 1;
    while (n)
    {
        S = new Node<DataType>;
        S->data = A[i];
        S->balanceFactor = 0;
        S->lChild = nullptr;
        S->rChild = nullptr;
        insert(p, S);
        AllAdjust(T);
        p = T;
        i++;
        n--;
    }
}

template<class DataType>
//销毁AVLTree
void AVLTree<DataType>::destroy(Node < DataType>*& T)
{
    if (T)
    {
        destroy(T->lChild);
        destroy(T->rChild);
        delete T;
    }
}

template<class DataType>
// 删除结点
void AVLTree<DataType>::deleteNode(Node < DataType>*& T, DataType x)
{
    Node <DataType>* f, * p = nullptr;
    search(T, p, x); // 查找结点
    getElementFatherPointer(T, f, x);
    if (p == nullptr)
    {
        // 如果没找到结点
        cout << "未找到结点." << endl;
        return;
    }
    if (p->lChild == nullptr && p->rChild == nullptr)
    {
        //如果为叶节点
        if (T == p)
        {
            // 如果根节点 
            delete p;
            T = nullptr;
        }
        else 
        {
            // 如果是非根节点
            if (f->lChild == p)
            {
                delete p;
                f->lChild = nullptr;
            }
            else {
                delete p;
                f->rChild = nullptr;
            }
        }
    }
    else if ((p->lChild == nullptr && p->rChild != nullptr) || (p->lChild != nullptr && p->rChild == nullptr))
    {
        // 如果有一边为空
        if (T == p)
        {
            if (T->lChild == nullptr&&T->rChild!=nullptr)
            {
                T = p->rChild;
                delete p;
            }
            if (T->rChild == nullptr && T->lChild != nullptr)
            {
                T = p->lChild;
                delete p;
            }
        }
        else
        {
            if (p->lChild != nullptr)
            {
                if (f->lChild == p)
                {
                    f->lChild = p->lChild;
                }
                else
                {
                    f->rChild = p->lChild;
                }
            }
            if (p->rChild != nullptr)
            {
                if (f->lChild == p)
                {
                    f->lChild = p->rChild;
                }
                else
                {
                    f->rChild = p->rChild;
                }
            }
        }
    }
    else {
        // 如果有两个子树
        Node <DataType>* f, * next, * prior;
        if (p ->balanceFactor==1)
        {
            //平衡因子为1
            prior = getElementPriorPointer(p->lChild);
            if (prior->lChild != nullptr && prior->rChild == nullptr)
            {
                p->data = prior->data;
                prior->data = prior->lChild->data;
                delete prior->lChild;
                prior->lChild = nullptr;
            }
            if (prior->lChild == nullptr && prior->rChild == nullptr)
            {
                getElementFatherPointer(T, f, prior->data);
                p->data = prior->data;
                delete prior;
                f->rChild = nullptr;
            }
        }
        else if (p->balanceFactor == -1)
        {
            //平衡因子为-1
            next = getElementNextPointer(p->rChild);                
            cout << next->data;
            int level = 1;
            if (next->rChild != nullptr && next->lChild == nullptr)      
            {
                p->data = next->data;
                next->data = next->rChild->data;
                delete next->rChild;
                next->rChild = nullptr;
            }
            else if (next->rChild == nullptr && next->lChild == nullptr)       
            {
                getElementFatherPointer(T, f, next->data);    
                p->data = next->data;
                delete next;
                f->lChild = nullptr;
            }
        }
        else if (p->balanceFactor == 0)
        {
            //平衡因子为0
            prior = getElementPriorPointer(p->lChild);              
            if (prior->lChild != nullptr && prior->rChild == nullptr)     
            {
                p->data = prior->data;
                prior->data = prior->lChild->data;
                delete prior->lChild;
                prior->lChild = nullptr;
            }
            if (prior->lChild == nullptr && prior->rChild == nullptr)      
            {
                getElementFatherPointer(T, f, prior->data);    
                p->data = prior->data;
                delete prior;
                if (p == f)                                      
                    f->lChild = nullptr;
                else
                    f->rChild = nullptr;

            }

        }
    }

    if (T != nullptr)
    {
        // 调整AVL
        AllAdjust(T);
    }
}

template<class DataType>
//LL调整
void AVLTree<DataType>::LLAdjust(Node < DataType>*& T, Node < DataType>*& p, Node < DataType>*& f)
{
    Node<DataType>* r;
    cout << "LL adjust" << endl;
    if (T == p)
    {
        T = p->lChild; //将P的左孩子提升为新的根节点
        r = T->rChild;
        T->rChild = p;
        p->lChild = r;
    }
    else
    {
        if (f->lChild == p) //f的左子树是p
        {
            f->lChild = p->lChild;
            r = f->lChild->rChild;
            f->lChild->rChild = p;
            p->lChild = r;
        }
        if (f->rChild == p) //f的右子树是p
        {
            f->rChild = p->lChild;
            r = f->rChild->rChild;
            f->rChild->rChild = p;
            p->rChild = r;
        }
    }
}

template<class DataType>
//RR调整
void AVLTree<DataType>::RRAdjust(Node < DataType>*& T, Node < DataType>*& p, Node < DataType>*& f)
{
    Node<DataType>* l;
    cout << "RR adjust" << endl;
    if (T == p)
    {
        T = p->rChild;
        l = T->lChild;
        T->lChild = p;
        p->rChild = l;
    }
    else
    {
        if (f->rChild == p)
        {
            f->rChild = p->rChild;
            l = f->rChild->lChild;
            f->rChild->lChild = p;
            p->rChild = l;
        }
        if (f->lChild == p)
        {
            f->lChild = p->rChild;
            l = f->lChild->lChild;
            f->lChild->lChild = p;
            p->rChild = l;
        }
    }
}

template<class DataType>
//LR调整
void AVLTree<DataType>::LRAdjust(Node < DataType>*& T, Node < DataType>*& p, Node < DataType>*& f)
{
    Node<DataType>* l, * r;
    cout << "LR adjust" << endl;
    if (T == p)
    {
        T = p->lChild->rChild;
        r = T->rChild;
        l = T->rChild;
        T->rChild = p;
        T->lChild = p->lChild;
        T->lChild->rChild = l;
        T->rChild->lChild = r;
    }
    else 
    {
        if (f->lChild == p)
        {
            f->lChild = p->lChild->rChild;
            l = f->lChild->lChild;
            r = f->lChild->rChild;
            f->lChild->lChild = p->lChild;
            f->rChild->rChild = p;
            f->lChild->lChild->rChild = l;
            p->lChild->rChild->lChild = r;
        }

        if (f->rChild == p)
        {
            f->rChild = p->lChild->rChild;
            l = f->rChild->lChild;
            r = f->rChild->rChild;
            f->rChild->rChild = p;
            f->rChild->lChild = p->lChild;
            f->rChild->lChild->rChild = l;
            f->rChild->rChild->lChild = r;
        }
    }
}

template<class DataType>
//RL调整
void AVLTree<DataType>::RLAdjust(Node < DataType>*& T, Node < DataType>*& p, Node < DataType>*& f)
{
    Node<DataType>* l, * r;
    cout << "RL adjust" << endl;
    if (T == p)
    {
        T = p->rChild->lChild;
        l = T->lChild;
        r = T->rChild;
        T->lChild = p;
        T->rChild = p->rChild;
        T->lChild->rChild = l;
        T->rChild->lChild = r;
    }
    else
    {
        if (f->rChild == p)
        {
            f->rChild = p->rChild->lChild;
            l = f->rChild->lChild;
            r = f->rChild->rChild;
            f->rChild->lChild = p;
            f->rChild->rChild = p->rChild;
            f->rChild->lChild->rChild = l;
            f->rChild->rChild->lChild = r;
        }

        if (f->lChild == p)
        {
            f->lChild = p->rChild->lChild;
            l = f->lChild->lChild;
            r = f->lChild->rChild;
            f->lChild->lChild = p;
            f->lChild->rChild = p->rChild;
            f->lChild->lChild->rChild = l;
            f->lChild->rChild->lChild = r;
        }
    }
}

template<class DataType>
void AVLTree<DataType>::AllAdjust(Node < DataType>*& T)
{
    //调整AVL
    Node<DataType>* f = nullptr, * p = nullptr;
    factorForTree(T);
    nodeFactorIsTwoFather(T, f);
    nodeFactorIsTwo(T, p);
    while (p)
    {
        factorForTree(T);
        if (p->balanceFactor == 2 && (p->lChild->balanceFactor == 1 || p->lChild->balanceFactor == 0))
        {
            LLAdjust(T, p, f);
            factorForTree(T);
        }
        else if (p->balanceFactor == 2 && p->lChild->balanceFactor == -1)
        {
            LRAdjust(T, p, f);
            factorForTree(T);
        }
        else if (p->balanceFactor == -2 && p->rChild->balanceFactor == 1)
        {
            RLAdjust(T, p, f);
            factorForTree(T);
        }
        else if (p->balanceFactor == -2 && (p->rChild->balanceFactor == -1 || p->rChild->balanceFactor == 0))
        {
            RRAdjust(T, p, f);
        }
        f = nullptr;
        p = nullptr;
        nodeFactorIsTwoFather(T, f);
        nodeFactorIsTwo(T, p);
    }
}

template<class DataType>
int AVLTree<DataType>::BiTreeDepth(Node<DataType>* T)
{
    //求树的高度
    int m, n;
    if (T == nullptr)
    {
        return 0;
    }
    else {
        m = BiTreeDepth(T->lChild);
        n = BiTreeDepth(T->rChild);
        if (m > n)
        {
            return m + 1;
        }
        else {
            return n + 1;
        }
    }
}

template<class DataType>
int AVLTree<DataType>::getNodeFactor(Node < DataType>* T)
{
    //求结点平衡因子
    int m = 0, n = 0;
    if (T)
    {
        m = BiTreeDepth(T->lChild);
        n = BiTreeDepth(T->rChild);
    }
    return m - n;
}

template<class DataType>
void AVLTree<DataType>::factorForTree(Node<DataType>*& T)
{
    //求树的平衡因子
    if (T)
    {
        T->balanceFactor = getNodeFactor(T);
        factorForTree(T->lChild);
        factorForTree(T->rChild);
    }
}

template<class DataType>
void AVLTree<DataType>::nodeFactorIsTwo(Node<DataType>*& T, Node<DataType>*& p)
{
    //获得平衡因子为2或-2的节点
    if (T)
    {
        if (T->balanceFactor == 2 || T->balanceFactor == -2)
        {
            p = T;
        }
        nodeFactorIsTwo(T->lChild, p);
        nodeFactorIsTwo(T->rChild, p);
    }
}

template<class DataType>
void AVLTree<DataType>::nodeFactorIsTwoFather(Node<DataType>*& T, Node<DataType>*& f)
{
    //获得平衡因子为2或-2的节点的父节点
    if (T)
    {
        if (T->lChild != nullptr)
        {
            if (T->lChild->balanceFactor == 2 || T->lChild->balanceFactor == -2)
            {
                f = T;
            }
        }
        if (T->rChild != nullptr)
        {
            if (T->rChild->balanceFactor == 2 || T->rChild->balanceFactor == -2)
            {
                f = T;
            }
        }
        nodeFactorIsTwoFather(T->lChild, f);
        nodeFactorIsTwoFather(T->rChild, f);
    }
}

template<class DataType>
Node<DataType>* AVLTree<DataType>::getElementFatherPointer(Node <DataType>*& T, Node <DataType>*& f, DataType x)
{
    //获取父指针
    if (T)
    {
        if (T->lChild != nullptr)
        {
            if (T->lChild->data == x)
                f = T;
        }
        if (T->rChild != nullptr)
        {
            if (T->rChild->data == x)
                f = T;
        }
        getElementFatherPointer(T->lChild, f, x);
        getElementFatherPointer(T->rChild, f, x);
    }
}

template<class DataType>
void AVLTree<DataType>::search(Node<DataType>*& T, Node<DataType>*& p, DataType x)
{
    // 查找元素
    if (T)
    {
        if (T->data == x)
        {
            p = T;
        }
        search(T->lChild, p, x);
        search(T->rChild, p, x);
    }

}

template<class DataType>
void AVLTree<DataType>::preOrderTraverse(Node<DataType>* T, int level)
{
    //先序遍历输出
    if (T)
    {
        cout << "先序遍历" << "(" << T->data << "," << level << ")" << " ";
        preOrderTraverse(T->lChild, level + 1);
        preOrderTraverse(T->rChild, level + 1);
    }
}