redis做緩存的網(wǎng)站并發(fā)數(shù)百度推廣關(guān)鍵詞價(jià)格查詢(xún)
二叉樹(shù)-數(shù)據(jù)結(jié)構(gòu)
二叉樹(shù)是屬性結(jié)構(gòu)的一個(gè)重要類(lèi)型。
如下圖二叉樹(shù)形狀
二叉樹(shù)特征如下:
1.二叉樹(shù)由 n(n >= 0) 個(gè)節(jié)點(diǎn)組成
2.如果 n 為 0,則為空樹(shù)
3.如果 n = 1,則只有一個(gè)節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)(root)
4.每個(gè)節(jié)點(diǎn)最多有兩個(gè)節(jié)點(diǎn),節(jié)點(diǎn)分為左子樹(shù)和右子樹(shù)
5.所有左子樹(shù)和右子樹(shù)自身也必須是二叉樹(shù)
如上圖
節(jié)點(diǎn)6 是 跟節(jié)點(diǎn) root
節(jié)點(diǎn)6 的左子樹(shù)和右子樹(shù) 分別是 節(jié)點(diǎn)4 和 節(jié)點(diǎn)8
名詞概念:
節(jié)點(diǎn):包含一個(gè)數(shù)據(jù)元素 及指向若干個(gè)子樹(shù) 信息
節(jié)點(diǎn)的度:一個(gè)節(jié)點(diǎn)擁有子樹(shù)的數(shù)量稱(chēng)為節(jié)點(diǎn)的度
葉子節(jié)點(diǎn):也稱(chēng)為終端節(jié)點(diǎn),沒(méi)有子樹(shù)的節(jié)點(diǎn)或者 度為零的節(jié)點(diǎn)
分支節(jié)點(diǎn):也成非終端節(jié)點(diǎn),有子樹(shù)的節(jié)點(diǎn)或者 度不為零的節(jié)點(diǎn)
樹(shù)的度:樹(shù)中所有節(jié)點(diǎn)的度的最大值
樹(shù)的層次:從根節(jié)點(diǎn)開(kāi)始,假設(shè)根節(jié)點(diǎn)是第一層,根節(jié)點(diǎn)的子節(jié)點(diǎn)為第二層,一次類(lèi)推,如果某一個(gè)節(jié)點(diǎn)位于第L層,則其子節(jié)點(diǎn)位于第 L+1層
樹(shù)的深度:也成樹(shù)的高度,樹(shù)中所有節(jié)點(diǎn)的層次最大值稱(chēng)為樹(shù)的深度
節(jié)點(diǎn)的深度:從根節(jié)點(diǎn)到節(jié)點(diǎn)的路徑長(zhǎng)度
節(jié)點(diǎn)的高度:從節(jié)點(diǎn)到其子樹(shù)葉子節(jié)點(diǎn)最長(zhǎng)的路徑