樹(shù) 樹(shù)的定義

樹(shù)（Tree）：n（n$\geq$0）個(gè)結(jié)點(diǎn)構(gòu)成的有限集合

創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括高縣網(wǎng)站建設(shè)、高縣網(wǎng)站制作、高縣網(wǎng)頁(yè)制作以及高縣網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，高縣網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到高縣省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

當(dāng)n=0時(shí)，稱為空樹(shù)

特征

對(duì)于任一棵非空樹(shù)（n>0），它具備一下特征：

• 樹(shù)中有個(gè)稱為“根（Root）”的特殊結(jié)點(diǎn)，用r表示
• 其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集T₁，T₂…，T_m，其中每個(gè)集合本身又是一棵樹(shù)，稱為原來(lái)樹(shù)的“子樹(shù)（SubTree）”
• 子樹(shù)是不相交的
• 除根節(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)父節(jié)點(diǎn)
• 一棵N個(gè)結(jié)點(diǎn)的樹(shù)有N-1條邊

基本術(shù)語(yǔ)

• 結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)

• 樹(shù)的度：樹(shù)的所有結(jié)點(diǎn)中大的度數(shù)

• 葉節(jié)點(diǎn)（Leaf）：度為0的結(jié)點(diǎn)

• 父結(jié)點(diǎn)（Parent）：有子樹(shù)的結(jié)點(diǎn)是其子樹(shù)的根結(jié)點(diǎn)的父結(jié)點(diǎn)

• 子節(jié)點(diǎn)（Child）：若A結(jié)點(diǎn)是B結(jié)點(diǎn)的父結(jié)點(diǎn)，則稱B結(jié)點(diǎn)是A結(jié)點(diǎn)的子節(jié)點(diǎn)，也成孩子結(jié)點(diǎn)

• 兄弟結(jié)點(diǎn)（Sibling）：具有統(tǒng)一父節(jié)點(diǎn)的各個(gè)結(jié)點(diǎn)彼此是兄弟結(jié)點(diǎn)

• 路徑：從結(jié)點(diǎn)n₁到n_k的路徑為一個(gè)結(jié)點(diǎn)序列n₁，n₂…. n_k，n_i是n₊₁的父結(jié)點(diǎn)

• 路徑長(zhǎng)度：路徑所包含邊的個(gè)數(shù)

• 祖先結(jié)點(diǎn)（Ancestor）：沿樹(shù)根到某一結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)都是這個(gè)結(jié)點(diǎn)的祖宗結(jié)點(diǎn)

• 子孫結(jié)點(diǎn)（Descendant）：某一結(jié)點(diǎn)的子樹(shù)中的所有結(jié)點(diǎn)是這個(gè)結(jié)點(diǎn)的子孫

• 結(jié)點(diǎn)的層次（Level）：規(guī)定根結(jié)點(diǎn)在1層，其他任一結(jié)點(diǎn)的層數(shù)是其父結(jié)點(diǎn)的層數(shù)+1

• 樹(shù)的深度（Depth）：樹(shù)中所有結(jié)點(diǎn)中大層次是這棵樹(shù)的深度

樹(shù)的表示 兒子 - 兄弟表示法

• Element 存值
• FirstChild 指向第一個(gè)兒子
• NextSibing 指向下一個(gè)兄弟

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-O9SqFjfd-1669946093040)(C:\Users\lx659\AppData\Roaming\Typora\typora-user-images\image-20221130223011506.png)]

二叉樹(shù)

即度為2的樹(shù)

• Element 存值
• Left 指向左子樹(shù)
• Right 指向右子樹(shù)

二叉樹(shù)其實(shí)就是兒子 - 兄弟表示法的鏈表右移45°得到的結(jié)果

二叉樹(shù)定義

二叉樹(shù) T ：一個(gè)有窮的結(jié)點(diǎn)集合

這個(gè)集合可以為空

若不為空，則它是由根結(jié)點(diǎn)和稱為其**左子樹(shù)T_L和右子樹(shù)T_R**的兩個(gè)不想交的二叉樹(shù)組成二叉樹(shù)的子樹(shù)有左右順序之分

五種形態(tài)

a：空樹(shù)；b：只有一個(gè)結(jié)點(diǎn)；c：有一個(gè)結(jié)點(diǎn)，只有一個(gè)左子樹(shù)；d：有一個(gè)結(jié)點(diǎn)，只有一個(gè)右子樹(shù)，e：有一個(gè)結(jié)點(diǎn)，有左右子樹(shù)

二叉樹(shù)的子樹(shù)有左右順序之分

特殊形態(tài)

• 斜二叉樹(shù)

只有左兒子或右兒子

• 完美二叉樹(shù)（滿二叉樹(shù)）

除最后一層葉節(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)

• 完全二叉樹(shù)

有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中結(jié)點(diǎn)按從上至下，從左到右順序進(jìn)行編號(hào)，編號(hào)為 i （1 ≤ \leq ≤i ≤ \leq ≤n）結(jié)點(diǎn)與滿二叉樹(shù)中編號(hào)為 i 結(jié)點(diǎn)在二叉樹(shù)中位置相同

重要性質(zhì)

• 一個(gè)二叉樹(shù)第 i 層的大結(jié)點(diǎn)樹(shù)為：2^i-1,i ≥ \geq ≥ 1

• 深度為 k 的二叉樹(shù)有大結(jié)點(diǎn)總數(shù)為：2^k-1，k ≥ \geq ≥ 1

• 操作集：BT ∈ \in ∈BinTree，item ∈ \in ∈int

主要操作有

• 判斷BT是否為空
• 遍歷，按某順序訪問(wèn)每個(gè)結(jié)點(diǎn)
• 創(chuàng)建一個(gè)二叉樹(shù)

常見(jiàn)的遍歷方法有

• 先序——根，左子樹(shù)，右子樹(shù)
• 中序——左子樹(shù)，根，右子樹(shù)
• 后序——左子樹(shù)，右子樹(shù)，根
• 層次遍歷——，從上到下，從左到右

1.順序存儲(chǔ)結(jié)構(gòu)

按從上到下，從左到右順序存儲(chǔ)n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)父子關(guān)系：

• 非根結(jié)點(diǎn)（序號(hào) i >1）的父結(jié)點(diǎn)的序號(hào)是[i/2]（向下取整）
• 結(jié)點(diǎn)（序號(hào)為 i ）的左孩子結(jié)點(diǎn)的序號(hào)是2i（若2 i ≤ \leq ≤ n，否則沒(méi)有左孩子）
• 結(jié)點(diǎn)（序號(hào)為 i ）的右孩子結(jié)點(diǎn)的序號(hào)是2i+1（若2 i +1 ≤ \leq ≤ n ，否則沒(méi)有右孩子）

一般二叉樹(shù)會(huì)造成空間浪費(fèi)

2.鏈?zhǔn)酱鎯?chǔ)

typedef struct TreeNode{
	int Data;  // 存值
    BinTree Left;   //左兒子結(jié)點(diǎn)
    BinTree Right;  //右兒子結(jié)點(diǎn)
}*BinTree;

---

今天18歲生日，此博客由杜老板贊助發(fā)布

你是否還在尋找穩(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)查看詳情吧

標(biāo)題名稱：樹(shù)的基本概念-創(chuàng)新互聯(lián)
文章路徑：http://www.yijiale78.com/article46/cesghg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、網(wǎng)頁(yè)設(shè)計(jì)公司、網(wǎng)站維護(hù)、App開(kāi)發(fā)、移動(dòng)網(wǎng)站建設(shè)、面包屑導(dǎo)航

廣告

聲明：本網(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)