您好,登錄后才能下訂單哦!
如何分析python二叉樹與多叉樹,很多新手對此不是很清楚,為了幫助大家解決這個難題,下面小編將為大家詳細(xì)講解,有這方面需求的人可以來學(xué)習(xí)下,希望你能有所收獲。
數(shù)組結(jié)構(gòu)
數(shù)組存儲是通過下標(biāo)方式訪問元素,查詢速度快,如果數(shù)組元素是有序的,還可使用二分查找提高檢索速度;如果添加新元素可能會導(dǎo)致多個下標(biāo)移動,效率較低;
鏈表結(jié)構(gòu)
鏈表存儲元素,對于元素添加和刪除效率高,但是遍歷元素每次都需要從頭結(jié)點(diǎn)開始,效率特別低;
樹形結(jié)構(gòu)能同時(shí)相對提高數(shù)據(jù)存儲和讀取的效率。
根節(jié)點(diǎn):樹的根源,沒有父節(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):沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。如圖DEFG節(jié)點(diǎn);
樹的高度:最大層數(shù),如圖為3層;
路徑:從root根節(jié)點(diǎn)找到指定節(jié)點(diǎn)的路線;
樹形結(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é)點(diǎn)最多只能有兩個子節(jié)點(diǎn)的一種形式稱為二叉樹,二叉樹的子節(jié)點(diǎn)分為左節(jié)點(diǎn)和右節(jié)點(diǎn),許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式。
完全二叉樹
二叉樹的所有葉子節(jié)點(diǎn)都在最后一層或者倒數(shù)第二層,而且最后一層的葉子節(jié)點(diǎn)在左邊連續(xù),倒數(shù)第二 層的葉子節(jié)點(diǎn)在右邊連續(xù),我們稱為完全二叉樹
滿二叉樹
當(dāng)二叉樹的所有葉子節(jié)點(diǎn)都在最后一層,并且結(jié)點(diǎn)總數(shù)= 2^n -1 , n 為層數(shù),則稱為滿二叉樹。
平衡二叉樹
平衡二叉樹指的是,任意節(jié)點(diǎn)的子樹的高度差的絕對值都小于等于1,并且左右兩個子樹都是一棵平衡二叉樹,常見的符合平衡樹的有,B樹(多路平衡搜索樹)、AVL樹(二叉平衡搜索樹)等。
二叉查找樹
二叉查找樹(BinarySearchTree)不但二叉樹,同時(shí)滿足一定的有序性:節(jié)點(diǎn)的左子節(jié)點(diǎn)比自己小,節(jié)點(diǎn)的右子節(jié)點(diǎn)比自己大。
節(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 +'}'; } }
樹結(jié)構(gòu)代碼
class BinaryTree01 { private TreeNode root ; }
前序遍歷查找
先處理當(dāng)前結(jié)點(diǎn)的數(shù)據(jù),再依次遞歸遍歷左子樹和右子樹;
public void prevTraverse() { // 輸出父結(jié)點(diǎn) 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é)點(diǎn) 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é)點(diǎn),再遞歸遍歷右子樹;
public void midTraverse() { // 向左子樹遞歸中序遍歷 if(this.leftNode != null) { this.leftNode.midTraverse(); } // 輸出父結(jié)點(diǎn) 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é)點(diǎn) if(this.num.equals(num)) { return this ; } // 遞歸遍歷右子樹查找 if(this.rightNode != null) { findNode = this.rightNode.midSearch(num); } return findNode ; }
后序遍歷查找
先遞歸遍歷左子樹,再遞歸遍歷右子樹,最后處理父節(jié)點(diǎn);
public void lastTraverse() { // 向左子樹遞歸后序遍歷 if(this.leftNode != null) { this.leftNode.lastTraverse(); } // 向右子樹遞歸后序遍歷 if(this.rightNode != null) { this.rightNode.lastTraverse(); } // 輸出父結(jié)點(diǎn) 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é)點(diǎn) if(this.num.equals(num)) { return this ; } return null ; }
如果當(dāng)前刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn),則可以直接刪除該節(jié)點(diǎn);如果刪除的節(jié)點(diǎn)是非葉子節(jié)點(diǎn),則刪除該節(jié)點(diǎn)樹。
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 ; } // 向左子樹遍歷進(jìn)行遞歸刪除 if(this.leftNode != null) { this.leftNode.deleteNode(num); } // 向右子樹遍歷進(jìn)行遞歸刪除 if(this.rightNode != null) { this.rightNode.deleteNode(num); } }
多叉樹是指一個父節(jié)點(diǎn)可以有多個子節(jié)點(diǎn),但是一個子節(jié)點(diǎn)依舊遵循一個父節(jié)點(diǎn)定律,通常情況下,二叉樹的實(shí)際應(yīng)用高度太高,可以通過多叉樹來簡化對數(shù)據(jù)關(guān)系的描述。例如:Linux文件系統(tǒng),組織架構(gòu)關(guān)系,角色菜單權(quán)限管理系統(tǒng)等,通常都基于多叉樹來描述。
看完上述內(nèi)容是否對您有幫助呢?如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章,請關(guān)注億速云行業(yè)資訊頻道,感謝您對億速云的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。