二叉樹(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)的路徑