樹(shù)(Tree)：是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。當(dāng)n=0時(shí)為空樹(shù)。

創(chuàng)新互聯(lián)主要從事網(wǎng)站設(shè)計(jì)制作、做網(wǎng)站、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)館陶,十多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):028-86922220

森林(Forest)：是m(m>=0)棵互不相交的樹(shù)的集合。

樹(shù)的存儲(chǔ)結(jié)構(gòu)：

雙親表示法

//雙親結(jié)點(diǎn)表示法
#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct PTNode
{ElemType data;  //結(jié)點(diǎn)數(shù)據(jù)
    int parent;   //雙親位置
}PTNode;

typedef struct
{PTNode nodes[MAX_TREE_SIZE];
    int r;  //根的位置
    int n;  //結(jié)點(diǎn)數(shù)目
}PTree;

雙親孩子表示法

#define MAX_TREE_SIZE 100

typedef char ElemType;

//孩子結(jié)點(diǎn)
typedef struct CTNode
{int child;  //孩子結(jié)點(diǎn)的下標(biāo)
    struct CTNode *next;  //指向下一個(gè)孩子結(jié)點(diǎn)的指針
}*ChildPtr;

//表頭結(jié)構(gòu)
typedef struct
{ElemType data;  //存放在樹(shù)中的結(jié)點(diǎn)的數(shù)據(jù)
    int parent;    //存放雙親的下標(biāo)
    ChildPtr firstchild;  //指向第一個(gè)孩子的指針
}CTBox;

//樹(shù)結(jié)構(gòu)
typedef struct
{CTBox nodes[MAX_TREE_SIZE];  //結(jié)點(diǎn)數(shù)組
    int r,n;
}

二叉樹(shù)的定義：是n(n>=0)個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集，或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的、分別稱為根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

二叉樹(shù)的五種基本形態(tài)

空二叉樹(shù)

只有根節(jié)點(diǎn)的二叉樹(shù)

根節(jié)點(diǎn)只有左子樹(shù)

根節(jié)點(diǎn)只有右子樹(shù)

根節(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)

特殊二叉樹(shù)

滿二叉樹(shù)：所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在同一層上。

完全二叉樹(shù)：是一個(gè)深度為k的有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中的節(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i(1≤i≤n)的結(jié)點(diǎn)與滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置相同。

特點(diǎn)：

• 葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層。
• 最下層的葉子一定集中在左部連續(xù)位置。
• 倒數(shù)第二層，若有葉子結(jié)點(diǎn)，一定都在右部連續(xù)位置。
• 如果結(jié)點(diǎn)度為1，則該結(jié)點(diǎn)只有左孩子。
• 同樣結(jié)點(diǎn)的二叉樹(shù)，完全二叉樹(shù)深度最小。

注：滿二叉樹(shù)一定是完全二叉樹(shù)，但完全二叉樹(shù)不一定是滿二叉樹(shù)。

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

在二叉樹(shù)的第 i 層上至多有 2 i ? 1 個(gè)結(jié)點(diǎn) ( i > = 1 ) 深度為 k 的二叉樹(shù)至多有 2 k ? 1 個(gè)結(jié)點(diǎn) ( k > = 1 ) 對(duì)于任何一棵二叉樹(shù) T ，如果其終端結(jié)點(diǎn)數(shù)為 n 0 ，度為 2 的結(jié)點(diǎn)數(shù)為 n 2 ，則 n 0 = n 2 + 1 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 ? l o g 2 n ? + 1 如果對(duì)一棵有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，對(duì)任一結(jié)點(diǎn) i ( 1 < = i < = n ) 有以下性質(zhì)： ? 如果 i = 1 ，則結(jié)點(diǎn) i 是二叉樹(shù)的根，無(wú)雙親；如果 i > 1 ，則其雙親是結(jié)點(diǎn) ? i / 2 ? ? 如果 2 i > n ，則結(jié)點(diǎn) i 無(wú)左孩子 ( 結(jié)點(diǎn) i 為葉子結(jié)點(diǎn) ) ；否則其左孩子是 2 i ? 如果 2 i + 1 > n ，則結(jié)點(diǎn) i 無(wú)右孩子；否則其右孩子是結(jié)點(diǎn) 2 i + 1 \begin{align} &在二叉樹(shù)的第i層上至多有2^{i-1}個(gè)結(jié)點(diǎn)(i>=1)\\ &深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn)(k>=1)\\ &對(duì)于任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1\\ &具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為\lfloor log_2n \rfloor+1\\ &如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，對(duì)任一結(jié)點(diǎn)i(1<=i<=n)有以下性質(zhì)：\\ &- 如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親是結(jié)點(diǎn)\lfloor i/2 \rfloor\\ &- 如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn))；否則其左孩子是2i\\ &- 如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子是結(jié)點(diǎn)2i+1 \end{align} ?在二叉樹(shù)的第i層上至多有2i?1個(gè)結(jié)點(diǎn)(i>=1)深度為k的二叉樹(shù)至多有2k?1個(gè)結(jié)點(diǎn)(k>=1)對(duì)于任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為?log2?n?+1如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，對(duì)任一結(jié)點(diǎn)i(1<=i<=n)有以下性質(zhì)：?如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親是結(jié)點(diǎn)?i/2??如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn))；否則其左孩子是2i?如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子是結(jié)點(diǎn)2i+1??

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

二叉鏈表

typedef struct BiTNode
{ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

二叉樹(shù)的遍歷

前序遍歷

中序遍歷

后序遍歷

層序遍歷

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：樹(shù)和二叉樹(shù)的性質(zhì)結(jié)構(gòu)-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://aaarwkj.com/article2/codjic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁(yè)設(shè)計(jì)公司、移動(dòng)網(wǎng)站建設(shè)、搜索引擎優(yōu)化、網(wǎng)站設(shè)計(jì)公司、網(wǎng)站設(shè)計(jì)、響應(yīng)式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)