數(shù)據(jù)結(jié)構(gòu)中的樹(shù)，是對(duì)現(xiàn)實(shí)世界中的樹(shù)的一層簡(jiǎn)化： 把樹(shù)根抽象為根節(jié)點(diǎn)，述職抽象為邊，樹(shù)枝的兩個(gè)端點(diǎn)抽象為節(jié)點(diǎn)， 樹(shù)葉抽象為葉字節(jié)點(diǎn)。抽象后的樹(shù)結(jié)構(gòu)如下：

image.png

把這棵樹(shù)抽象顛倒一下就得到了計(jì)算機(jī)中的樹(shù)結(jié)構(gòu)：

image.png

• 樹(shù)的層次計(jì)算規(guī)則： 跟節(jié)點(diǎn)所在的層為第一層，其自己點(diǎn)所在的為第二層，以此類推
• 結(jié)點(diǎn)和樹(shù)的“高度”計(jì)算規(guī)則：葉子結(jié)點(diǎn)高度記為1，每向上一層高度就加1，逐層向上累加至目標(biāo)結(jié)點(diǎn)時(shí)，所得到的的值就是目標(biāo)結(jié)點(diǎn)的高度。樹(shù)中結(jié)點(diǎn)的最大高度，稱為“樹(shù)的高度”。
• 度的概念： 一個(gè)節(jié)點(diǎn)開(kāi)叉出去多少子樹(shù)，即為度
• 葉子節(jié)點(diǎn)就是度為0的結(jié)點(diǎn)

二叉樹(shù)

二叉樹(shù)是指滿足一下要求的樹(shù)

• 它可以沒(méi)有根節(jié)點(diǎn)作為一棵空樹(shù)存在
• 如果他不是空樹(shù)，那么他必須有根節(jié)點(diǎn)，左子樹(shù)和右子樹(shù)組成，且左右子樹(shù)都是二叉樹(shù)

image.png

二叉樹(shù)的編碼實(shí)現(xiàn)

在js中定二叉樹(shù)，他的結(jié)構(gòu)分為3塊

• 數(shù)據(jù)域
• 左側(cè)子節(jié)點(diǎn)的引用
• 右側(cè)子節(jié)點(diǎn)的引用

//二叉樹(shù)節(jié)點(diǎn)的構(gòu)造函數(shù)
function TreeNode(val){
  this.val = val
  this.left = this.right = null
}

當(dāng)需要新建一個(gè)二叉樹(shù)時(shí)，直接調(diào)用構(gòu)造函數(shù)傳入數(shù)據(jù)域的值就行了：

const node = new TreeNode(1)

如此便能得到一個(gè)值為1的二叉樹(shù)節(jié)點(diǎn)，從結(jié)構(gòu)上來(lái)說(shuō)，他張這樣：

image.png

以這個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，我們可以通過(guò)給left、right賦值拓展其子樹(shù)信息，延展出一棵二叉樹(shù)。因此從更加細(xì)化的角度來(lái)看，一棵二叉樹(shù)的形態(tài)實(shí)際是

image.png