1、樹(shù)的概念及結(jié)構(gòu)(了解)

1.1樹(shù)的概念：

樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。

• 有一個(gè)特殊的結(jié)點(diǎn)，稱(chēng)為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。
• 除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個(gè)互不相交的集合T1、T2、……、Tm，其中每一個(gè)集合Ti(1<= i <= m)又是一棵結(jié)構(gòu)與樹(shù)類(lèi)似的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼。
• 樹(shù)是遞歸定義的。

子樹(shù)是不相交的；除了根節(jié)點(diǎn)之外，每個(gè)節(jié)點(diǎn)有且僅有一個(gè)父節(jié)點(diǎn)；一棵N個(gè)節(jié)點(diǎn)的樹(shù)有N-1條邊。

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的度； 如上圖：A的為3

葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn)； 如上圖：J、F、K、L、H、I節(jié)點(diǎn)為葉節(jié)點(diǎn)

非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)； 如上圖：B、C、D、E..等節(jié)點(diǎn)為分支節(jié)點(diǎn)

雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱(chēng)為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)

兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱(chēng)為兄弟節(jié)點(diǎn)； 如上圖：B、C是兄弟節(jié)點(diǎn)

樹(shù)的度：一棵樹(shù)中，最大的節(jié)點(diǎn)的度稱(chēng)為樹(shù)的度； 如上圖：樹(shù)的度為3

節(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類(lèi)推；

樹(shù)的高度或深度：樹(shù)中節(jié)點(diǎn)的最大層次； 如上圖：樹(shù)的高度為4

節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先

子孫：以某節(jié)點(diǎn)為根的子樹(shù)中任一節(jié)點(diǎn)都稱(chēng)為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫

森林：由m（m>0）棵互不相交的多顆樹(shù)的集合稱(chēng)為森林；（數(shù)據(jù)結(jié)構(gòu)中的學(xué)習(xí)并查集本質(zhì)就是 一個(gè)森林）

1.2樹(shù)的表示法：

??樹(shù)結(jié)構(gòu)相對(duì)線性表就比較復(fù)雜了，要存儲(chǔ)表示起來(lái)就比較麻煩了，實(shí)際中樹(shù)有很多種表示方式， 如：雙親表示法，孩子表示法、孩子兄弟表示法等等。我們這里就簡(jiǎn)單的了解其中最常用的孩子 兄弟表示法。(我們本期主要講解二叉樹(shù))

typedef int DataType;
struct Node
{
    struct Node* _firstChild1;    // 第一個(gè)孩子結(jié)點(diǎn)
    struct Node* _pNextBrother;   // 指向其下一個(gè)兄弟結(jié)點(diǎn)
    DataType _data;               // 結(jié)點(diǎn)中的數(shù)據(jù)域
};

2、二叉樹(shù)的概念及結(jié)構(gòu)

2.1二叉樹(shù)的概念

一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱(chēng)為左子 樹(shù)和右子樹(shù)的二叉樹(shù)組成。

二叉樹(shù)的特點(diǎn)：

1. 每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，即二叉樹(shù)不存在度大于2的結(jié)點(diǎn)。

2. 二叉樹(shù)的子樹(shù)有左右之分，其子樹(shù)的次序不能顛倒。

2.2特殊的二叉樹(shù)

1、滿(mǎn)二叉樹(shù)：一個(gè)二叉樹(shù)，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹(shù)就是滿(mǎn)二叉 樹(shù)。也就是說(shuō)，如果一個(gè)二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是(2^k) -1 ，則它就是滿(mǎn)二叉樹(shù)。

2、完全二叉樹(shù)：完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿(mǎn)二叉樹(shù)而引出來(lái)的。對(duì) 于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿(mǎn)二叉樹(shù)中編號(hào) 從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱(chēng)之為完全二叉樹(shù)。 要注意的是滿(mǎn)二叉樹(shù)是一種特殊的完全二叉樹(shù)。

2.2二叉樹(shù)的性質(zhì)

1、若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹(shù)的第i層上最多有2^(i-1) 個(gè)結(jié)點(diǎn).

2、若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是2^h- 1.

3、對(duì)任何一棵二叉樹(shù), 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0＝n2 + 1.

2.3二叉樹(shù)的順序存儲(chǔ)

順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來(lái)存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹(shù)，因?yàn)椴皇峭耆鏄?shù)會(huì)有空間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來(lái)存儲(chǔ)，二叉樹(shù)順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹(shù)。

2.4二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來(lái)表示一棵二叉樹(shù)，即用鏈來(lái)指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針?lè)謩e用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，我們本期用的是二叉鏈，后期到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹(shù)等會(huì)用到三叉鏈。

代碼結(jié)構(gòu)搭建：

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

3、二叉樹(shù)鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)

3.1二叉樹(shù)的前中后序遍歷

如果這個(gè)地方看不明白的可以去畫(huà)遞展開(kāi)歸圖，如果畫(huà)展開(kāi)遞歸圖還不明白就得去復(fù)習(xí)下C語(yǔ)言的遞歸章節(jié)了！

3.2求二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)

同理我們一樣可以使用遞歸的方法：

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

3.3求二叉樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)

int TreeLeafSize(BTNode* root)
{
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

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

void DestoryTree(BTNode* root)
{
    if (root == NULL)
        return;
    DestoryTree(root->left);
    DestoryTree(root->right);
 
    free(root);
    root = NULL;
}

還剩一個(gè)二叉樹(shù)的層序遍歷，我把思路給大家講一下，看完了可以自己去實(shí)現(xiàn)一下，如果實(shí)現(xiàn)不了或者有疑問(wèn)隨時(shí)可以聯(lián)系我哦！

層序遍歷：設(shè)二叉樹(shù)的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹(shù)的根節(jié)點(diǎn)出發(fā)，首先訪問(wèn)第一層的樹(shù)根節(jié)點(diǎn)，然 后從左到右訪問(wèn)第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類(lèi)推，自上而下，自左至右逐層訪問(wèn) 樹(shù)的結(jié)點(diǎn)的過(guò)程就是層序遍歷。

可以借助棧來(lái)實(shí)現(xiàn)，上一層帶下一層的思路！

二叉樹(shù)的實(shí)現(xiàn)到這里就結(jié)束了，可能小伙伴還有疑問(wèn)，為什么二叉樹(shù)沒(méi)有增刪查改，因?yàn)橛枚鏄?shù)進(jìn)行增刪查改是沒(méi)意義的，搜索二叉樹(shù)才是需要用到的，再者像復(fù)雜的VAL樹(shù)和紅黑樹(shù)就得等到后期講完C++配合著C++一起講了，這只是非線性的入門(mén)！

到此這篇關(guān)于C語(yǔ)言二叉樹(shù)的概念結(jié)構(gòu)詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論