在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。
二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)；對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n_0，度為2的結(jié)點(diǎn)數(shù)為n_2，則n_0=n_2+1。
一棵深度為k，且有2^k-1個(gè)節(jié)點(diǎn)稱之為滿二叉樹；深度為k，有n個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹中，序號(hào)為1至n的節(jié)點(diǎn)對(duì)應(yīng)時(shí)，稱之為完全二叉樹。
從上圖中可以看出 二叉樹一個(gè)左指針一個(gè)右指針 每一個(gè)節(jié)點(diǎn) 最多有兩個(gè)分叉
下面來(lái)寫一個(gè)數(shù)組里的元素按照大小規(guī)律放入二叉樹中的示范：
var arr = [123,12,2,14,144,1245,1,546,568,234,36,42,3467];
左指針?lè)判?右指針?lè)糯?/p>
先把 第一個(gè)元素 放入根節(jié)點(diǎn) 1圖
然后放入 第二個(gè)元素 12 12比123小 所以放在 123的左邊? ? ? ? ? ????2圖
接下來(lái)放第三個(gè)元素 先和根節(jié)點(diǎn)相比 2比123 小 所以去左邊 左邊已經(jīng)有了 就和左邊第一個(gè)先相比一下 2比12小 所以 2放在 12的左邊? ? ? ? ? ? ? ? ? 3圖
接下來(lái)放第四個(gè) 14? 還是先和 根結(jié)點(diǎn)相比 比 123 小在和左邊的12相比 比12 大 所以 放在 12右邊????????? 4圖
再放第五個(gè) 144 先和根節(jié)點(diǎn)相比 比 123 大 然后去根節(jié)點(diǎn)右邊 根結(jié)點(diǎn)右邊沒(méi)有節(jié)點(diǎn) 那么直接放在根節(jié)點(diǎn)右邊即可? 5 圖
然后同樣的理論 放第六個(gè)
第七個(gè)
第八個(gè)
第九個(gè)
最后全部放入 就是這個(gè)樣子
我們按照 先左 再根 再右的 遍歷方法（中序遍歷，前序和后序會(huì)在后面的章節(jié)講到）來(lái)進(jìn)行遍歷
注意：有兩個(gè)分叉的 就可以成為 根 其中 12 1245 546 還有123這是最根本的根 父根
就有了? 1，2，12，14，36，42，123，144，234，546，568，1245，3467 從小到大排好的順序。
下面用js來(lái)寫一個(gè)二叉樹：
先建立一個(gè)節(jié)點(diǎn)方法：
function Node(value){
? ? ? ? this.value = value;//作為根結(jié)點(diǎn)的值 所以創(chuàng)建節(jié)點(diǎn)的一瞬間 就變成了根節(jié)點(diǎn)
? ? ? ? this.left = null;//左指針
? ? ? ? this.right = null;//右指針
? ? ? ? this.add = function(value){ //插入節(jié)點(diǎn)的方法
? ? ? ? ? ? ? ? if(value<this.value){? //先判斷一下傳入的值是否小于根節(jié)點(diǎn)的值 如果小于 就去右面操作 不小于 就去左邊操作
? ? ? ? ? ? ? ? ? ? ? ? if(this.left!=null){ //如果右指針已經(jīng)有節(jié)點(diǎn)了 那么 用右指針去調(diào)用 add 直到 右邊或者左邊沒(méi)有值了
? ? ? ? ? ? ? ? ? ? ? ? ? ? this.left.add(value);
????????????????????????}else{
? ? ? ? ? ? ? ? ? ? ? ? ? ? this.left = new Node(value);
????????????????????????}
????????????????}else{
? ? ? ? ? ? ? ? ? ? ?if(this.right!=null){//如果左指針已經(jīng)有節(jié)點(diǎn)了 那么 用左指針去調(diào)用 add 直到 右邊或者左邊沒(méi)有值了
? ? ? ? ? ? ? ? ? ? ? ? ? ?this.right.add(value);
? ? ? ? ? ? ? ? ? ? ?}else{
? ? ? ? ? ? ? ? ? ? ? ? ? ? this.right = new Node(value);
? ? ? ? ? ? ? ? ? ? ?}
????????????????}
????????}
? ? ? ? this.iterate = function(arr){ //中序遍歷 將一個(gè)數(shù)組傳入這個(gè)方法中，用于接受遍歷的值
? ? ? ? ? ? if(this.left!=null){//先判斷右邊有沒(méi)有節(jié)點(diǎn) 如果有 就再次調(diào)用iterate方法 一直到右邊沒(méi)有的時(shí)候 把值賦給arr 這個(gè)過(guò)程結(jié)束時(shí) 會(huì)把最根節(jié)點(diǎn)右邊所有的值排好序 給arr
? ? ? ? ? ? ? ? this.left.iterate(arr);
? ? ? ? ? ? }
? ? ? ? ? ? arr.push(this.value);
? ? ? ? ? ? if(this.right!=null){//然后再判斷左邊
? ? ? ? ? ? ? ? this.right.iterate(arr);
????????????}
????????}
}
