AI 助理
备案控制台
开发者社区 云计算 文章 正文

ACM模板——平衡二叉树（插入、删除、创建、遍历、判断完全二叉树）

2022-05-18 307
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ACM模板——平衡二叉树（插入、删除、创建、遍历、判断完全二叉树）

理论模板

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a)
#define INF 3f3f3f3f
using namespace std;
typedef long long ll;
// 平衡二叉树结点
template <typename T>
struct AvlNode
{
    T data;
    int height; // 结点所在高度
    AvlNode<T> *left;
    AvlNode<T> *right;
    AvlNode<T>(const T theData):data(theData),left(NULL),right(NULL),height(0){}
};
// AvlTree
template <typename T>
class AvlTree
{
public:
    AvlNode<T> *root;
    AvlTree<T>():root(NULL){}
    ~AvlTree<T>(){}
    void Insert(AvlNode<T> *&t,T x); // 插入结点
    bool Delete(AvlNode<T> *&t,T x); // 删除结点
    bool Contains(AvlNode<T> *t,const T x) const; // 查找是否存在给定值的结点
    void InorderTraversal(AvlNode<T> *t); // 中序遍历
    void PreorderTraversal(AvlNode<T> *t); // 前序遍历
    AvlNode<T> *FindMin(AvlNode<T> *t) const; // 最小值结点
    AvlNode<T> *FindMax(AvlNode<T> *t) const; // 最大值结点
private:
    int GetHeight(AvlNode<T> *t);  // 求树的高度
    AvlNode<T> *LL(AvlNode<T> *t); // 单旋转 左
    AvlNode<T> *RR(AvlNode<T> *t); // 单旋转 右
    AvlNode<T> *LR(AvlNode<T> *t); // 双旋转 右左
    AvlNode<T> *RL(AvlNode<T> *t); // 双旋转 左右
};
// 查找最大结点
template <typename T>
AvlNode<T> *AvlTree<T>::FindMax(AvlNode<T> *t) const
{
    if(t==NULL)
        return NULL;
    if(t->right==NULL)
        return t;
    return FindMax(t->right);
}
// 查找最小结点
template <typename T>
AvlNode<T> *AvlTree<T>::FindMin(AvlNode<T> *t) const
{
    if(t==NULL)
        return NULL;
    if(t->left==NULL)
        return t;
    return FindMin(t->left);
}
// 获取高度
template <typename T>
int AvlTree<T>::GetHeight(AvlNode<T> *t)
{
    if(t==NULL)
        return -1;
    return t->height;
}
// 单旋转
// 左左插入导致不平衡
template <typename T>
AvlNode<T> *AvlTree<T>::LL(AvlNode<T> *t)
{
    AvlNode<T> *q=t->left;
    t->left=q->right;
    q->right=t;
    t->height=max(GetHeight(t->left),GetHeight(t->right))+1;
    q->height=max(GetHeight(q->left),GetHeight(q->right))+1;
    // 注意1：并不是没有连结操作，因为 q 是一个新的 AvlNode<T>，所以在这里返回的时候就连结上这个新修改好的地址
    // 注意2：因为地址改变了，它儿子结点原来连的旧地址被更新后会不会断了？不会，因为上面在操作这个更新了
    // 注意3：因为地址改变了，新的根结点 q 如何连结原来它的父亲结点？把以上整个更新完后的最新根节点 q，把它们看为一个整体(结点~相当于叶子结点)，返回的时候就在做这个覆盖旧的根 t 结点的地址
    // 注意4：如果注意2、3还没明白的话看：本博客【基础知识 - 指针篇 - 案例二】
    return q;
}
// 单旋转
// 右右插入导致不平衡
template <typename T>
AvlNode<T> *AvlTree<T>::RR(AvlNode<T> *t)
{
    AvlNode<T> *q=t->right;
    t->right=q->left;
    q->left=t;
    t->height=max(GetHeight(t->left),GetHeight(t->right))+1;
    q->height=max(GetHeight(q->left),GetHeight(q->right))+1;
    return q;
}
// 双旋转
// 插入点位于 t 的左儿子的右子树
template <typename T>
AvlNode<T> *AvlTree<T>::LR(AvlNode<T> *t)
{
    // 双旋转可以通过两次单旋转实现
    // 对 t 的左结点进行RR旋转，再对根节点进行LL旋转
    // 记忆法：LR --> RR+LL // 先RR再LL，类似Stack - FILO
    RR(t->left);
    return LL(t);
}
// 双旋转
// 插入点位于 t 的右儿子的左子树
template <typename T>
AvlNode<T> *AvlTree<T>::RL(AvlNode<T> *t)
{
    LL(t->right);
    return RR(t);
}
// 插入
template <typename T>
void AvlTree<T>::Insert(AvlNode<T> *&t,T x)
{
    if(t==NULL)
    {
        t=new AvlNode<T>(x); // 新生成的自动连结父亲
    }
    else if(x<t->data)
    {
        Insert(t->left,x);
        // 判断平衡情况
        if(GetHeight(t->left)-GetHeight(t->right)>1)
        {
            // 分两种情况：左左 or 左右
            if(x<t->left->data) // 左左
                t=LL(t);
            else                // 左右
                t=LR(t);
        }
    }
    else if(x>t->data)
    {
        Insert(t->right,x);
        if(GetHeight(t->right)-GetHeight(t->left)>1)
        {
            if(x>t->right->data)
                t=RR(t);
            else
                t=RL(t);
        }
    }
    else
        ; // 数据重复，看情况处理
    // 不能把以下此代码移动到 t==NULL 里，因为其他 (else if)'s t 还需要更新
    t->height=max(GetHeight(t->left),GetHeight(t->right))+1;
}
// 删除
template <typename T>
bool AvlTree<T>::Delete(AvlNode<T> *&t,T x)
{
    // t 为空，未找到要删除的结点
    if(t==NULL)
        return false;
    // 找到要删除的结点
    else if(t->data==x)
    {
        // 左右子树都非空
        if(t->left!=NULL && t->right!=NULL)
        {
            // 在高度更大的那个子树上进行删除操作
            // 左子树高度更大，则删除左子树中data最大的结点，将其赋给根节点
            if(GetHeight(t->left)>GetHeight(t->right))
            {
                t->data=FindMax(t->left)->data;
                Delete(t->left,t->data);
            }
            else // 右子树高度更大，则删除右子树中data最小的结点，将其赋给根节点
            {
                t->data=FindMin(t->right)->data;
                Delete(t->right,t->data);
            }
        }
        else
        {
            // 左右子树右一个不为空（或左右子树都为空），直接用需要删除的结点的子结点替换即可
            AvlNode<T> *old=t;
            // 当左右子树右一个不为空，则 t 赋值为不空的子结点
            // 当左右子树都为空，则随意
            t=t->left?t->left:t->right;
            delete old;
        }
    }
    // 要删除的结点在左子树上
    else if(x<t->data)
    {
        // 递归删除左子树上的结点
        Delete(t->left,x);
        // 判断是否仍然满足平衡条件
        if(GetHeight(t->right)-GetHeight(t->left)>1)
        {
            if(GetHeight(t->right->left)>GetHeight(t->right->right))
            {
                t=RL(t);
            }
            else
            {
                t=RR(t);
            }
        }
        else // 满足平衡条件，调整高度信息
        {
            t->height=max(GetHeight(t->left),GetHeight(t->right))+1;
        }
    }
    // 要删除的结点在右子树上
    else
    {
        Delete(t->right,x);
        if(GetHeight(t->left)-GetHeight(t->right)>1)
        {
            if(GetHeight(t->left->right)>GetHeight(t->left->left))
            {
                t=LR(t);
            }
            else
            {
                t=LL(t);
            }
        }
        else // 满足平衡条件，调整高度信息
        {
            t->height=max(GetHeight(t->left),GetHeight(t->right))+1;
        }
    }
    return true;
}
// 查找结点
template <typename T>
bool AvlTree<T>::Contains(AvlNode<T> *t,const T x) const
{
    if(t==NULL)
        return false;
    if(x<t->data)
        return Contains(t->left,x);
    else if(x>t->data)
        return Contains(t->right,x);
    else
        return true;
}
// 中序遍历
template <typename T>
void AvlTree<T>::InorderTraversal(AvlNode<T> *t)
{
    if(t)
    {
        InorderTraversal(t->left);
        printf("%d ",t->data);
        InorderTraversal(t->right);
    }
}
// 前序遍历
template <typename T>
void AvlTree<T>::PreorderTraversal(AvlNode<T> *t)
{
    if(t)
    {
        printf("%d ",t->data);
        PreorderTraversal(t->left);
        PreorderTraversal(t->right);
    }
}
// 显示中序+前序遍历结果
template <typename T>
void showTraversal(AvlTree<T> &tree)
{
    printf("中序遍历:");
    tree.InorderTraversal(tree.root);
    printf("\n前序遍历:");
    tree.PreorderTraversal(tree.root);
}
// 测试数据：18 14 20 12 16 1 -1
int main()
{
    AvlTree<int> tree;
    int val,tmp;
    printf("请输入整数建立二叉树(-1 end):\n");
    while(~scanf("%d",&val))
    {
        if(val==-1)
            break;
        tree.Insert(tree.root,val);
    }
    showTraversal(tree);
    printf("\n请输入要查找的结点: ");
    scanf("%d",&tmp);
    if(tree.Contains(tree.root,tmp))
        printf("已找到\n");
    else
        printf("不存在\n");
    printf("请输入要删除的结点: ");
    scanf("%d",&tmp);
    tree.Delete(tree.root,tmp);
    showTraversal(tree);
    return 0;
}

image.png


ACM 模板

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;
struct node
{
    int val;
    node *left,*right; // default NULL
};
vector<int> v;
int after, isComp;
node *LL(node *tree)
{
    node *tmp=tree->right;
    tree->right=tmp->left;
    tmp->left=tree;
    return tmp;
}
node *RR(node *tree)
{
    node *tmp=tree->left;
    tree->left=tmp->right;
    tmp->right=tree;
    return tmp;
}
node *LR(node *tree)
{
    tree->left=LL(tree->left);
    tree=RR(tree);
    return tree;
}
node *RL(node *tree)
{
    tree->right=RR(tree->right);
    tree=LL(tree);
    return tree;
}
int getHeight(node *tree)
{
    if(tree==NULL) return 0;
    int l=getHeight(tree->left), r=getHeight(tree->right);
    return l>r ? l+1 : r+1;
}
node *insert(node *tree, int val)
{
    if(tree==NULL)
    {
        tree=new node();
        tree->val=val;
//        tree->left=tree->right=NULL;
        return tree;
    }
    if(tree->val>val)
    {
        tree->left=insert(tree->left,val);
        int l=getHeight(tree->left), r=getHeight(tree->right);
        if(l-r>=2)
            if(tree->left->val > val) tree=RR(tree);
            else tree=LR(tree);
    }
    else
    {
        tree->right=insert(tree->right,val);
        int l=getHeight(tree->left), r=getHeight(tree->right);
        if(r-l>=2)
            if(tree->right->val < val) tree=LL(tree);
            else tree=RL(tree);
    }
    return tree;
}
// 层序遍历 + 判断是否完全二叉树
void bfs(node *tree)
{
    v.clear();
    queue<node*> q;
    q.push(tree);
    after=0, isComp=1;
    while(!q.empty())
    {
        tree=q.front(); q.pop();
        v.push_back(tree->val);
        if(tree->left!=NULL)
        {
            if(after) isComp=0;
            q.push(tree->left);
        }
        else after=1;
        if(tree->right!=NULL)
        {
            if(after) isComp=0;
            q.push(tree->right);
        }
        else after=1;
    }
}
int main()
{
    int n,val;
    while(~scanf("%d",&n))
    {
        node *tree=NULL;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&val);
            tree=insert(tree,val);
        }
        bfs(tree);
        for(int i=0;i<v.size()-1;i++) printf("%d ",v[i]);
        printf("%d\n",v[v.size()-1]);
        puts(isComp?"YES":"NO");
    }
    return 0;
}
Lux_Sun
目录
相关文章
戊子仲秋
【面试必刷TOP101】删除链表的倒数第n个节点 & 两个链表的第一个公共结点
【面试必刷TOP101】删除链表的倒数第n个节点 & 两个链表的第一个公共结点
戊子仲秋
49 0
qiuqiushuibx
代码随想录Day18 LeetCode235 二叉搜索树的公共祖先 T701二叉搜索树中的插入操作 T140 删除二叉搜索树中的公共节点
代码随想录Day18 LeetCode235 二叉搜索树的公共祖先 T701二叉搜索树中的插入操作 T140 删除二叉搜索树中的公共节点
qiuqiushuibx
31 0
wjq++
|
5月前
二叉树的创建、插入和删除
二叉树的创建、插入和删除
wjq++
28 1
sky_qiyi
|
5月前
|
算法
数据结构和算法学习记录——认识二叉搜索树及二叉搜索树的查找操作（递归以及迭代实现-查找操作、查找最大和最小元素）
数据结构和算法学习记录——认识二叉搜索树及二叉搜索树的查找操作（递归以及迭代实现-查找操作、查找最大和最小元素）
sky_qiyi
52 0
luming.02
|
6月前
|
存储
数据结构：图文详解双向链表的各种操作（头插法，尾插法，任意位置插入，查询节点，删除节点，求链表的长度... ...）
数据结构：图文详解双向链表的各种操作（头插法，尾插法，任意位置插入，查询节点，删除节点，求链表的长度... ...）
luming.02
821 0
刘牌
|
存储 算法
二叉树的创建和遍历
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分
刘牌
91 0
.Ashy.
链表学习(链表的创建，插入，删除，查找，遍历)
链表学习(链表的创建，插入，删除，查找，遍历)
.Ashy.
126 0
存在morning
剑指offer_链表---删除链表中重复的结点
剑指offer_链表---删除链表中重复的结点
存在morning
46 0
pandaconda
剑指offer 17. 删除链表中重复的节点
剑指offer 17. 删除链表中重复的节点
pandaconda
57 0
HannYang
|
机器学习/深度学习 C++ 容器
二叉树创建和遍历（C++实现）
树（Tree）是n(n≥0)个节点的有限集。在任意一棵树中有且仅有一个特定的称为根（Root）的节点；当n＞1时，其余节点可分m(m＞0)为个互不相交的有限集T1,T2,...,Tm；其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。 二叉树（Binary Tree）是一种特殊的有序树型结构，所有节点最多只有2棵子树。
HannYang
654 0