99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話：13121318867

登錄
首頁(yè)精彩閱讀工具 | Python數(shù)據(jù)結(jié)構(gòu)：樹(shù)的基本概念
工具 | Python數(shù)據(jù)結(jié)構(gòu)：樹(shù)的基本概念
2016-06-06
收藏
樹(shù)的例子

樹(shù)（Tree）在計(jì)算機(jī)科學(xué)里應(yīng)用廣泛，包括操作系統(tǒng)，圖形學(xué)，數(shù)據(jù)庫(kù)和計(jì)算機(jī)網(wǎng)絡(luò)。樹(shù)和真正的樹(shù)有許多相似的地方，也包括根、樹(shù)枝和葉子，它們的不同在于計(jì)算機(jī)中的樹(shù)的根在頂層而它的葉子在底部。

在我們開(kāi)始學(xué)習(xí)樹(shù)之前，讓我們先來(lái)看看幾個(gè)常見(jiàn)的關(guān)于樹(shù)的例子。首先讓我們看看生物學(xué)中的分類。圖 1 是一個(gè)動(dòng)物分類的例子，從中我們可以看出樹(shù)的幾個(gè)特點(diǎn)。第一，這個(gè)例子說(shuō)明樹(shù)是分級(jí)的，這里分級(jí)的意思是樹(shù)的頂層部分更加寬泛，而底部更加具體。在這個(gè)例子中，最上層的是“界”，它下面的一層（上層的子級(jí)）是“門(mén)”，然后是“綱”等等。但是，無(wú)論我們細(xì)分到多少層，這里面包含的生命體也都是動(dòng)物。

圖 1：一些動(dòng)物的分類樹(shù)

我們注意到可以從樹(shù)的頂層開(kāi)始然后沿著圓圈和箭頭構(gòu)成的一條路徑到達(dá)樹(shù)的底層。在樹(shù)的每一層我們都可以問(wèn)自己一個(gè)問(wèn)題，然后沿著相符的那條路徑繼續(xù)下去。比如我們可以問(wèn) “這個(gè)動(dòng)物是脊椎動(dòng)物還是無(wú)脊椎動(dòng)物”，如果回答是“脊椎動(dòng)物”我們就沿著脊椎動(dòng)物這條路下去然后接著問(wèn)“這個(gè)脊椎動(dòng)物是哺乳動(dòng)物嗎”，如果回答“不是哺乳動(dòng)物”我們就卡在這里了（不過(guò)僅限于這個(gè)簡(jiǎn)單的例子會(huì)有這種情況）。當(dāng)我們到達(dá)哺乳動(dòng)物這一層的時(shí)候我們問(wèn)自己“這個(gè)哺乳動(dòng)物是靈長(zhǎng)類還是食肉動(dòng)物”。我們可以沿著路徑一直走下去直到樹(shù)的最底層，這也就能看到動(dòng)物的名稱了。

樹(shù)的第二個(gè)特點(diǎn)是一個(gè)節(jié)點(diǎn)（node）的所有子節(jié)點(diǎn)（children）和另一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)是完全獨(dú)立的。比如“貓屬”有兩個(gè)子節(jié)點(diǎn)“家生”和“野生”，“蠅屬”中也有一個(gè)“家生”，但它和“貓屬”中的“家生”完全不同而且相互獨(dú)立。這意味著我們可以在不影響“貓屬” 的子節(jié)點(diǎn)的情況下更改“蠅屬”的子節(jié)點(diǎn)。

樹(shù)的第三個(gè)特點(diǎn)就是每個(gè)它的葉節(jié)點(diǎn)（leaf）都是不同的。對(duì)每一種動(dòng)物，我們都可以從根節(jié)點(diǎn)（root）開(kāi)始沿著一條特定的路徑找到它對(duì)應(yīng)的葉節(jié)點(diǎn)，并把它和其他動(dòng)物區(qū)分開(kāi)，例如對(duì)于家貓，我們可以沿著動(dòng)物界——脊索動(dòng)物門(mén)——哺乳動(dòng)物綱——食肉動(dòng)物目——貓科——貓屬——家貓找到它。

另一個(gè)樹(shù)的例子就是你每天都會(huì)用到的文件系統(tǒng)。在文件系統(tǒng)中，磁盤(pán)的分支或者說(shuō)子目錄都是運(yùn)用了樹(shù)來(lái)構(gòu)建的。圖 2 展示了Unix文件系統(tǒng)的部分的分層情況。

圖 2 ：Unix文件系統(tǒng)的部分的分層情況

這個(gè)樹(shù)的文件系統(tǒng)和真正的樹(shù)也非常相像。你可以從根節(jié)點(diǎn)出發(fā)沿著一條路徑到任意分支。這條路徑會(huì)把這個(gè)子分支（包括它里面的所有文件）和其他分支區(qū)別開(kāi)。樹(shù)的另一重要特點(diǎn)，就是你可以將樹(shù)下層的所有部分（叫做子樹(shù)subtree）移動(dòng)到樹(shù)的另一位置而不影響更下層的情況，這是由樹(shù)的分級(jí)方式?jīng)Q定的。例如，我們可以將所有標(biāo)注/etc的子樹(shù)從根節(jié)點(diǎn)下移動(dòng)到usr/下面。這樣做會(huì)將 httpd 的路徑從/etc/httpd改變成/usr/etc/httpd，但是對(duì)httpd的內(nèi)容和子節(jié)點(diǎn)的內(nèi)容不會(huì)有影響。

最后一個(gè)樹(shù)的例子是一個(gè)網(wǎng)頁(yè)。下圖是一個(gè)利用超文本標(biāo)記語(yǔ)言（HTML）編寫(xiě)的簡(jiǎn)單網(wǎng)頁(yè)。圖 3 是構(gòu)成網(wǎng)頁(yè)的超文本標(biāo)記語(yǔ)言中的標(biāo)簽相互關(guān)聯(lián)關(guān)系所構(gòu)成的樹(shù)。

圖 3 ：網(wǎng)頁(yè)的標(biāo)記符之間的相互關(guān)聯(lián)所構(gòu)成的樹(shù)

上面的超文本標(biāo)記的代碼和它對(duì)應(yīng)的樹(shù)說(shuō)明了另一種分級(jí)方式。我們發(fā)現(xiàn)樹(shù)的每一層都對(duì)應(yīng)超文本標(biāo)記符的一層嵌套。代碼的第一個(gè)標(biāo)記符是<html>同時(shí)最后一個(gè)是</html>。這一頁(yè)中所有其他的標(biāo)記符也都是成對(duì)的。試一下你就會(huì)發(fā)現(xiàn)這種嵌套的特點(diǎn)在樹(shù)的每一層都是成立的。

術(shù)語(yǔ)表與定義

現(xiàn)在我們已經(jīng)看了幾個(gè)樹(shù)的例子了，現(xiàn)在正式定義樹(shù)以及構(gòu)成它的要素。

節(jié)點(diǎn)（Node）

節(jié)點(diǎn)是樹(shù)的基本構(gòu)成部分。它可能有其他專屬的名稱，我們稱之為“鍵（key）”。一個(gè)節(jié)點(diǎn)也可能有更多的信息，我們稱之為“負(fù)載”。雖然負(fù)載信息和樹(shù)的許多算法并不直接相關(guān)，但是它對(duì)于樹(shù)的應(yīng)用至關(guān)重要。

邊（Edge）

邊也是樹(shù)的基本構(gòu)成部分。邊連接兩個(gè)節(jié)點(diǎn)，并表示它們之間存在聯(lián)系。除了根節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都有且只有一條與其他節(jié)點(diǎn)相連的入邊（指向該節(jié)點(diǎn)的邊），每個(gè)節(jié)點(diǎn)可能有許多條出邊（從該節(jié)點(diǎn)指向其他節(jié)點(diǎn)的邊）。

根節(jié)點(diǎn)（Root）

根節(jié)點(diǎn)是樹(shù)種中唯一一個(gè)沒(méi)有入邊的節(jié)點(diǎn)。在圖 2 中，“/”是樹(shù)的根節(jié)點(diǎn)。

路徑（Path）

路徑是由邊連接起來(lái)的節(jié)點(diǎn)的有序排列。例如：（動(dòng)物界——脊索動(dòng)物門(mén)——哺乳動(dòng)物綱——食肉動(dòng)物目——貓科——貓屬——家貓）就是一條路徑。

子節(jié)點(diǎn)集（Children）

當(dāng)一個(gè)節(jié)點(diǎn)的入邊來(lái)自另一個(gè)節(jié)點(diǎn)時(shí)，我們稱前者是后者的子節(jié)點(diǎn)，同一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)構(gòu)成子節(jié)點(diǎn)集。在圖 2 中，節(jié)點(diǎn)log/，spool/，yp/構(gòu)成節(jié)點(diǎn)var/的子節(jié)點(diǎn)集。

父節(jié)點(diǎn)（Parent）

一個(gè)節(jié)點(diǎn)是它出邊所連接的所有節(jié)點(diǎn)的父節(jié)點(diǎn)。在圖 2 中，節(jié)點(diǎn)var/是節(jié)點(diǎn)log/，spool/，yp/的父節(jié)點(diǎn)。

兄弟節(jié)點(diǎn)（Sibling）

同一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)互為兄弟節(jié)點(diǎn)，在文件系統(tǒng)樹(shù)中節(jié)點(diǎn)etc/和節(jié)點(diǎn)usr/是兄弟節(jié)點(diǎn)。

子樹(shù)（Subtree）

子樹(shù)是一個(gè)父節(jié)點(diǎn)的某個(gè)子節(jié)點(diǎn)的所有邊和后代節(jié)點(diǎn)所構(gòu)成的集合。

葉節(jié)點(diǎn)（Leaf Node）

沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)成為稱為葉節(jié)點(diǎn)。例如圖 1 中的“人”和“黑猩猩”就是葉節(jié)點(diǎn)。

層數(shù)（Level）

一個(gè)節(jié)點(diǎn)的層數(shù)是指從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑中的邊的數(shù)目。例如，圖 1 中“貓屬”的層數(shù)是 5，定義根節(jié)點(diǎn)的層數(shù)為 0。

高度（Height）

樹(shù)的高度等于所有節(jié)點(diǎn)的層數(shù)的最大值。圖 2 中樹(shù)的高度為 2。

我們已經(jīng)定義好所需的術(shù)語(yǔ)了，現(xiàn)在可以正式定義樹(shù)了。我們將用兩種方式定義，一種需要用到節(jié)點(diǎn)和邊，而另一種更為有效的定義方式是利用遞歸定義。

定義一：樹(shù)是節(jié)點(diǎn)和連接節(jié)點(diǎn)的邊的集合，它有以下特征：

有一個(gè)節(jié)點(diǎn)被設(shè)計(jì)為根節(jié)點(diǎn)。
除了根節(jié)點(diǎn)的每一個(gè)節(jié)點(diǎn) n，都通過(guò)一條邊與它唯一的父節(jié)點(diǎn)相連。
可以沿著唯一的路徑從根節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)。
如果這個(gè)樹(shù)的每個(gè)節(jié)點(diǎn)都至多有兩個(gè)子節(jié)點(diǎn)，我們稱它為二叉樹(shù)。

圖 4 展示了一個(gè)符合定義一的樹(shù)。每條邊的箭頭指出了連接的方向。


圖 4 ：由節(jié)點(diǎn)和邊構(gòu)成的樹(shù)

定義二：每個(gè)樹(shù)或者為空，或者包含一個(gè)根節(jié)點(diǎn)和 0 個(gè)或多個(gè)子樹(shù)，其中每個(gè)子樹(shù)也符合這樣的定義。每個(gè)子樹(shù)的根節(jié)點(diǎn)和其父樹(shù)的根節(jié)點(diǎn)之間通過(guò)邊相連。圖 5 描繪了這種遞歸定義的樹(shù)。通過(guò)這種樹(shù)的遞歸定義，我們知道圖 5 中的樹(shù)至少有 4 個(gè)節(jié)點(diǎn)，因?yàn)槊總€(gè)三角形所代表的子樹(shù)必須有根。它也可能有更多的節(jié)點(diǎn)，但我們需要更深入的了解這棵樹(shù)來(lái)得到答案。


圖 5 ：遞歸法定義的樹(shù)


文 | wzhvictor  
原文鏈接：https://segmentfault.com/a/1190000004003299

數(shù)據(jù)分析咨詢請(qǐng)掃描二維碼

若不方便掃碼，搜微信號(hào)：CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1：配置參數(shù) // 參數(shù)2：回調(diào)，回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對(duì)象，之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須，不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺(tái)檢測(cè)極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式，包括：float，popup width: "280px", https: true // 更多配置參數(shù)說(shuō)明請(qǐng)參見(jiàn)：http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請(qǐng)輸入'+oInput.attr('placeholder')+'！'; var errTxt = '請(qǐng)輸入正確的'+oInput.attr('placeholder')+'！'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }