如何分析python二叉樹與多叉樹，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。
創(chuàng)新互聯(lián)主營(yíng)隆陽(yáng)網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,成都app軟件開發(fā)公司,隆陽(yáng)h5成都微信小程序搭建,隆陽(yáng)網(wǎng)站營(yíng)銷推廣歡迎隆陽(yáng)等地區(qū)企業(yè)咨詢
數(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)開始，效率特別低；
樹形結(jié)構(gòu)能同時(shí)相對(duì)提高數(shù)據(jù)存儲(chǔ)和讀取的效率。
根節(jié)點(diǎn)：樹的根源，沒(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ù)，如圖為3層；
路徑：從root根節(jié)點(diǎn)找到指定節(jié)點(diǎn)的路線；
樹形結(jié)構(gòu)是一層次的嵌套結(jié)構(gòu)。一個(gè)樹形結(jié)構(gòu)的外層和內(nèi)層有相似的結(jié)構(gòu)，所以這種結(jié)構(gòu)多可以遞歸的表示。經(jīng)典數(shù)據(jù)結(jié)構(gòu)中的各種樹狀圖是一種典型的樹形結(jié)構(gòu)：一顆樹可以簡(jiǎn)單的表示為根， 左子樹， 右子樹。 左子樹和右子樹又有自己的子樹。
樹的種類有很多，二叉樹（BinaryTree）是樹形結(jié)構(gòu)的一個(gè)重要類型，每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)的一種形式稱為二叉樹，二叉樹的子節(jié)點(diǎn)分為左節(jié)點(diǎn)和右節(jié)點(diǎn)，許多實(shí)際問(wèn)題抽象出來(lái)的數(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)的子樹的高度差的絕對(duì)值都小于等于1，并且左右兩個(gè)子樹都是一棵平衡二叉樹，常見(jiàn)的符合平衡樹的有，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);
}
}
多叉樹是指一個(gè)父節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)，但是一個(gè)子節(jié)點(diǎn)依舊遵循一個(gè)父節(jié)點(diǎn)定律，通常情況下，二叉樹的實(shí)際應(yīng)用高度太高，可以通過(guò)多叉樹來(lái)簡(jiǎn)化對(duì)數(shù)據(jù)關(guān)系的描述。例如：Linux文件系統(tǒng)，組織架構(gòu)關(guān)系，角色菜單權(quán)限管理系統(tǒng)等，通常都基于多叉樹來(lái)描述。
看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)的支持。
