這篇文章主要講解了“什么是二叉樹與多叉樹”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“什么是二叉樹與多叉樹”吧！

專注于為中小企業(yè)提供成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)靖邊免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了上千多家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

一、樹狀結(jié)構(gòu)

1、數(shù)組與鏈表

數(shù)組結(jié)構(gòu)

數(shù)組存儲是通過下標(biāo)方式訪問元素，查詢速度快，如果數(shù)組元素是有序的，還可使用二分查找提高檢索速度;如果添加新元素可能會導(dǎo)致多個下標(biāo)移動，效率較低;

鏈表結(jié)構(gòu)

鏈表存儲元素，對于元素添加和刪除效率高，但是遍歷元素每次都需要從頭結(jié)點開始，效率特別低;

樹形結(jié)構(gòu)能同時相對提高數(shù)據(jù)存儲和讀取的效率。

2、樹結(jié)構(gòu)概念

• 根節(jié)點：樹的根源，沒有父節(jié)點的節(jié)點，如上圖A節(jié)點;

• 兄弟節(jié)點：擁有同一父節(jié)點的子節(jié)點。如圖B與C點;

• 葉子節(jié)點：沒有子節(jié)點的節(jié)點。如圖DEFG節(jié)點;

• 樹的高度：最大層數(shù)，如圖為3層;

• 路徑：從root根節(jié)點找到指定節(jié)點的路線;

樹形結(jié)構(gòu)是一層次的嵌套結(jié)構(gòu)。一個樹形結(jié)構(gòu)的外層和內(nèi)層有相似的結(jié)構(gòu)，所以這種結(jié)構(gòu)多可以遞歸的表示。經(jīng)典數(shù)據(jù)結(jié)構(gòu)中的各種樹狀圖是一種典型的樹形結(jié)構(gòu)：一顆樹可以簡單的表示為根，  左子樹， 右子樹。 左子樹和右子樹又有自己的子樹。

二、二叉樹模型

樹的種類有很多，二叉樹(BinaryTree)是樹形結(jié)構(gòu)的一個重要類型，每個節(jié)點最多只能有兩個子節(jié)點的一種形式稱為二叉樹，二叉樹的子節(jié)點分為左節(jié)點和右節(jié)點，許多實際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式。

完全二叉樹

二叉樹的所有葉子節(jié)點都在最后一層或者倒數(shù)第二層，而且最后一層的葉子節(jié)點在左邊連續(xù)，倒數(shù)第二 層的葉子節(jié)點在右邊連續(xù)，我們稱為完全二叉樹

滿二叉樹

當(dāng)二叉樹的所有葉子節(jié)點都在最后一層，并且結(jié)點總數(shù)= 2^n -1 , n 為層數(shù)，則稱為滿二叉樹。

平衡二叉樹

平衡二叉樹指的是，任意節(jié)點的子樹的高度差的絕對值都小于等于1，并且左右兩個子樹都是一棵平衡二叉樹，常見的符合平衡樹的有，B樹(多路平衡搜索樹)、AVL樹(二叉平衡搜索樹)等。

二叉查找樹

二叉查找樹(BinarySearchTree)不但二叉樹，同時滿足一定的有序性：節(jié)點的左子節(jié)點比自己小，節(jié)點的右子節(jié)點比自己大。

三、二叉樹編碼

1、基礎(chǔ)代碼

節(jié)點代碼

class TreeNode {     private String num ;     private TreeNode leftNode ;     private TreeNode rightNode ;     public TreeNode(String num) {         this.num = num;     }    @Override     public String toString() {         return "TreeNode{num=" + num +'}';     }}

樹結(jié)構(gòu)代碼

class BinaryTree01 {     private TreeNode root ; }

2、遍歷與查找

前序遍歷查找

先處理當(dāng)前結(jié)點的數(shù)據(jù)，再依次遞歸遍歷左子樹和右子樹;

public void prevTraverse() {     // 輸出父結(jié)點     System.out.println(this);     // 向左子樹遞歸前序遍歷     if(this.leftNode != null) {         this.leftNode.prevTraverse();     }    // 向右子樹遞歸前序遍歷     if(this.rightNode != null) {         this.rightNode.prevTraverse();     }}public TreeNode prevSearch(String num) {    //比較當(dāng)前結(jié)點     if(this.num.equals(num)) {         return this ;     }    // 遞歸遍歷左子樹查找     TreeNode findNode = null;     if(this.leftNode != null) {         findNode = this.leftNode.prevSearch(num);     }    // 左子樹遍歷命中     if(findNode != null) {         return findNode ;     }    // 遞歸遍歷右子樹查找     if(this.rightNode != null) {         findNode = this.rightNode.prevSearch(num);     }    return findNode ; }

中序遍歷查找

先遞歸遍歷左子樹，再處理父節(jié)點，再遞歸遍歷右子樹

public void midTraverse() {     // 向左子樹遞歸中序遍歷     if(this.leftNode != null) {         this.leftNode.midTraverse();     }    // 輸出父結(jié)點     System.out.println(this);     // 向右子樹遞歸中序遍歷     if(this.rightNode != null) {         this.rightNode.midTraverse();     }}public TreeNode midSearch(String num) {    // 遞歸遍歷左子樹查找     TreeNode findNode = null;     if(this.leftNode != null) {         findNode = this.leftNode.midSearch(num);     }    if(findNode != null) {         return findNode ;     }    // 比較當(dāng)前結(jié)點     if(this.num.equals(num)) {         return this ;     }    // 遞歸遍歷右子樹查找     if(this.rightNode != null) {         findNode = this.rightNode.midSearch(num);     }    return findNode ; }

后序遍歷查找

先遞歸遍歷左子樹，再遞歸遍歷右子樹，最后處理父節(jié)點;

public void lastTraverse() {     // 向左子樹遞歸后序遍歷     if(this.leftNode != null) {         this.leftNode.lastTraverse();     }    // 向右子樹遞歸后序遍歷     if(this.rightNode != null) {         this.rightNode.lastTraverse();     }    // 輸出父結(jié)點     System.out.println(this); }public TreeNode lastSearch(String num) {    // 遞歸遍歷左子樹查找     TreeNode findNode = null;     if(this.leftNode != null) {         findNode = this.leftNode.lastSearch(num);     }    if(findNode != null) {         return findNode ;     }    // 遞歸遍歷右子樹查找     if(this.rightNode != null) {         findNode = this.rightNode.lastSearch(num);     }    if(findNode != null) {         return findNode ;     }    // 比較當(dāng)前結(jié)點     if(this.num.equals(num)) {         return this ;     }    return null ; }

3、刪除節(jié)點

如果當(dāng)前刪除的節(jié)點是葉子節(jié)點，則可以直接刪除該節(jié)點;如果刪除的節(jié)點是非葉子節(jié)點，則刪除該節(jié)點樹。

public void deleteNode(String num) {     // 判斷左節(jié)點是否刪除     if(this.leftNode != null && this.leftNode.num.equals(num)) {         this.leftNode = null ;         return ;     }    // 判斷右節(jié)點是否刪除     if(this.rightNode != null && this.rightNode.num.equals(num)) {         this.rightNode = null;         return ;     }    // 向左子樹遍歷進行遞歸刪除     if(this.leftNode != null) {         this.leftNode.deleteNode(num);     }    // 向右子樹遍歷進行遞歸刪除     if(this.rightNode != null) {         this.rightNode.deleteNode(num);     }}

四、多叉樹

多叉樹是指一個父節(jié)點可以有多個子節(jié)點，但是一個子節(jié)點依舊遵循一個父節(jié)點定律，通常情況下，二叉樹的實際應(yīng)用高度太高，可以通過多叉樹來簡化對數(shù)據(jù)關(guān)系的描述。

例如：Linux文件系統(tǒng)，組織架構(gòu)關(guān)系，角色菜單權(quán)限管理系統(tǒng)等，通常都基于多叉樹來描述。

感謝各位的閱讀，以上就是“什么是二叉樹與多叉樹”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對什么是二叉樹與多叉樹這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！

當(dāng)前文章：什么是二叉樹與多叉樹
轉(zhuǎn)載來源：http://sd-ha.com/article16/iheidg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、網(wǎng)站營銷、動態(tài)網(wǎng)站、網(wǎng)站設(shè)計、搜索引擎優(yōu)化、關(guān)鍵詞優(yōu)化

廣告

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