數(shù)據(jù)結(jié)構(gòu)之一對多，樹（完結(jié)）

個(gè)人介紹及問題解決

樹:

定義:一個(gè)樹至多有一個(gè)根節(jié)點(diǎn),每一個(gè)路徑的終端都叫終端節(jié)點(diǎn),也叫葉子結(jié)點(diǎn)。既不是根也不是葉子節(jié)點(diǎn)叫中間節(jié)點(diǎn),節(jié)點(diǎn)與節(jié)點(diǎn)連接的線叫邊。從底下往上看叫高度,從上往低看叫深度。
PS:樹整體高度和深度取最大值。
度:看當(dāng)前節(jié)點(diǎn)有n個(gè)子節(jié)點(diǎn)就叫n度。

樹

二叉樹(Binary Tree)

定義:樹里的每個(gè)節(jié)點(diǎn)至多允許有兩個(gè)節(jié)點(diǎn)。

滿二叉樹

定義:每一層都是滿節(jié)點(diǎn)(2個(gè)節(jié)點(diǎn))除最后一層的二叉樹。

完全二叉樹

定義:只允許最后一層有空缺,且空缺的方式從右向左的二叉樹。
ps:滿二叉樹是完全二叉樹的一種特殊形勢。

平衡二叉樹

定義:樹中任意節(jié)點(diǎn),左右子樹高度差不超過1。
ps:完全二叉樹一定是平衡二叉樹。

排序二叉樹

定義:左孩子的值比父親小,右節(jié)點(diǎn)的值比父節(jié)點(diǎn)的大。

二叉樹的性質(zhì)

  • $k$層滿二叉樹,葉子節(jié)點(diǎn)的個(gè)數(shù)是$ 2^{k-1} $
  • $k$層滿二叉樹,總節(jié)點(diǎn)個(gè)數(shù)為$2^{k}-1$
  • 對于任意一個(gè)二叉樹而言,度為0的節(jié)點(diǎn)比度為2的節(jié)點(diǎn)少一個(gè)。($n_0=n_2+1$),PS:對于一個(gè)完全二叉樹而言,度為1的節(jié)點(diǎn)至多有一個(gè)。
  • 一個(gè)有$n$個(gè)節(jié)點(diǎn)的完全二叉樹,它的深度是$ K=\lfloor log2^{n}\rfloor +1$(向下取整) 例如:3.33 取3
  • 對一個(gè)有$n$個(gè)節(jié)點(diǎn)的完全二叉樹,按照從上到下,從左到右的順序從1開始,開始編號,
  1. $i=1$時(shí)是根節(jié)點(diǎn)。
  2. $2i<=n $ ,$i$有左子樹,否則沒有。
  3. $2i+1<=n$時(shí),$i$有右子樹,否則沒有。
  • 從$1$ ~ $\displaystyle\frac{n}2 $之間的節(jié)點(diǎn)都是父節(jié)點(diǎn),$\displaystyle\frac{n}2 $都是向下取整。

二叉樹的遍歷

  • 深度（遞歸版）
  1. 前序遍歷:根左右
  2. 中序遍歷:左根右
  3. 后序遍歷:左右根
  • 廣度遍歷(層序遍歷):從上到下,從左到右
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
    int nValue;
    struct Node *pLeft;
    struct Node *pRight;

}BinaryTree;
typedef struct node3
{
BinaryTree *nValue;
struct node3 *pNext;
}MyQueue;

typedef struct node4
{
int nCount;
MyQueue* pHead;
MyQueue *pTail;
}Queue;
BinaryTree * CreateTree();
void RecPreOrderTraversal(BinaryTree *pRoot)
{
    if(pRoot == NULL)return;
    //前序遍歷 根左右
    printf("%d ",pRoot->nValue);
    RecPreOrderTraversal(pRoot->pLeft);
    RecPreOrderTraversal(pRoot->pRight);
}
void RecInOrderTraversal(BinaryTree *pRoot)
{
    if(pRoot == NULL)return;
    //中序遍歷 左根右
    RecInOrderTraversal(pRoot->pLeft);
    printf("%d ",pRoot->nValue);
    RecInOrderTraversal(pRoot->pRight);
}
void RecLastOrderTraversal(BinaryTree *pRoot)
{
    if(pRoot == NULL)return;
    //后序遍歷 左右根
    RecLastOrderTraversal(pRoot->pLeft);
    RecLastOrderTraversal(pRoot->pRight);
    printf("%d ",pRoot->nValue);
}
void q_Init(Queue **pQueue)
{
    if(pQueue == NULL)return;
    *pQueue = (Queue*)malloc(sizeof(Queue));
    (*pQueue)->nCount = 0;
    (*pQueue)->pHead = NULL;
    (*pQueue)->pTail = NULL;
}

void q_Push(Queue *pQueue,BinaryTree *nNum)
{
    MyQueue *pTemp = NULL;
    if(pQueue == NULL)return;

    pTemp = (MyQueue*)malloc(sizeof(MyQueue));
    pTemp->nValue = nNum;
    pTemp->pNext = NULL;

    if(pQueue->pHead == NULL)
    {
    pQueue->pHead = pTemp;
    }
    else
    {
    pQueue->pTail->pNext = pTemp;
    }

    pQueue->pTail = pTemp;
    pQueue->nCount++;

}
BinaryTree* q_Pop(Queue *pQueue)
{
    MyQueue *pDel = NULL;
    BinaryTree  *Temp = NULL;
    if(pQueue == NULL || pQueue->pHead == NULL)return NULL;

    pDel = pQueue->pHead;
    Temp = pDel->nValue;

    pQueue->pHead = pQueue->pHead->pNext;
    free(pDel);
    pDel = NULL;
    pQueue->nCount--;

    if(pQueue->nCount == 0)
    {
    pQueue->pTail = NULL;
    }

    return Temp;
}

int q_IsEmpty(Queue *pQueue)
{
    if(pQueue == NULL )return -1;
    return pQueue->nCount ? 0:1;
}
void EveryTravelsalTree(BinaryTree *Tree)
{
    //層序遍歷
    Queue *M_Queue = NULL;
    BinaryTree *Temp = NULL;
    if(Tree == NULL)return;
    q_Init(&M_Queue);
    q_Push(M_Queue,Tree);
    while(!q_IsEmpty(M_Queue))
    {
        Temp = q_Pop(M_Queue);
        printf("%d ",Temp->nValue);
        if(Temp->pLeft != NULL)
        {
            q_Push(M_Queue,Temp->pLeft);
        }
        if (Temp->pRight != NULL)
        {
            q_Push(M_Queue,Temp->pRight);
        }   
    }
}

例二叉樹

二叉樹

前序:X Y F X R B K G D
中序:X B R Y Z F D G K
后序:X Y F Z R B K G D

二叉樹的創(chuàng)建

手動(dòng)創(chuàng)建二叉樹,最慢最基礎(chǔ)零技術(shù)的創(chuàng)建方法

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
    int nValue;
    struct Node *pLeft;
    struct Node *pRight;

}BinaryTree;
BinaryTree * CreateTree()
{
    BinaryTree *pRoot = NULL;
    pRoot = (BinaryTree*)malloc(sizeof(BinaryTree));
    pRoot ->nValue = 1;
    //根的左2
    pRoot->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
    pRoot->pLeft->nValue = 2;
    //左的左4
    pRoot->pLeft->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
    pRoot->pLeft->pLeft->nValue = 4;
    pRoot->pLeft->pLeft->pLeft = NULL;
    pRoot->pLeft->pLeft->pRight = NULL;
    //左的右5
    pRoot->pLeft->pRight = (BinaryTree*)malloc(sizeof(BinaryTree));
    pRoot->pLeft->pRight->nValue = 5;
    pRoot->pLeft->pRight->pLeft = NULL;
    pRoot->pLeft->pRight->pRight = NULL;
    //根的右3
    pRoot->pRight = (BinaryTree*)malloc(sizeof(BinaryTree));
    pRoot->pRight->nValue = 3;
    pRoot->pRight->pRight = NULL;
    //右的左6
    pRoot->pRight->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
    pRoot->pRight->pLeft->nValue = 6;
    pRoot->pRight->pLeft->pLeft = NULL;
    pRoot->pRight->pLeft->pRight = NULL;
    return pRoot;
}

遞歸創(chuàng)建二叉樹(反序列創(chuàng)建二叉樹)

根據(jù)層序遍歷特點(diǎn)來創(chuàng)建二叉樹

void DynamicRecPreOrder(BinaryTree **Temp)
{
    //前序動(dòng)態(tài)創(chuàng)建二叉樹,叫遞歸創(chuàng)建二叉樹或者反序列化創(chuàng)建二叉樹
    int j;
    scanf_s("%d",&j);   
    if(Temp==NULL)return;
    if(j == 0)return;
    *Temp = (BinaryTree*)malloc(sizeof(BinaryTree));
    (*Temp)->nValue = j;
    (*Temp)->pLeft = NULL;
    (*Temp)->pRight = NULL;
    DynamicRecPreOrder(&((*Temp)->pLeft));
    DynamicRecPreOrder(&((*Temp)->pRight));

    return;
}

動(dòng)態(tài)創(chuàng)建二叉樹(用數(shù)組的形勢)

根據(jù)二叉樹的性質(zhì)5

BinaryTree *DynamicArryCreateTree(int Temp[],int Num)
{
    BinaryTree *Templ = NULL;
    int i = 0;
    int m = 0;
    Templ = (BinaryTree*)malloc(sizeof(BinaryTree)*Num);
    for(;i<Num;i++)
    {
        Templ[i].nValue = Temp[i];
        Templ[i].pLeft = NULL;
        Templ[i].pRight = NULL;
    }
    for (m = 0; m <= (Num/2) - 1 ; m++)
    {
        if(2*m+1<Num)
        {
        Templ[m].pLeft = &Templ[2*m+1];
        }
        if(2*m+2<Num)
        {
        Templ[m].pRight = &Templ[2*m+2];
        }
    }

        return Templ;
}

二叉樹的循環(huán)高級遍歷（非遞歸）

敘述流程

  1. 申請棧stack
  2. 檢驗(yàn)參數(shù)
  3. (前序:打印節(jié)點(diǎn))節(jié)點(diǎn)入棧
  4. 判斷節(jié)點(diǎn)是否有左
    • 有,重復(fù)3 4
    • 沒有,下一步(中序:打印節(jié)點(diǎn))
  5. 棧頂彈出,彈出棧頂是否為空
    • 是,結(jié)束
    • 無,重復(fù)5
  6. 判斷彈出節(jié)點(diǎn)是否有右
    • 有,把右變成當(dāng)前節(jié)點(diǎn),之后重復(fù)3 4
    • 無,重復(fù)5

用循環(huán)實(shí)現(xiàn)前序遍歷

void OnRecTraversal(BinaryTree* Temp)
{
    Stack *m_Stack = NULL;
    if(Temp == NULL)return;
    s_Init(&m_Stack);
    while(1)
    {
        while (Temp)
        {
            printf("%d\n",Temp->nValue);
            s_Push(m_Stack,Temp);
            Temp = Temp->pLeft;
        }
        //棧頂彈出
        Temp = s_Pop(m_Stack);
        //判斷節(jié)點(diǎn)是否為空
        if(Temp == NULL)return;
        //向右處理
        Temp = Temp->pRight;
    }
}

用循環(huán)實(shí)現(xiàn)中序遍歷

void MidTraversal(BinaryTree* Temp)
{
    Stack *m_Stack = NULL;
    if(Temp == NULL)return;
    s_Init(&m_Stack);
    while(1)
    {
        while (Temp)
        {
            s_Push(m_Stack,Temp);
            Temp = Temp->pLeft;
        }
        //棧頂彈出
        Temp = s_Pop(m_Stack);
        //判斷節(jié)點(diǎn)是否為空
        if(Temp == NULL)return;
        printf("%d\n",Temp->nValue);
        //向右處理
        Temp = Temp->pRight;
    }
}

用循環(huán)實(shí)現(xiàn)后序遍歷

void RecLastOrderTraversal(BinaryTree* Temp)
{
    Stack *m_Stack = NULL;
    BinaryTree* pTemp = 0;
    if(Temp == NULL)return;
    s_Init(&m_Stack);
    while(1)
    {   
        while (Temp)
        {       
            s_Push(m_Stack,Temp);
            Temp = Temp->pLeft;
        }
        if(m_Stack->pTop == NULL)return;
        if(m_Stack->pTop->nValue->pRight == NULL||m_Stack->pTop->nValue->pRight == pTemp)
        {
            pTemp = s_Pop(m_Stack);
            printf("%d\n",pTemp->nValue);
        }else
        {
            Temp = m_Stack->pTop->nValue->pRight;
        }
    }
    return;
}

在二叉樹中插入一個(gè)結(jié)點(diǎn)

首先先寫一個(gè)查找的API

在一個(gè)二叉樹中查找一個(gè)結(jié)點(diǎn)

BinaryTree * Chop(BinaryTree *pRoot,int nNum)
{
    Queue *pQueue = NULL;
    BinaryTree *pTemp = NULL;
    if(pRoot == NULL)return NULL;
    
    q_Init(&pQueue);

    //根入隊(duì)
    q_Push(pQueue,pRoot);

    while(!q_IsEmpty(pQueue))
    {
        pTemp = q_Pop(pQueue);
        
        if(pTemp->nValue == nNum)
        {
            //記得清空隊(duì)列
            return pTemp;
        }

        //左右非空入隊(duì)
        if(pTemp->pLeft != NULL)
        {
            q_Push(pQueue,pTemp->pLeft);
        }
        if(pTemp->pRight != NULL)
        {
            q_Push(pQueue,pTemp->pRight);
        }
    }
    return NULL;
}

在一個(gè)二叉樹中插入一個(gè)結(jié)點(diǎn),傳入方向,值

//傳入樹，放在那個(gè)節(jié)點(diǎn)的下面，放入得值，放入的方向
void InsertNode(BinaryTree **pRoot,int nNum,int nValue,int nDirection)
{
    BinaryTree *pNode = NULL;
    BinaryTree *pTemp = NULL;
    if(pRoot == NULL || *pRoot == NULL)return;

    //查找
    pNode = Chop(*pRoot,nNum);

    //檢測
    //不存在
    if(pNode == NULL)
    {
        printf("值不存在~~~\n");
        return;
    }

    //存在
    pTemp = (BinaryTree*)malloc(sizeof(BinaryTree));
    pTemp->nValue = nValue;
    pTemp->pLeft = NULL;
    pTemp->pRight = NULL;

    //被插入方向
    if(nDirection == LEFT)
    {
        pTemp->pLeft = pNode->pLeft;
        pNode->pLeft = pTemp;
        return;
    }
    if(nDirection == RIGHT)
    {
        pTemp->pRight = pNode->pRight;
        pNode->pRight = pTemp;
        return;
    }
}

創(chuàng)建一個(gè)排序二叉樹

創(chuàng)建流程

  1. 將值放入結(jié)點(diǎn)
  2. 檢測樹是否為空樹,若是空結(jié)點(diǎn),則新結(jié)點(diǎn)即為根,結(jié)束
  3. 若樹為非空樹
    比較結(jié)點(diǎn)值大小
    若值比結(jié)點(diǎn)值大,則向右子樹方向走
  • 空樹:放入結(jié)點(diǎn)
  • 非空樹:向右走,重復(fù)3步驟

若值比結(jié)點(diǎn)值小,則向左子樹方向走

  • 空樹:放入結(jié)點(diǎn)
  • 非空樹:向左走,重復(fù)3步驟

值相同的話,違背排序二叉樹的步驟,釋放新建結(jié)點(diǎn)空間,結(jié)束

void InsertNode(BinaryTree **pRoot,int nNum)
{
    BinaryTree *pTemp = NULL;
    BinaryTree *pMark = NULL;

    if(pRoot == NULL)return;

    pTemp = (BinaryTree*)malloc(sizeof(BinaryTree));
    pTemp->nValue = nNum;
    pTemp->pLeft = NULL;
    pTemp->pRight = NULL;

    //空樹
    if(*pRoot == NULL)
    {
        *pRoot = pTemp;
        return;
    }

    //標(biāo)記根
    pMark = *pRoot;

    while(1)
    {
        //新來的節(jié)點(diǎn)值小
        if(nNum < pMark->nValue)
        {
            //左空
            if(pMark->pLeft == NULL)
            {
                pMark->pLeft = pTemp;
                return;
            }

            //非空 向左走
            pMark = pMark->pLeft;
        }
        //新來的節(jié)點(diǎn)值大
        else if(nNum > pMark->nValue)
        {
            //右空
            if(pMark->pRight == NULL)
            {
                pMark->pRight = pTemp;
                return;
            }

            //非空 向右走
            pMark = pMark->pRight;
        }

        //新來值已經(jīng)存在  違背性質(zhì)  結(jié)束
        else
        {
            free(pTemp);
            pTemp = NULL;
            return;
        }
    }
}


BinaryTree *CreateSrtTree(int arr[],int nLength)
{
    BinaryTree *pRoot = NULL;
    int i;
    if(arr == NULL || nLength <=0)return NULL;

    for(i = 0;i<nLength;i++)
    {
        InsertNode(&pRoot,arr[i]);
    }
    return pRoot;
}

從排序二叉樹中刪除一個(gè)結(jié)點(diǎn)

刪除的流程

  1. 葉子節(jié)點(diǎn),直接刪除
  2. 有一個(gè)孩子(即只有一個(gè)左子樹或者右子樹),刪除當(dāng)前結(jié)點(diǎn),用孩子代替它
  3. 有兩個(gè)孩子,找到其右的最左或者左的最右的結(jié)點(diǎn),將找到的結(jié)點(diǎn)的值覆蓋刪除結(jié)點(diǎn)的值,之后進(jìn)行步驟1,2

在一個(gè)排序二叉樹查找一個(gè)結(jié)點(diǎn)的代碼

//參數(shù)：樹，被查找的值，被刪除節(jié)點(diǎn)的地址，被刪除節(jié)點(diǎn)的父親
void Search(BinaryTree *pTree,int nNum,BinaryTree **pDel,BinaryTree **pDelFather)
{
    if(pTree == NULL)return;

    while(pTree)
    {
        //找到  記住被刪除位置 結(jié)束
        if(pTree->nValue == nNum)
        {
            *pDel = pTree;
            return;
        }

        //查找的值比當(dāng)前節(jié)點(diǎn)的小 記住被刪除節(jié)點(diǎn)的父親 而后向左走
        else if(pTree->nValue > nNum)
        {
            *pDelFather = pTree;
            pTree = pTree->pLeft;
        }
        //查找的值比當(dāng)前節(jié)點(diǎn)的大 記住被刪除節(jié)點(diǎn)的父親 而后向右走
        else
        {
            *pDelFather = pTree;
            pTree = pTree->pRight;
        }
    }

    //查找結(jié)束 沒找到 清空標(biāo)記刪除節(jié)點(diǎn)父親的指針
    *pDelFather = NULL;
    return ;
}

在排序二叉樹刪除一個(gè)節(jié)點(diǎn)代碼

void DelOneChild(BinaryTree **pRoot, BinaryTree *pDel,BinaryTree *pDelFather)
{
    if(pRoot == NULL)return;

    //被刪除節(jié)點(diǎn)是根
    if(pDelFather == NULL)
    {
        *pRoot = pDel->pLeft ? pDel->pLeft:pDel->pRight;
        free(pDel);
        pDel = NULL;
        
        return;
    }

    //檢測被刪除節(jié)點(diǎn)是父親的左還是右
    if(pDel == pDelFather->pLeft)
    {
        //將被刪除節(jié)點(diǎn)非空的孩子與pdelfather關(guān)聯(lián) 
        pDelFather->pLeft = pDel->pLeft ? pDel->pLeft:pDel->pRight;
        free(pDel);
        pDel = NULL;
        return;
    }
    if(pDel == pDelFather->pRight)
    {
        pDelFather->pRight = pDel->pLeft ? pDel->pLeft:pDel->pRight;
        free(pDel);
        pDel = NULL;
        return;
    }

}

void DelNode(BinaryTree **pTree,int nNum)
{
    BinaryTree *pDel = NULL;
    BinaryTree *pDelFather = NULL;
    BinaryTree *pMark =NULL;
    if(pTree == NULL || *pTree == NULL)return;

    //查找
    Search(*pTree,nNum,&pDel,&pDelFather);

    //沒找到
    if(pDel == NULL)return;

    //找到
    //有兩個(gè)孩子 向右找最小的
    if(pDel->pLeft!= NULL && pDel->pRight != NULL)
    {
        pMark = pDel;

        //移動(dòng)到右
        pDelFather = pDel;
        pDel = pDel->pRight;

        //找右的最左
        while(pDel->pLeft)
        {
            pDelFather = pDel;
            pDel = pDel->pLeft;
        }

        //值覆蓋
        pMark->nValue = pDel->nValue;
    }

    //刪除有一個(gè)孩子的或者沒孩子的
    DelOneChild(pTree,pDel,pDelFather);

}

排序二叉樹轉(zhuǎn)換成一個(gè)排序雙向鏈表

流程

  1. 根據(jù)中序遍歷特點(diǎn),左根右
  2. 將二叉樹左看成鏈表的上指針,將二叉樹的右看鏈表的下指針.
  3. 在中序遍歷輸出的位置,將二叉樹變成鏈表式連接

代碼

void SortTreeToList(BinaryTree *pRoot, BinaryTree **pHead,BinaryTree **pTail)
{
    if(pRoot == NULL)return;
    if(pHead == NULL || pTail == NULL)return;

    //找到左側(cè)
    SortTreeToList(pRoot->pLeft,pHead,pTail);

    //尾添加節(jié)點(diǎn)
    if(*pHead == NULL)
    {
        *pHead = pRoot;
    }
    else
    {
        //雙向指向關(guān)聯(lián)
        //left = 上一個(gè)pre
        //right = 下一個(gè)next
        (*pTail)->pRight = pRoot;
        pRoot->pLeft = *pTail;
    }
    *pTail = pRoot;

    //找到右側(cè)
    SortTreeToList(pRoot->pRight,pHead,pTail);
}

平衡二叉樹的兩種旋轉(zhuǎn)

普通二叉樹深度:后序遍歷查棧里元素的個(gè)數(shù)

將差一步的平衡二叉樹變成平衡二叉樹

右旋

在原有的二叉樹里,添加一個(gè)父親的指針
在左子樹的左子樹添加一個(gè)結(jié)點(diǎn)F,進(jìn)行右旋
A交支點(diǎn)長的一邊B - D - F掰下來


右旋

兩個(gè)步驟:
記:A->pLeft = pMark
先處理兒子:

  • A ->Father->left = pmark
  • pmark->right = A
  • pmark = pmark->right
    父親:
  • pmark ->father = A->father
  • A->father = pmark
  • pmark->right->father = A

左旋

與右旋相反

創(chuàng)建一個(gè)不平衡二叉樹

void CreateBiTree(BinaryTree **root)
{
    if(root == NULL)return;
    (*root) = (BinaryTree*)malloc(sizeof(BinaryTree));
    (*root)->nValue = 1;
    (*root)->pFather = NULL;

    //左子樹
    (*root)->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
    (*root)->pLeft->nValue = 2;
    (*root)->pLeft->pFather = *root;

    //右子樹
    (*root)->pRight = NULL;

    //左的左
    (*root)->pLeft->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
    (*root)->pLeft->pLeft->nValue = 3;
    (*root)->pLeft->pLeft->pFather = (*root)->pLeft;

    //左的左的左
    (*root)->pLeft->pLeft->pLeft = (BinaryTree*)malloc(sizeof(BinaryTree));
    (*root)->pLeft->pLeft->pLeft->nValue = 5;
    (*root)->pLeft->pLeft->pLeft->pFather = (*root)->pLeft->pLeft;
    (*root)->pLeft->pLeft->pLeft->pLeft = NULL;
    (*root)->pLeft->pLeft->pLeft->pRight = NULL;

    //左的左的右
    (*root)->pLeft->pLeft->pRight = (BinaryTree*)malloc(sizeof(BinaryTree));
    (*root)->pLeft->pLeft->pRight ->nValue = 6;
    (*root)->pLeft->pLeft->pRight ->pFather = (*root)->pLeft->pLeft;
    (*root)->pLeft->pLeft->pRight ->pLeft = NULL;
    (*root)->pLeft->pLeft->pRight ->pRight = NULL;

    //左的右
    (*root)->pLeft->pRight = (BinaryTree*)malloc(sizeof(BinaryTree));
    (*root)->pLeft->pRight->nValue = 4;
    (*root)->pLeft->pRight->pFather = (*root)->pLeft;
    (*root)->pLeft->pRight->pLeft = NULL;
    (*root)->pLeft->pRight->pRight = NULL;
}

右旋,左旋代碼

void RightRotate(BinaryTree **pTree)
{
    BinaryTree *pMark = NULL;

    if(pTree == NULL)return;

    //右旋標(biāo)記左側(cè)
    pMark = (*pTree)->pLeft;

    //處理兒子關(guān)系
    (*pTree)->pLeft = pMark->pRight;
    pMark->pRight = *pTree;

    //支點(diǎn)父親是否存在
    if((*pTree)->pFather != NULL)
    {
        //將支點(diǎn)的左和支點(diǎn)的父親關(guān)聯(lián)起來
        ((*pTree)->pFather->pLeft == *pTree)?((*pTree)->pFather->pLeft  = pMark):((*pTree)->pFather->pRight= pMark);
    }

    //關(guān)聯(lián)父親
    //支點(diǎn)的左是否存在
    if((*pTree)->pLeft != NULL)
    {
        (*pTree)->pLeft->pFather = *pTree;
    }

    pMark->pFather = (*pTree)->pFather;
    (*pTree)->pFather = pMark;

    //支點(diǎn)是根節(jié)點(diǎn) 旋轉(zhuǎn)之后根節(jié)點(diǎn)更改
    if(pMark->pFather == NULL)
    {
        *pTree = pMark;
    }
}

void LeftRotate(BinaryTree **pTree)
{
    BinaryTree *pMark = NULL;

    if(pTree == NULL)return;

    //右旋標(biāo)記左側(cè)
    pMark = (*pTree)->pRight;

    //處理兒子關(guān)系
    (*pTree)->pRight = pMark->pLeft;
    pMark->pLeft = *pTree;

    //支點(diǎn)父親是否存在
    if((*pTree)->pFather != NULL)
    {
        //將支點(diǎn)的左和支點(diǎn)的父親關(guān)聯(lián)起來
        ((*pTree)->pFather->pLeft == *pTree)?((*pTree)->pFather->pLeft  = pMark):((*pTree)->pFather->pRight= pMark);
    }

    //關(guān)聯(lián)父親
    //支點(diǎn)的左是否存在
    if((*pTree)->pRight != NULL)
    {
        (*pTree)->pRight->pFather = *pTree;
    }

    pMark->pFather = (*pTree)->pFather;
    (*pTree)->pFather = pMark;

    //支點(diǎn)是根節(jié)點(diǎn) 旋轉(zhuǎn)之后根節(jié)點(diǎn)更改
    if(pMark->pFather == NULL)
    {
        *pTree = pMark;
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容