欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(shù)(AVL樹(shù))實(shí)現(xiàn)方法示例

 更新時(shí)間:2018年01月19日 11:50:49   作者:肥寶Fable  
這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(shù)(AVL樹(shù))實(shí)現(xiàn)方法,結(jié)合實(shí)例形式分析了C語(yǔ)言平衡二叉樹(shù)的相關(guān)定義與使用技巧,需要的朋友可以參考下

本文實(shí)例講述了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹(shù)(AVL樹(shù))實(shí)現(xiàn)方法。分享給大家供大家參考,具體如下:

AVL樹(shù)是每個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度最多差1的二叉查找樹(shù)。

要維持這個(gè)樹(shù),必須在插入和刪除的時(shí)候都檢測(cè)是否出現(xiàn)破壞樹(shù)結(jié)構(gòu)的情況。然后立刻進(jìn)行調(diào)整。

看了好久,網(wǎng)上各種各種的AVL樹(shù),千奇百怪。

關(guān)鍵是要理解插入的時(shí)候旋轉(zhuǎn)的概念。

//
// 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;
  }
  //二叉查找樹(shù),對(duì)于Comparable,必須實(shí)現(xiàn)了><=的比較
  template<typename Comparable>
  class AvlTree
  {
  public:
    //構(gòu)造函數(shù)
    AvlTree(){}
    //復(fù)制構(gòu)造函數(shù)
    AvlTree(const AvlTree& rhs)
    {
      root = clone(rhs.root);
    }
    //析構(gòu)函數(shù)
    ~AvlTree()
    {
      makeEmpty(root);
    }
    //復(fù)制賦值運(yùn)算符
    const AvlTree& operator=(const AvlTree& rhs)
    {
      if (this != &rhs)
      {
        makeEmpty(root);//先清除
        root = clone(rhs.root);//再?gòu)?fù)制
      }
      return *this;
    }
    //查找最小的對(duì)象
    const Comparable& findMin()const
    {
      findMin(root);
    }
    //查找最大的對(duì)象
    const Comparable& findMax()const
    {
      findMax(root);
    }
    //是否包含了某個(gè)對(duì)象
    bool contains(const Comparable& x)const
    {
      return contains(x, root);
    }
    //樹(shù)為空
    bool isEmpty()const
    {
      return root == nullptr;
    }
    //打印整棵樹(shù)
    void printTree()const
    {
      printTree(root);
    }
    //清空樹(shù)
    void makeEmpty()
    {
      makeEmpty(root);
    }
    //插入某個(gè)對(duì)象
    void insert(const Comparable& x)
    {
      insert(x, root);
    }
    //移除某個(gè)對(duì)象
    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;//根結(jié)點(diǎn)
    //順時(shí)針旋轉(zhuǎn)
    void clockwiseRotate(AvlNodePtr& a)
    {
      AvlNodePtr b = a->left;//左葉子
      a->left = b->right;//a的左葉子變?yōu)閎的右葉子,b本來(lái)的子結(jié)點(diǎn)都比a小的。
      b->right = a;//b的右結(jié)點(diǎn)指向a,b的高度上升了。
      a->height = max(height(a->left), height(a->right)) + 1;//重新計(jì)算a的高度
      b->height = max(height(b->left), a->height) + 1;//重新計(jì)算b的高度
      a = b;//a的位置現(xiàn)在是b,當(dāng)前的根結(jié)點(diǎn)
    }
    //逆時(shí)針旋轉(zhuǎn)
    void antiClockWiseRotate(AvlNodePtr& a)
    {
      AvlNodePtr b = a->right;//右結(jié)點(diǎn)
      a->right = b->left;//a接收b的左結(jié)點(diǎn)
      b->left = a;//自己成為b的左結(jié)點(diǎn)
      a->height = max(height(a->left), height(a->right)) + 1;//計(jì)算高度
      b->height = max(b->height, height(a->right)) + 1;//計(jì)算高度
      a = b;//新的根結(jié)點(diǎn)
    }
    //對(duì)左邊結(jié)點(diǎn)的雙旋轉(zhuǎn)
    void doubleWithLeftChild(AvlNodePtr& k3)
    {
      antiClockWiseRotate(k3->left);//逆時(shí)針旋轉(zhuǎn)左結(jié)點(diǎn)
      clockwiseRotate(k3);//順時(shí)針旋轉(zhuǎn)自身
    }
    //對(duì)右邊結(jié)點(diǎn)的雙旋轉(zhuǎn)
    void doubleWithRightChild(AvlNodePtr& k3)
    {
      clockwiseRotate(k3->right);//順時(shí)針旋轉(zhuǎn)有節(jié)點(diǎn)
      antiClockWiseRotate(k3);//逆時(shí)針旋轉(zhuǎn)自身
    }
    //插入對(duì)象,這里使用了引用
    void insert(const Comparable& x, AvlNodePtr& t)
    {
      if (!t)
      {
        t = new AvlNode(x, nullptr, nullptr);
      }
      else if (x < t->element)
      {
        insert(x, t->left);//比根結(jié)點(diǎn)小,插入左邊
        if (height(t->left) - height(t->right) == 2)//高度差達(dá)到2了
        {
          if (x < t->left->element)//插入左邊
          {
            clockwiseRotate(t);//順時(shí)針旋轉(zhuǎn)
          }
          else
          {
            doubleWithLeftChild(t);//雙旋轉(zhuǎn)
          }
        }
      }
      else if (x > t->element)
      {
        insert(x, t->right);//比根結(jié)點(diǎn)大,插入右邊
        if (height(t->right) - height(t->left) == 2)//高度差達(dá)到2
        {
          if (t->right->element < x)//插入右邊
          {
            antiClockWiseRotate(t);//旋轉(zhuǎn)
          }
          else
          {
            doubleWithRightChild(t);//雙旋轉(zhuǎn)
          }
        }
      }
      else
      {
        //相同的
      }
      t->height = max(height(t->left), height(t->right)) + 1;//計(jì)算結(jié)點(diǎn)的高度
    }
    void removeMin(AvlNodePtr& x, AvlNodePtr& t)const
    {
      if (!t)
      {
        return;//找不到
      }
      if (t->left)
      {
        removeMin(t->left);//使用了遞歸的方式
      }
      else
      {
        //找到最小的結(jié)點(diǎn)了
        x->element = t->element;
        AvlNodePtr oldNode = t;
        t = t->right;
        delete oldNode;//刪除原來(lái)要?jiǎng)h除的結(jié)點(diǎn)
      }
      if (t)
      {
        t->height = max(height(t->left), height(t->right)) + 1;//計(jì)算結(jié)點(diǎn)的高度
        if(height(t->left) - height(t->right) == 2)
        { //如果左兒子高度大于右兒子高度
          if(height(t->left->left) >= height(t->left->right))//并且左兒子的左子樹(shù)高度大于左兒子的右子樹(shù)高度
          {
            clockwiseRotate(t); //順時(shí)針旋轉(zhuǎn)
          }
          else
          {
            doubleWithLeftChild(t);//雙旋轉(zhuǎn)左子樹(shù)
          }
        }
        else
        {
          if(height(t->right->right) - height(t->right->left) == 2) //如果右子樹(shù)大于左子樹(shù)
          {
            antiClockWiseRotate(t);//逆時(shí)針旋轉(zhuǎn)
          }
          else
          {
            doubleWithRright(t);//雙旋轉(zhuǎn)右子樹(shù)
          }
        }
      }
    }
    //刪除某個(gè)對(duì)象,這里必須要引用
    void remove(const Comparable& x, AvlNodePtr& t)const
    {
      if (!t)
      {
        return;//樹(shù)為空
      }
      else if (x < t->element)
      {
        remove(x, t->left);//比根結(jié)點(diǎn)小,去左邊查找
      }
      else if (x > t->element)
      {
        remove(x, t->right);//比根結(jié)點(diǎn)大,去右邊查找
      }
      else if (!t->left && !t->right)//找到結(jié)點(diǎn)了,有兩個(gè)葉子
      {
        removeMin(t, t->right);//這里選擇的方法是刪除右子樹(shù)的最小的結(jié)點(diǎn)
      }
      else
      {
        AvlNodePtr oldNode = t;
        t = (t->left) ? t->left : t->right;//走到這里,t最多只有一個(gè)葉子,將t指向這個(gè)葉子
        delete oldNode;//刪除原來(lái)要?jiǎng)h除的結(jié)點(diǎn)
      }
      if (t)
      {
        t->height = max(height(t->left), height(t->right)) + 1;//計(jì)算結(jié)點(diǎn)的高度
        if(height(t->left) - height(t->right) == 2)
        { //如果左兒子高度大于右兒子高度
          if(height(t->left->left) >= height(t->left->right))//并且左兒子的左子樹(shù)高度大于左兒子的右子樹(shù)高度
          {
            clockwiseRotate(t); //順時(shí)針旋轉(zhuǎn)
          }
          else
          {
            doubleWithLeftChild(t);//雙旋轉(zhuǎn)左子樹(shù)
          }
        }
        else
        {
          if(height(t->right->right) - height(t->right->left) == 2) //如果右子樹(shù)大于左子樹(shù)
          {
            antiClockWiseRotate(t);//逆時(shí)針旋轉(zhuǎn)
          }
          else
          {
            doubleWithRright(t);//雙旋轉(zhuǎn)右子樹(shù)
          }
        }
      }
    }
    //左邊子樹(shù)的結(jié)點(diǎn)肯定比當(dāng)前根小的,所以一直往左邊尋找
    AvlNodePtr findMin(AvlNodePtr t)const
    {
      if (!t)
      {
        return nullptr;//找不到
      }
      if (!t->left)
      {
        return t;
      }
      return findMin(t->left);//使用了遞歸的方式
    }
    //右邊子樹(shù)的結(jié)點(diǎn)肯定比當(dāng)前根大,所以一直往右邊找
    AvlNodePtr findMax(AvlNodePtr t)const
    {
      if (t)
      {
        while (t->right)//使用了循環(huán)的方式
        {
          t = t->right;
        }
      }
      return t;
    }
    //判斷是否包含某個(gè)對(duì)象,因?yàn)橐褂眠f歸,所以還有一個(gè)public版本的
    bool contains(const Comparable& x, AvlNodePtr t)const
    {
      if (!t)
      {
        return false;//空結(jié)點(diǎn)了
      }
      else if (x < t->element)
      {
        //根據(jù)二叉樹(shù)的定義,比某個(gè)結(jié)點(diǎn)小的對(duì)象,肯定只能存在與這個(gè)結(jié)點(diǎn)的左邊的子樹(shù)
        return contains(x, t->left);
      }
      else if (x > t->element)
      {
        //根據(jù)二叉樹(shù)的定義,比某個(gè)結(jié)點(diǎn)大的對(duì)象,肯定只能存在與這個(gè)結(jié)點(diǎn)的右邊的子樹(shù)
        return contains(x, t->right);
      }
      else
      {
        //相等,就是找到啦。
        return true;
      }
    }
    //清空子樹(shù)
    void makeEmpty(AvlNodePtr& t)
    {
      if (t)
      {
        makeEmpty(t->left);//清空左邊
        makeEmpty(t->right);//清空右邊
        delete t;//釋放自身
      }
      t = nullptr;//置為空
    }
    //打印子樹(shù),這里沒(méi)有使用復(fù)雜的排位,純屬打印
    void printTree(AvlNodePtr t)const
    {
      if (!t)
      {
        return;
      }
      std::cout << t->element << std::endl;//輸出自身的對(duì)象
      printTree(t->left);//打印左子樹(shù)
      printTree(t->right);//打印右子樹(shù)
    }
    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

簡(jiǎn)單測(cè)試一下。

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

這個(gè)刪除的方法完全是自己寫的,可能不是很高效。

希望本文所述對(duì)大家C語(yǔ)言程序設(shè)計(jì)有所幫助。

相關(guān)文章

  • 淺談C++的淺拷貝出現(xiàn)的錯(cuò)誤

    淺談C++的淺拷貝出現(xiàn)的錯(cuò)誤

    下面小編就為大家?guī)?lái)一篇淺談C++的淺拷貝出現(xiàn)的錯(cuò)誤。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2017-01-01
  • C語(yǔ)言實(shí)現(xiàn)班級(jí)檔案管理系統(tǒng)課程設(shè)計(jì)

    C語(yǔ)言實(shí)現(xiàn)班級(jí)檔案管理系統(tǒng)課程設(shè)計(jì)

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)班級(jí)檔案管理系統(tǒng)課程設(shè)計(jì),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-12-12
  • C++ Primer中&、*符號(hào)的多重定義與int *p和int* p的區(qū)別講解

    C++ Primer中&、*符號(hào)的多重定義與int *p和int* p的區(qū)別講解

    今天小編就為大家分享一篇關(guān)于C++Primer中&、*符號(hào)的多重定義與int *p和int* p的區(qū)別講解,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧
    2019-04-04
  • Prim(普里姆)算法求最小生成樹(shù)的思想及C語(yǔ)言實(shí)例講解

    Prim(普里姆)算法求最小生成樹(shù)的思想及C語(yǔ)言實(shí)例講解

    Prim算法能夠在帶權(quán)的圖中搜索出最小生成樹(shù),這也是各大ACM和面試及考研題目中的熱點(diǎn),下面我們就來(lái)詳細(xì)看一下Prim(普里姆)算法求最小生成樹(shù)的思想及C語(yǔ)言實(shí)例講解
    2016-06-06
  • C語(yǔ)言實(shí)現(xiàn)掃雷經(jīng)典游戲

    C語(yǔ)言實(shí)現(xiàn)掃雷經(jīng)典游戲

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)掃雷經(jīng)典游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-07-07
  • C語(yǔ)言文件打開(kāi)的模式

    C語(yǔ)言文件打開(kāi)的模式

    這篇文章主要介紹了C語(yǔ)言文件打開(kāi)的模式,以及相關(guān)的原理和知識(shí)點(diǎn)做了分享,有興趣的朋友參考學(xué)習(xí)下。
    2018-03-03
  • C++內(nèi)存管理介紹

    C++內(nèi)存管理介紹

    這篇文章主要介紹了C++內(nèi)存管理,C++標(biāo)準(zhǔn)委員會(huì)給我們提供了auto_ptr智能指針,后面又引入了share_ptr以及weak_ptr幫助我們正確和安全的使用指針,本文主要是介紹boost庫(kù)提供的解決方案,需要的朋友可以參考一下
    2022-01-01
  • Opencv處理圖像之輪廓提取

    Opencv處理圖像之輪廓提取

    這篇文章主要為大家詳細(xì)介紹了Opencv處理圖像之輪廓提取,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-01-01
  • C++中的拷貝構(gòu)造詳解

    C++中的拷貝構(gòu)造詳解

    這篇文章主要為大家介紹了C++中的拷貝構(gòu)造,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助
    2022-01-01
  • C語(yǔ)言實(shí)現(xiàn)隨機(jī)抽取紙牌程序

    C語(yǔ)言實(shí)現(xiàn)隨機(jī)抽取紙牌程序

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)隨機(jī)抽取紙牌程序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-03-03

最新評(píng)論