這篇文章主要講解了“什么是二叉樹(shù)與多叉樹(shù)”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來(lái)研究和學(xué)習(xí)“什么是二叉樹(shù)與多叉樹(shù)”吧!
專注于為中小企業(yè)提供成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)靖邊免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都,凝聚了一批互聯(lián)網(wǎng)行業(yè)人才,有力地推動(dòng)了上千多家企業(yè)的穩(wěn)健成長(zhǎng),幫助中小企業(yè)通過(guò)網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。
1、數(shù)組與鏈表
數(shù)組結(jié)構(gòu)
數(shù)組存儲(chǔ)是通過(guò)下標(biāo)方式訪問(wèn)元素,查詢速度快,如果數(shù)組元素是有序的,還可使用二分查找提高檢索速度;如果添加新元素可能會(huì)導(dǎo)致多個(gè)下標(biāo)移動(dòng),效率較低;
鏈表結(jié)構(gòu)
鏈表存儲(chǔ)元素,對(duì)于元素添加和刪除效率高,但是遍歷元素每次都需要從頭結(jié)點(diǎn)開(kāi)始,效率特別低;
樹(shù)形結(jié)構(gòu)能同時(shí)相對(duì)提高數(shù)據(jù)存儲(chǔ)和讀取的效率。
2、樹(shù)結(jié)構(gòu)概念
根節(jié)點(diǎn):樹(shù)的根源,沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn),如上圖A節(jié)點(diǎn);
兄弟節(jié)點(diǎn):擁有同一父節(jié)點(diǎn)的子節(jié)點(diǎn)。如圖B與C點(diǎn);
葉子節(jié)點(diǎn):沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。如圖DEFG節(jié)點(diǎn);
樹(shù)的高度:最大層數(shù),如圖為3層;
路徑:從root根節(jié)點(diǎn)找到指定節(jié)點(diǎn)的路線;
樹(shù)形結(jié)構(gòu)是一層次的嵌套結(jié)構(gòu)。一個(gè)樹(shù)形結(jié)構(gòu)的外層和內(nèi)層有相似的結(jié)構(gòu),所以這種結(jié)構(gòu)多可以遞歸的表示。經(jīng)典數(shù)據(jù)結(jié)構(gòu)中的各種樹(shù)狀圖是一種典型的樹(shù)形結(jié)構(gòu):一顆樹(shù)可以簡(jiǎn)單的表示為根, 左子樹(shù), 右子樹(shù)。 左子樹(shù)和右子樹(shù)又有自己的子樹(shù)。
樹(shù)的種類有很多,二叉樹(shù)(BinaryTree)是樹(shù)形結(jié)構(gòu)的一個(gè)重要類型,每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)的一種形式稱為二叉樹(shù),二叉樹(shù)的子節(jié)點(diǎn)分為左節(jié)點(diǎn)和右節(jié)點(diǎn),許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)形式。
完全二叉樹(shù)
二叉樹(shù)的所有葉子節(jié)點(diǎn)都在最后一層或者倒數(shù)第二層,而且最后一層的葉子節(jié)點(diǎn)在左邊連續(xù),倒數(shù)第二 層的葉子節(jié)點(diǎn)在右邊連續(xù),我們稱為完全二叉樹(shù)
滿二叉樹(shù)
當(dāng)二叉樹(shù)的所有葉子節(jié)點(diǎn)都在最后一層,并且結(jié)點(diǎn)總數(shù)= 2^n -1 , n 為層數(shù),則稱為滿二叉樹(shù)。
平衡二叉樹(shù)
平衡二叉樹(shù)指的是,任意節(jié)點(diǎn)的子樹(shù)的高度差的絕對(duì)值都小于等于1,并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù),常見(jiàn)的符合平衡樹(shù)的有,B樹(shù)(多路平衡搜索樹(shù))、AVL樹(shù)(二叉平衡搜索樹(shù))等。
二叉查找樹(shù)
二叉查找樹(shù)(BinarySearchTree)不但二叉樹(shù),同時(shí)滿足一定的有序性:節(jié)點(diǎn)的左子節(jié)點(diǎn)比自己小,節(jié)點(diǎn)的右子節(jié)點(diǎn)比自己大。
1、基礎(chǔ)代碼
節(jié)點(diǎn)代碼
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 +'}'; }}
樹(shù)結(jié)構(gòu)代碼
class BinaryTree01 { private TreeNode root ; }
2、遍歷與查找
前序遍歷查找
先處理當(dāng)前結(jié)點(diǎn)的數(shù)據(jù),再依次遞歸遍歷左子樹(shù)和右子樹(shù);
public void prevTraverse() { // 輸出父結(jié)點(diǎn) System.out.println(this); // 向左子樹(shù)遞歸前序遍歷 if(this.leftNode != null) { this.leftNode.prevTraverse(); } // 向右子樹(shù)遞歸前序遍歷 if(this.rightNode != null) { this.rightNode.prevTraverse(); }}public TreeNode prevSearch(String num) { //比較當(dāng)前結(jié)點(diǎn) if(this.num.equals(num)) { return this ; } // 遞歸遍歷左子樹(shù)查找 TreeNode findNode = null; if(this.leftNode != null) { findNode = this.leftNode.prevSearch(num); } // 左子樹(shù)遍歷命中 if(findNode != null) { return findNode ; } // 遞歸遍歷右子樹(shù)查找 if(this.rightNode != null) { findNode = this.rightNode.prevSearch(num); } return findNode ; }
中序遍歷查找
先遞歸遍歷左子樹(shù),再處理父節(jié)點(diǎn),再遞歸遍歷右子樹(shù)
public void midTraverse() { // 向左子樹(shù)遞歸中序遍歷 if(this.leftNode != null) { this.leftNode.midTraverse(); } // 輸出父結(jié)點(diǎn) System.out.println(this); // 向右子樹(shù)遞歸中序遍歷 if(this.rightNode != null) { this.rightNode.midTraverse(); }}public TreeNode midSearch(String num) { // 遞歸遍歷左子樹(shù)查找 TreeNode findNode = null; if(this.leftNode != null) { findNode = this.leftNode.midSearch(num); } if(findNode != null) { return findNode ; } // 比較當(dāng)前結(jié)點(diǎn) if(this.num.equals(num)) { return this ; } // 遞歸遍歷右子樹(shù)查找 if(this.rightNode != null) { findNode = this.rightNode.midSearch(num); } return findNode ; }
后序遍歷查找
先遞歸遍歷左子樹(shù),再遞歸遍歷右子樹(shù),最后處理父節(jié)點(diǎn);
public void lastTraverse() { // 向左子樹(shù)遞歸后序遍歷 if(this.leftNode != null) { this.leftNode.lastTraverse(); } // 向右子樹(shù)遞歸后序遍歷 if(this.rightNode != null) { this.rightNode.lastTraverse(); } // 輸出父結(jié)點(diǎn) System.out.println(this); }public TreeNode lastSearch(String num) { // 遞歸遍歷左子樹(shù)查找 TreeNode findNode = null; if(this.leftNode != null) { findNode = this.leftNode.lastSearch(num); } if(findNode != null) { return findNode ; } // 遞歸遍歷右子樹(shù)查找 if(this.rightNode != null) { findNode = this.rightNode.lastSearch(num); } if(findNode != null) { return findNode ; } // 比較當(dāng)前結(jié)點(diǎn) if(this.num.equals(num)) { return this ; } return null ; }
3、刪除節(jié)點(diǎn)
如果當(dāng)前刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn),則可以直接刪除該節(jié)點(diǎn);如果刪除的節(jié)點(diǎn)是非葉子節(jié)點(diǎn),則刪除該節(jié)點(diǎn)樹(shù)。
public void deleteNode(String num) { // 判斷左節(jié)點(diǎn)是否刪除 if(this.leftNode != null && this.leftNode.num.equals(num)) { this.leftNode = null ; return ; } // 判斷右節(jié)點(diǎn)是否刪除 if(this.rightNode != null && this.rightNode.num.equals(num)) { this.rightNode = null; return ; } // 向左子樹(shù)遍歷進(jìn)行遞歸刪除 if(this.leftNode != null) { this.leftNode.deleteNode(num); } // 向右子樹(shù)遍歷進(jìn)行遞歸刪除 if(this.rightNode != null) { this.rightNode.deleteNode(num); }}
多叉樹(shù)是指一個(gè)父節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn),但是一個(gè)子節(jié)點(diǎn)依舊遵循一個(gè)父節(jié)點(diǎn)定律,通常情況下,二叉樹(shù)的實(shí)際應(yīng)用高度太高,可以通過(guò)多叉樹(shù)來(lái)簡(jiǎn)化對(duì)數(shù)據(jù)關(guān)系的描述。
例如:Linux文件系統(tǒng),組織架構(gòu)關(guān)系,角色菜單權(quán)限管理系統(tǒng)等,通常都基于多叉樹(shù)來(lái)描述。
感謝各位的閱讀,以上就是“什么是二叉樹(shù)與多叉樹(shù)”的內(nèi)容了,經(jīng)過(guò)本文的學(xué)習(xí)后,相信大家對(duì)什么是二叉樹(shù)與多叉樹(shù)這一問(wèn)題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián),小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
當(dāng)前文章:什么是二叉樹(shù)與多叉樹(shù)
轉(zhuǎn)載來(lái)源:http://muchs.cn/article16/iheidg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供軟件開(kāi)發(fā)、網(wǎng)站營(yíng)銷、動(dòng)態(tài)網(wǎng)站、網(wǎng)站設(shè)計(jì)、搜索引擎優(yōu)化、關(guān)鍵詞優(yōu)化
聲明:本網(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)