青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Just enjoy programming

AVL樹(轉(zhuǎn)載)

轉(zhuǎn)載:http://m.shnenglu.com/converse/archive/2007/08/29/31179.html

/********************************************************************
created:    
2007/08/28
filename:     avltree.c
author:        Lichuang

purpose:    AVL樹的實現(xiàn)代碼, 
            參考資料
<<數(shù)據(jù)結構與算法分析-C語言描述>>, 作者Allen Weiss
*********************************************************************/

#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<time.h>

typedef struct AVLTree
{
    
int nData;
    struct AVLTree
* pLeft;
    struct AVLTree
* pRight;
    
int nHeight;
}AVLTree;

int Max(int a, int b);
int Height(AVLTree* pNode);
AVLTree
* Insert(int nData, AVLTree* pNode);
AVLTree
* SingleRotateWithLeft(AVLTree* pNode);
AVLTree
* SingleRotateWithRight(AVLTree* pNode);
AVLTree
* DoubleRotateWithLeft(AVLTree* pNode);
AVLTree
* DoubleRotateWithRight(AVLTree* pNode);
void DeleteTree(AVLTree
** ppRoot);
void PrintTree(AVLTree
* pRoot);

int main()
{
    
int i;
    AVLTree
* pRoot = NULL;

    srand((unsigned 
int)::time(NULL));
    
    
for (i = 0; i < 100000000++i)
    {
        pRoot 
= Insert(::rand(), pRoot);
    }

    
//PrintTree(pRoot);

    DeleteTree(
&pRoot);

    return 
0;
}

int Max(int a, int b)
{
    return (a 
> b ? a : b);
}

int Height(AVLTree* pNode)
{
    
if (NULL == pNode)
        return 
-1;

    return pNode
->nHeight;
}

AVLTree
* Insert(int nData, AVLTree* pNode)
{
    
if (NULL == pNode)
    {
        pNode 
= (AVLTree*)malloc(sizeof(AVLTree));
        pNode
->nData = nData;
        pNode
->nHeight = 0;
        pNode
->pLeft = pNode->pRight = NULL;
    }
    
else if (nData < pNode->nData)          // 插入到左子樹中
    {
        pNode
->pLeft = Insert(nData, pNode->pLeft);
        
if (Height(pNode->pLeft) - Height(pNode->pRight) == 2)    // AVL樹不平衡
        {
            
if (nData < pNode->pLeft->nData)
            {
                
// 插入到了左子樹左邊, 做單旋轉(zhuǎn)
                pNode 
= SingleRotateWithLeft(pNode);
            }
            
else 
            {
                
// 插入到了左子樹右邊, 做雙旋轉(zhuǎn)
                pNode 
= DoubleRotateWithLeft(pNode);
            }
        }
    }
    
else if (nData > pNode->nData)          // 插入到右子樹中
    {
        pNode
->pRight = Insert(nData, pNode->pRight);
        
if (Height(pNode->pRight) - Height(pNode->pLeft) == 2)    // AVL樹不平衡
        {
            
if (nData > pNode->pRight->nData)
            {
                
// 插入到了右子樹右邊, 做單旋轉(zhuǎn)
                pNode 
= SingleRotateWithRight(pNode);
            }
            
else 
            {
                
// 插入到了右子樹左邊, 做雙旋轉(zhuǎn)
                pNode 
= DoubleRotateWithRight(pNode);
            }
        }
    }

    pNode
->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;

    return pNode;
}

/********************************************************************
      pNode                                pNode
->pLeft 
      
/                                             \
pNode
->pLeft                      ==>              pNode
           
\                                       /
          pNode
->pLeft->pRight                   pNode->pLeft->pRight
*********************************************************************/
AVLTree
* SingleRotateWithLeft(AVLTree* pNode)
{
    AVLTree
* pNode1;

    pNode1 
= pNode->pLeft;
    pNode
->pLeft = pNode1->pRight;
    pNode1
->pRight = pNode;

    
// 結點的位置變了, 要更新結點的高度值
    pNode
->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
    pNode1
->nHeight = Max(Height(pNode1->pLeft), pNode->nHeight) + 1;

    return pNode1;
}

/********************************************************************
pNode                                   pNode
->pRight
     
\                                  /
     pNode
->pRight           ==>    pNode 
     
/                                   \
pNode
->pRight->pLeft                     pNode->pRight->pLeft
*********************************************************************/
AVLTree
* SingleRotateWithRight(AVLTree* pNode)
{
    AVLTree
* pNode1;

    pNode1 
= pNode->pRight;
    pNode
->pRight = pNode1->pLeft;
    pNode1
->pLeft = pNode;

    
// 結點的位置變了, 要更新結點的高度值
    pNode
->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
    pNode1
->nHeight = Max(Height(pNode1->pRight), pNode->nHeight) + 1;

    return pNode1;
}

AVLTree
* DoubleRotateWithLeft(AVLTree* pNode)
{
    pNode
->pLeft = SingleRotateWithRight(pNode->pLeft);

    return SingleRotateWithLeft(pNode);
}

AVLTree
* DoubleRotateWithRight(AVLTree* pNode)
{
    pNode
->pRight = SingleRotateWithLeft(pNode->pRight);

    return SingleRotateWithRight(pNode);
}

// 后序遍歷樹以刪除樹
void DeleteTree(AVLTree
** ppRoot)
{
    
if (NULL == ppRoot || NULL == *ppRoot)
        return;

    DeleteTree(
&((*ppRoot)->pLeft));
    DeleteTree(
&((*ppRoot)->pRight));
    free(
*ppRoot);
    
*ppRoot = NULL;
}

// 中序遍歷打印樹的所有結點, 因為左結點 < 父結點 < 右結點, 因此打印出來數(shù)據(jù)的大小是遞增的
void PrintTree(AVLTree
* pRoot)
{
    
if (NULL == pRoot)
        return;

    static 
int n = 0;

    PrintTree(pRoot
->pLeft);
    printf(
"[%d]nData = %d\n"++n, pRoot->nData);
    PrintTree(pRoot
->pRight);
}

posted on 2011-05-11 10:25 周強 閱讀(290) 評論(0)  編輯 收藏 引用 所屬分類: 算法

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲欧美综合网| 亚洲第一久久影院| 欧美全黄视频| 噜噜噜噜噜久久久久久91| 国产精品青草久久| 亚洲另类视频| 亚洲另类黄色| 欧美激情综合五月色丁香小说| 久久婷婷麻豆| 韩国v欧美v日本v亚洲v | 欧美激情欧美狂野欧美精品| 国产一区日韩欧美| 欧美中文字幕在线观看| 欧美一区二区三区视频| 国产精品婷婷午夜在线观看| 宅男精品导航| 香蕉久久一区二区不卡无毒影院 | 欧美黑人国产人伦爽爽爽| 欧美第一黄色网| 91久久久久久| 欧美福利网址| 亚洲日韩欧美视频| 在线一区日本视频| 欧美三区在线视频| 亚洲视频一二区| 欧美影视一区| 永久久久久久| 欧美成人精品一区二区| 亚洲国产视频a| 亚洲午夜精品一区二区三区他趣 | 国产亚洲午夜| 久久综合国产精品| 91久久精品国产91久久性色tv| 亚洲精品美女91| 欧美日韩国产在线播放网站| 亚洲午夜视频在线| 久久久久一区二区三区| 一区视频在线看| 欧美片在线观看| 亚洲欧美日韩国产综合| 麻豆久久久9性大片| 亚洲精品国产精品乱码不99| 欧美三级在线播放| 欧美一区二区成人6969| 欧美成人中文| 亚洲一区二区日本| 激情视频一区| 欧美日韩国语| 久久er精品视频| 亚洲激情视频| 久久精品国产一区二区三区免费看 | 欧美日韩高清免费| 亚洲欧美日韩在线高清直播| 美女被久久久| 亚洲砖区区免费| 亚洲国产精品999| 国产精品久久久久一区二区| 久久久久久久999精品视频| 亚洲精品社区| 玖玖视频精品| 亚洲一级影院| 亚洲国产精品va在看黑人| 国产精品久久国产愉拍| 麻豆视频一区二区| 亚洲一区中文| 亚洲精品一区二区网址| 久久综合网hezyo| 羞羞漫画18久久大片| 亚洲精品免费看| 国语自产精品视频在线看抢先版结局| 欧美高清一区二区| 久久精品日韩欧美| 亚洲免费伊人电影在线观看av| 亚洲黄一区二区三区| 麻豆精品一区二区av白丝在线| 亚洲自拍偷拍一区| 亚洲作爱视频| 91久久精品日日躁夜夜躁国产| 国产日韩久久| 国产精品国产精品| 欧美日韩国产丝袜另类| 蜜臀a∨国产成人精品| 久久黄金**| 香蕉久久精品日日躁夜夜躁| 一区二区三区四区在线| 亚洲伦理精品| 亚洲精品人人| 亚洲欧洲日韩女同| 亚洲欧洲精品一区二区三区波多野1战4 | 久久精品国产清高在天天线| 亚洲男人的天堂在线| 亚洲视屏一区| 亚洲视频久久| 亚洲视频导航| 亚洲一区二区三区乱码aⅴ蜜桃女 亚洲一区二区三区乱码aⅴ | 先锋a资源在线看亚洲| 亚洲一区二区黄| 亚洲一区二区三区精品视频| 这里只有精品视频| 一区二区三区欧美在线| 亚洲视频中文| 亚洲免费小视频| 午夜精品福利电影| 欧美一级大片在线免费观看| 欧美亚洲日本国产| 久久激情五月婷婷| 久久最新视频| 欧美激情精品久久久久久蜜臀 | 99re视频这里只有精品| 99国产一区| 亚洲一区二区三区中文字幕在线| 亚洲在线观看视频网站| 欧美亚洲免费高清在线观看| 欧美一区二区高清在线观看| 久久成人免费| 免费观看日韩av| 欧美日韩国产一区二区| 国产精品久久一区主播| 国产曰批免费观看久久久| 伊人久久大香线蕉av超碰演员| 91久久精品美女| 亚洲在线视频观看| 久久久午夜视频| 亚洲国产成人高清精品| 一区二区三区高清在线| 欧美一区二区三区啪啪| 免费日韩av| 欧美性大战久久久久久久蜜臀| 国产日韩欧美不卡| 亚洲国产精品va在线观看黑人| 在线视频亚洲欧美| 久久精品国内一区二区三区| 欧美国产视频一区二区| 一区二区三区精品视频在线观看| 欧美一级黄色网| 欧美大胆成人| 国产欧美日韩一区二区三区在线观看| 激情综合视频| 亚洲永久精品大片| 免费永久网站黄欧美| 一本色道久久| 久久亚洲精品网站| 欧美午夜不卡在线观看免费| 国语自产精品视频在线看一大j8| 亚洲精选大片| 久久先锋影音| 一本色道久久综合亚洲精品按摩| 久久精品99国产精品酒店日本| 欧美日韩精品免费观看| 国内一区二区在线视频观看| 一区二区日韩伦理片| 蜜桃久久av| 午夜精品一区二区三区电影天堂| 欧美aⅴ99久久黑人专区| 国产亚洲欧美另类中文| 亚洲午夜精品| 亚洲黄色视屏| 久热精品视频在线观看| 国产日韩欧美日韩大片| 宅男噜噜噜66国产日韩在线观看| 欧美成人精品在线视频| 欧美一区二区三区四区在线观看地址 | 亚洲精品一区在线| 久久综合伊人77777麻豆| 亚洲一区在线免费观看| 欧美三级电影一区| 99日韩精品| 亚洲福利视频三区| 久久在线免费观看| 国内揄拍国内精品久久| 久久国产精品72免费观看| 99视频日韩| 欧美啪啪成人vr| 亚洲精品四区| 亚洲国产精品久久久久秋霞蜜臀| 久久精品官网| 国产亚洲制服色| 久久久久国产精品一区| 亚洲欧美日韩在线不卡| 国产精品美女一区二区| 亚洲影院色在线观看免费| 亚洲人成亚洲人成在线观看图片| 免费在线亚洲| 亚洲日本免费| 亚洲精品午夜精品| 欧美日韩精品免费| 亚洲一区精品在线| 亚洲午夜成aⅴ人片| 国产精品美女视频网站| 欧美亚洲三级| 久久大逼视频| 亚洲电影毛片| 亚洲激情综合| 欧美日韩在线视频一区二区| 这里只有精品视频在线| 一区二区欧美日韩| 国产欧美日韩另类视频免费观看| 欧美资源在线| 久久午夜精品一区二区| 亚洲日本国产|