樹 樹的定義

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

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

當n=0時，稱為空樹

特征

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

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

基本術(shù)語

• 結(jié)點的度（Degree）：結(jié)點的子樹個數(shù)

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

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

• 父結(jié)點（Parent）：有子樹的結(jié)點是其子樹的根結(jié)點的父結(jié)點

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

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

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

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

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

• 子孫結(jié)點（Descendant）：某一結(jié)點的子樹中的所有結(jié)點是這個結(jié)點的子孫

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

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

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

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

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

二叉樹

即度為2的樹

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

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

二叉樹定義

二叉樹 T ：一個有窮的結(jié)點集合

這個集合可以為空

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

五種形態(tài)

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

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

特殊形態(tài)

• 斜二叉樹

只有左兒子或右兒子

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

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

• 完全二叉樹

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

重要性質(zhì)

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

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

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

主要操作有

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

常見的遍歷方法有

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

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

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

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

一般二叉樹會造成空間浪費

2.鏈式存儲

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

---

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

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

標題名稱：樹的基本概念-創(chuàng)新互聯(lián)
文章路徑：http://chinadenli.net/article46/cesghg.html

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

廣告

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