C语言数据结构之平衡二叉树（AVL树）实现方法示例

Tallulah ·

更新时间:2024-11-13

· 653 次阅读

本文实例讲述了C语言数据结构之平衡二叉树（AVL树）实现方法。分享给大家供大家参考，具体如下：

AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树。

要维持这个树，必须在插入和删除的时候都检测是否出现破坏树结构的情况。然后立刻进行调整。

看了好久，网上各种各种的AVL树，千奇百怪。

关键是要理解插入的时候旋转的概念。


//
// AvlTree.h
// HelloWorld
// Created by feiyin001 on 17/1/9.
// Copyright (c) 2017年 FableGame. All rights reserved.
//
#ifndef __HelloWorld__AvlTree__
#define __HelloWorld__AvlTree__
#include <iostream>
namespace Fable
{
  int max(int a, int b)
  {
    return a > b? a:b;
  }
  //二叉查找树，对于Comparable,必须实现了><=的比较
  template<typename Comparable>
  class AvlTree
  {
  public:
    //构造函数
    AvlTree(){}
    //复制构造函数
    AvlTree(const AvlTree& rhs)
    {
      root = clone(rhs.root);
    }
    //析构函数
    ~AvlTree()
    {
      makeEmpty(root);
    }
    //复制赋值运算符
    const AvlTree& operator=(const AvlTree& rhs)
    {
      if (this != &rhs)
      {
        makeEmpty(root);//先清除
        root = clone(rhs.root);//再复制
      }
      return *this;
    }
    //查找最小的对象
    const Comparable& findMin()const
    {
      findMin(root);
    }
    //查找最大的对象
    const Comparable& findMax()const
    {
      findMax(root);
    }
    //是否包含了某个对象
    bool contains(const Comparable& x)const
    {
      return contains(x, root);
    }
    //树为空
    bool isEmpty()const
    {
      return root == nullptr;
    }
    //打印整棵树
    void printTree()const
    {
      printTree(root);
    }
    //清空树
    void makeEmpty()
    {
      makeEmpty(root);
    }
    //插入某个对象
    void insert(const Comparable& x)
    {
      insert(x, root);
    }
    //移除某个对象
    void remove(const Comparable& x)
    {
      remove(x, root);
    }
  private:
    struct AvlNode
    {
      Comparable element;
      AvlNode* left;
      AvlNode* right;
      int height;
      AvlNode(const Comparable& theElement, AvlNode* lt, AvlNode* rt, int h = 0)
      :element(theElement), left(lt), right(rt), height(h){}
    };
    typedef AvlNode* AvlNodePtr;
    AvlNodePtr root;//根结点
    //顺时针旋转
    void clockwiseRotate(AvlNodePtr& a)
    {
      AvlNodePtr b = a->left;//左叶子
      a->left = b->right;//a的左叶子变为b的右叶子，b本来的子结点都比a小的。
      b->right = a;//b的右结点指向a，b的高度上升了。
      a->height = max(height(a->left), height(a->right)) + 1;//重新计算a的高度
      b->height = max(height(b->left), a->height) + 1;//重新计算b的高度
      a = b;//a的位置现在是b，当前的根结点
    }
    //逆时针旋转
    void antiClockWiseRotate(AvlNodePtr& a)
    {
      AvlNodePtr b = a->right;//右结点
      a->right = b->left;//a接收b的左结点
      b->left = a;//自己成为b的左结点
      a->height = max(height(a->left), height(a->right)) + 1;//计算高度
      b->height = max(b->height, height(a->right)) + 1;//计算高度
      a = b;//新的根结点
    }
    //对左边结点的双旋转
    void doubleWithLeftChild(AvlNodePtr& k3)
    {
      antiClockWiseRotate(k3->left);//逆时针旋转左结点
      clockwiseRotate(k3);//顺时针旋转自身
    }
    //对右边结点的双旋转
    void doubleWithRightChild(AvlNodePtr& k3)
    {
      clockwiseRotate(k3->right);//顺时针旋转有节点
      antiClockWiseRotate(k3);//逆时针旋转自身
    }
    //插入对象，这里使用了引用
    void insert(const Comparable& x, AvlNodePtr& t)
    {
      if (!t)
      {
        t = new AvlNode(x, nullptr, nullptr);
      }
      else if (x < t->element)
      {
        insert(x, t->left);//比根结点小，插入左边
        if (height(t->left) - height(t->right) == 2)//高度差达到2了
        {
          if (x < t->left->element)//插入左边
          {
            clockwiseRotate(t);//顺时针旋转
          }
          else
          {
            doubleWithLeftChild(t);//双旋转
          }
        }
      }
      else if (x > t->element)
      {
        insert(x, t->right);//比根结点大，插入右边
        if (height(t->right) - height(t->left) == 2)//高度差达到2
        {
          if (t->right->element < x)//插入右边
          {
            antiClockWiseRotate(t);//旋转
          }
          else
          {
            doubleWithRightChild(t);//双旋转
          }
        }
      }
      else
      {
        //相同的
      }
      t->height = max(height(t->left), height(t->right)) + 1;//计算结点的高度
    }
    void removeMin(AvlNodePtr& x, AvlNodePtr& t)const
    {
      if (!t)
      {
        return;//找不到
      }
      if (t->left)
      {
        removeMin(t->left);//使用了递归的方式
      }
      else
      {
        //找到最小的结点了
        x->element = t->element;
        AvlNodePtr oldNode = t;
        t = t->right;
        delete oldNode;//删除原来要删除的结点
      }
      if (t)
      {
        t->height = max(height(t->left), height(t->right)) + 1;//计算结点的高度
        if(height(t->left) - height(t->right) == 2)
        { //如果左儿子高度大于右儿子高度
          if(height(t->left->left) >= height(t->left->right))//并且左儿子的左子树高度大于左儿子的右子树高度
          {
            clockwiseRotate(t); //顺时针旋转
          }
          else
          {
            doubleWithLeftChild(t);//双旋转左子树
          }
        }
        else
        {
          if(height(t->right->right) - height(t->right->left) == 2) //如果右子树大于左子树
          {
            antiClockWiseRotate(t);//逆时针旋转
          }
          else
          {
            doubleWithRright(t);//双旋转右子树
          }
        }
      }
    }
    //删除某个对象，这里必须要引用
    void remove(const Comparable& x, AvlNodePtr& t)const
    {
      if (!t)
      {
        return;//树为空
      }
      else if (x < t->element)
      {
        remove(x, t->left);//比根结点小，去左边查找
      }
      else if (x > t->element)
      {
        remove(x, t->right);//比根结点大，去右边查找
      }
      else if (!t->left && !t->right)//找到结点了，有两个叶子
      {
        removeMin(t, t->right);//这里选择的方法是删除右子树的最小的结点
      }
      else
      {
        AvlNodePtr oldNode = t;
        t = (t->left) ? t->left : t->right;//走到这里，t最多只有一个叶子，将t指向这个叶子
        delete oldNode;//删除原来要删除的结点
      }
      if (t)
      {
        t->height = max(height(t->left), height(t->right)) + 1;//计算结点的高度
        if(height(t->left) - height(t->right) == 2)
        { //如果左儿子高度大于右儿子高度
          if(height(t->left->left) >= height(t->left->right))//并且左儿子的左子树高度大于左儿子的右子树高度
          {
            clockwiseRotate(t); //顺时针旋转
          }
          else
          {
            doubleWithLeftChild(t);//双旋转左子树
          }
        }
        else
        {
          if(height(t->right->right) - height(t->right->left) == 2) //如果右子树大于左子树
          {
            antiClockWiseRotate(t);//逆时针旋转
          }
          else
          {
            doubleWithRright(t);//双旋转右子树
          }
        }
      }
    }
    //左边子树的结点肯定比当前根小的，所以一直往左边寻找
    AvlNodePtr findMin(AvlNodePtr t)const
    {
      if (!t)
      {
        return nullptr;//找不到
      }
      if (!t->left)
      {
        return t;
      }
      return findMin(t->left);//使用了递归的方式
    }
    //右边子树的结点肯定比当前根大，所以一直往右边找
    AvlNodePtr findMax(AvlNodePtr t)const
    {
      if (t)
      {
        while (t->right)//使用了循环的方式
        {
          t = t->right;
        }
      }
      return t;
    }
    //判断是否包含某个对象，因为要使用递归，所以还有一个public版本的
    bool contains(const Comparable& x, AvlNodePtr t)const
    {
      if (!t)
      {
        return false;//空结点了
      }
      else if (x < t->element)
      {
        //根据二叉树的定义，比某个结点小的对象，肯定只能存在与这个结点的左边的子树
        return contains(x, t->left);
      }
      else if (x > t->element)
      {
        //根据二叉树的定义，比某个结点大的对象，肯定只能存在与这个结点的右边的子树
        return contains(x, t->right);
      }
      else
      {
        //相等，就是找到啦。
        return true;
      }
    }
    //清空子树
    void makeEmpty(AvlNodePtr& t)
    {
      if (t)
      {
        makeEmpty(t->left);//清空左边
        makeEmpty(t->right);//清空右边
        delete t;//释放自身
      }
      t = nullptr;//置为空
    }
    //打印子树，这里没有使用复杂的排位，纯属打印
    void printTree(AvlNodePtr t)const
    {
      if (!t)
      {
        return;
      }
      std::cout << t->element << std::endl;//输出自身的对象
      printTree(t->left);//打印左子树
      printTree(t->right);//打印右子树
    }
    AvlNodePtr clone(AvlNodePtr t)const
    {
      if (!t)
      {
        return nullptr;
      }
      return new AvlNode(t->element, clone(t->left), clone(t->right));
    }
    int height(AvlNodePtr t)const
    {
      return t == nullptr ? -1 : t->height;
    }
  };
}
#endif

简单测试一下。


//
// AvlTree.cpp
// HelloWorld
// Created by feiyin001 on 17/1/9.
// Copyright (c) 2017年 FableGame. All rights reserved.
//
#include "AvlTree.h"
using namespace Fable;
int main(int argc, char* argv[])
{
  AvlTree<int> a;
  for(int i = 0; i < 100; ++i)
  {
    a.insert(i);
  }
  return 0;
}

这个删除的方法完全是自己写的，可能不是很高效。

希望本文所述对大家C语言程序设计有所帮助。

您可能感兴趣的文章:python 平衡二叉树实现代码示例C语言数据结构平衡二叉树实例详解平衡二叉树AVL操作模板平衡二叉树的实现实例java实现按层遍历二叉树java实现二叉树遍历的三种方式Java二叉树的遍历思想及核心代码实现C语言判定一棵二叉树是否为二叉搜索树的方法分析Python实现输入二叉树的先序和中序遍历，再输出后序遍历操作示例平衡二叉树的左右旋以及双旋转的图文详解

平衡二叉树示例 avl 方法数据二叉树 C语言数据结构