引言

現(xiàn)在是北京時(shí)間2023年6月13日9點(diǎn)11分。從決定要開(kāi)始減脂之后，饑餓總是伴隨著我。一覺(jué)起來(lái)肚子咕咕叫，我還是想先把文章發(fā)了再吃第一餐。燕麥加蛋白粉幾乎伴隨了我大學(xué)的第一年早飯。昨天練了一個(gè)小時(shí)背，練背后還做了45分鐘有氧?？崭褂?xùn)練沒(méi)有影響我的訓(xùn)練狀態(tài)。這一點(diǎn)我還是比較舒服的。堅(jiān)持鍛煉是一個(gè)不錯(cuò)的習(xí)慣也懇請(qǐng)你務(wù)必多多鍛煉自己的身體，身體就是自己最寶貴的財(cái)富。

前言

本篇文章講解的主要是二叉樹(shù)的結(jié)構(gòu)以及操作，對(duì)于學(xué)習(xí)二叉樹(shù)來(lái)說(shuō)先了解它的使用，再回過(guò)頭去學(xué)習(xí)它的底層原理等效果會(huì)更好。所以，我就簡(jiǎn)單模擬實(shí)現(xiàn)了一個(gè)簡(jiǎn)單二叉樹(shù)，等結(jié)構(gòu)和用法都了解的差不多了再研究二叉樹(shù)真正創(chuàng)建的方式。

typedef int BTDataType;

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    BTDataType data;
    
}BTNode;

BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        return NULL;
    }

    node->data = x;
    node->left = NULL;
    node->right = NULL;

    return node;
}

BTNode* CreatTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    BTNode* node7 = BuyNode(7);


    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    node3->right = node7;

    return node1;
}

簡(jiǎn)單回顧

這里簡(jiǎn)單回顧一下二叉樹(shù)的概念。二叉樹(shù)又分為空二叉樹(shù)和非空二叉數(shù)兩種。非空二叉樹(shù)有兩個(gè)部分構(gòu)成：根和子樹(shù)，子樹(shù)又可以分成根和子樹(shù)。

二叉樹(shù)的遍歷

二叉樹(shù)的遍歷大致分為四種，前序遍歷、中序遍歷、后序遍歷、層序遍歷。下面我們就了解一下各種的遍歷方式。

前序遍歷

實(shí)現(xiàn)思路大致如下，采取遞歸的思想進(jìn)行遍歷。遞歸的結(jié)束條件為遍歷的結(jié)點(diǎn)為空就結(jié)束。

void PreOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    printf("%d ",root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

中序遍歷

與前序遍歷的的代碼邏輯大致一樣，只是訪問(wèn)根的順序時(shí)機(jī)不同。本質(zhì)上還是一樣的思想。

void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

后序遍歷

void PosOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    PosOrder(root->left);
    PosOrder(root->right);
    printf("%d ", root->data);
}

求樹(shù)結(jié)點(diǎn)總數(shù)

求節(jié)點(diǎn)的總個(gè)數(shù)的思路就是用分治的思想。只要節(jié)點(diǎn)不為NULL就表示有一個(gè)結(jié)點(diǎn)，然后將左右子樹(shù)的結(jié)點(diǎn)總數(shù)的和加上1（1即根結(jié)點(diǎn)）就能求出當(dāng)前結(jié)點(diǎn)的總數(shù)。二叉樹(shù)是可以不斷地拆分成根和左右子樹(shù)的，其實(shí)遞歸的核心就是處理一個(gè)個(gè)與原問(wèn)題類(lèi)似的子問(wèn)題。

int TreeSize(BTNode* root)
{
    return root == NULL ?
            0 :
            TreeSize(root->left)
            +TreeSize(root->right)
            +1;
}

求樹(shù)的高度

求樹(shù)的高度也可以采取分治的思路。如果說(shuō)上面的求結(jié)點(diǎn)總數(shù)是校長(zhǎng)求全校的人數(shù)，那么求樹(shù)的高度其實(shí)就是找全校最高的人。實(shí)現(xiàn)思路如下，找左右子樹(shù)中較大的那個(gè)加上根節(jié)點(diǎn)的高度就是樹(shù)的高度。

int TreeHeight(BTNode* root)
{
    if(root == NULL)
        return 0;
    
    int lh =TreeHeight(root->left);
    int rh =TreeHeight(root->right);
    
    return lh > rh ? lh+1 : rh+1;
}

求第k層節(jié)點(diǎn)個(gè)數(shù)

求第k層的結(jié)點(diǎn)個(gè)數(shù)本質(zhì)就是求左子樹(shù)第k-1個(gè)結(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)第k-1層結(jié)點(diǎn)個(gè)數(shù)的和。

int TreeKLevel(BTNode* root, int k)
{
    if(root == NULL)
        return 0;
    if(k == 1)
        return 1;
    int lk = TreeKLevel(root->left, k-1);
    int rk = TreeKLevel(root->right, k-1);
    
    return lk+rk;
    
}

單值二叉樹(shù)問(wèn)題

本題的解題的思路有很多，如遍歷、分治等。當(dāng)然這里比較推薦實(shí)用分治的思想來(lái)進(jìn)行解決這種二叉樹(shù)的很多問(wèn)題中，遍歷的結(jié)局思路是不如分治的。下面就簡(jiǎn)單的介紹一下思路。首先，要將結(jié)點(diǎn)為空的情況考慮進(jìn)去。其次，判斷左右子結(jié)點(diǎn)是否存在且值不相等的情況。最后，分治遞歸進(jìn)行比較判斷，只要有一個(gè)不相等整體就是不為等值二叉樹(shù)。

二叉樹(shù)的查找

二叉樹(shù)的查找接口，它的作用不僅僅是查找到該結(jié)點(diǎn)，還可以作為獲取想要修改結(jié)點(diǎn)的地址的一個(gè)方式。實(shí)現(xiàn)思路主要是以遞歸的思想進(jìn)行遍歷整棵樹(shù)。如果結(jié)點(diǎn)的值==val，那就返回這個(gè)結(jié)點(diǎn)的地址。

BTNode* BTFind(BTNode* root, int x)
{
    if(root == NULL)
    {
        return NULL;
    }
    //判斷
    if(root->data == x)
        return root;
    //NULL不返回，找到了才返回
    BTNode* lret = BTFind(root->left, x);
    if(lret)
        return lret;
    BTNode* rret = BTFind(root->right, x);
    if(rret)
        return rret;
    //走到此處表示沒(méi)有找到結(jié)點(diǎn)
    return NULL;
}

相同二叉樹(shù)

解決本問(wèn)題的思路如下，首先，考慮根節(jié)點(diǎn)都為空的情況以及其中是一個(gè)根結(jié)點(diǎn)為空的情況下。然后遞歸判斷左右子樹(shù)值是否相等即可。

前序遍歷oj

主要介紹的是接口型oj的特點(diǎn)。這里的returnSize是一個(gè)輸出型參數(shù)，傳遞的局部變量標(biāo)識(shí)數(shù)組長(zhǎng)度變量的地址，要求我們寫(xiě)入動(dòng)態(tài)開(kāi)辟數(shù)組的長(zhǎng)度。作為返回值的數(shù)組要用存放在堆區(qū)（動(dòng)態(tài)申請(qǐng)）的數(shù)組。若使用局部定義的數(shù)組，在函數(shù)調(diào)用結(jié)束后就會(huì)銷(xiāo)毀，就無(wú)法的到遍歷后的結(jié)果，也會(huì)有野指針問(wèn)題。

解題思路如下，先求出樹(shù)的結(jié)點(diǎn)總數(shù)，然后，根據(jù)樹(shù)的結(jié)點(diǎn)總數(shù)來(lái)malloc申請(qǐng)空間。最后，在創(chuàng)建一個(gè)局部變量來(lái)作為標(biāo)記數(shù)組下標(biāo)，前序遍歷將數(shù)據(jù)寫(xiě)入數(shù)組中。

另一棵樹(shù)的子樹(shù)

解題思路如下，首先，root == NULL時(shí)，那就不可能是匹配和subRoot的一樣的子樹(shù)。然后，這里可以復(fù)用之前寫(xiě)的判斷兩樹(shù)是否相同的代碼，用每個(gè)根節(jié)點(diǎn)進(jìn)行匹配，然后，遞歸分治找到匹配的子樹(shù)就返回真，否則返回假。

層序遍歷

二叉樹(shù)的層序遍歷實(shí)現(xiàn)思路如下，將根節(jié)點(diǎn)入隊(duì)列，遍歷根節(jié)點(diǎn)后，判斷根的左右節(jié)點(diǎn)是否為NULL，不為NULL就入隊(duì)列。循環(huán)往復(fù)直到隊(duì)列為空就結(jié)束層序遍歷。點(diǎn)擊獲取隊(duì)列實(shí)現(xiàn)代碼。

判斷是否為完全二叉樹(shù)

本接口實(shí)現(xiàn)主要思路是根據(jù)層序遍歷，完全二叉樹(shù)第一個(gè)NULL結(jié)點(diǎn)后面不會(huì)出現(xiàn)非空結(jié)點(diǎn)。實(shí)現(xiàn)步驟依舊是層序遍歷的思路，當(dāng)出到第一個(gè)NULL結(jié)點(diǎn)時(shí)，便不再讓數(shù)據(jù)入隊(duì)，遍歷剩下的結(jié)點(diǎn)。當(dāng)出現(xiàn)非空結(jié)點(diǎn)即表示不是完全二叉樹(shù)，若全為空結(jié)點(diǎn)則表示為完全二叉樹(shù)。

二叉樹(shù)的銷(xiāo)毀

采取后序遍歷的思想進(jìn)行對(duì)節(jié)點(diǎn)的釋放。這里實(shí)現(xiàn)的版本為一級(jí)指針作為參數(shù)，需要調(diào)用本函數(shù)后手動(dòng)置空。
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-481836.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——二叉樹(shù)基礎(chǔ)結(jié)構(gòu)篇（C語(yǔ)言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！