樹的基本概念-創(chuàng)新互聯

樹 樹的定義

樹（Tree）：n（n$\geq$0）個結點構成的有限集合

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

當n=0時，稱為空樹

特征

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

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

  • 結點的度（Degree）：結點的子樹個數

  • 樹的度：樹的所有結點中大的度數

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

  • 父結點（Parent）：有子樹的結點是其子樹的根結點的父結點

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

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

  • 路徑：從結點n1到nk的路徑為一個結點序列n1，n2…. nk，ni是n+1的父結點

  • 路徑長度：路徑所包含邊的個數

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

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

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

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

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

image-20221130222844807

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

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

二叉樹

即度為2的樹

image-20221130223046184

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

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

image-20221130223154792

二叉樹定義

二叉樹 T ：一個有窮的結點集合

這個集合可以為空

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

五種形態(tài)

image-20221201152616240

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

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

特殊形態(tài)
  • 斜二叉樹

只有左兒子或右兒子

image-20221201152733537
  • 完美二叉樹（滿二叉樹）

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

image-20221201152903267

  • 完全二叉樹

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

image-20221201153321215

重要性質

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

  • 深度為 k 的二叉樹有大結點總數為：2k-1，k ≥ \geq ≥ 1

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

主要操作有

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

常見的遍歷方法有

  • 先序——根，左子樹，右子樹
  • 中序——左子樹，根，右子樹
  • 后序——左子樹，右子樹，根
  • 層次遍歷——，從上到下，從左到右
1.順序存儲結構

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

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

image-20221202095002937

image-20221202095015136

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

2.鏈式存儲

image-20221202095049786

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

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

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

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

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

廣告

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

外貿網站制作