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

大师兄的数据结构学习笔记(五）:二叉树
大师兄的数据结构学习笔记(七）:堆

一、二叉搜索树(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)

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

1. 关于平衡二叉树

• 任一结点左右子树高度差的绝对值不超过1。

• 根节点的左子树和右子树都是一颗平衡二叉树。

  
  

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