樹 樹的定義

樹（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)頁制作以及高縣網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(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)輻射到高縣省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

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

特征

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

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

基本術(shù)語

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

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

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

• 父結(jié)點(diǎn)（Parent）：有子樹的結(jié)點(diǎn)是其子樹的根結(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)

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

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

• 子孫結(jié)點(diǎn)（Descendant）：某一結(jié)點(diǎn)的子樹中的所有結(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

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

樹的表示 兒子 - 兄弟表示法

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

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

二叉樹

即度為2的樹

• Element 存值
• Left 指向左子樹
• Right 指向右子樹

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

二叉樹定義

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

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

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

五種形態(tài)

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

二叉樹的子樹有左右順序之分

特殊形態(tài)

• 斜二叉樹

只有左兒子或右兒子

• 完美二叉樹（滿二叉樹）

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

• 完全二叉樹

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

重要性質(zhì)

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

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

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

主要操作有

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

常見的遍歷方法有

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

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

按從上到下，從左到右順序存儲(chǔ)n個(gè)結(jié)點(diǎn)的完全二叉樹的結(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，否則沒有左孩子）
• 結(jié)點(diǎn)（序號(hào)為 i ）的右孩子結(jié)點(diǎn)的序號(hào)是2i+1（若2 i +1 ≤ \leq ≤ n ，否則沒有右孩子）

一般二叉樹會(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ù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

標(biāo)題名稱：樹的基本概念-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://weahome.cn/article/cesghg.html