1 學(xué)習(xí)的內(nèi)容
在之前分析finsh shell的時候，看到siblings，隨手一搜，發(fā)現(xiàn)這個是在二叉樹中提到的，所以學(xué)習(xí)一下。
二叉樹，分為完美二叉樹、完全二叉樹和完滿二叉樹。
2 樹
我抄一個定義，鏈接
樹是由結(jié)點或頂點和邊組成的(可能是非線性的)且不存在著任何環(huán)的一種數(shù)據(jù)結(jié)構(gòu)。沒有結(jié)點的樹稱為空(null或empty)樹。一棵非空的樹包括一個根結(jié)點，還(很可能)有多個附加結(jié)點，所有結(jié)點構(gòu)成一個多級分層結(jié)構(gòu)。
這里面提到的結(jié)點，在finsh shell中同樣也提到過，也就是node。這里還是要區(qū)分一下：
節(jié)點和結(jié)點：
- joint和connection為節(jié)點。"節(jié)點"是物理概念，是對實際結(jié)構(gòu)中的一個"節(jié)段"與另一個"節(jié)段"物理連接區(qū)的統(tǒng)稱。
- node是結(jié)點。"結(jié)點"是力學(xué)概念，是在力學(xué)模型上根據(jù)分析需要所設(shè)置的標(biāo)識點或計算點。
姑且可以參考：鏈接
也將樹的一些概念性內(nèi)容貼出來：
| 英文 | 中文 | 含義 |
|---|---|---|
| root | 根 | 樹的頂端結(jié)點 |
| child | 孩子 | 當(dāng)遠(yuǎn)離根(Root)的時候，直接連接到另外一個結(jié)點的結(jié)點被稱之為孩子(Child) |
| parent | 雙親 | 相應(yīng)地，另外一個結(jié)點稱為孩子(child)的雙親 |
| siblings | 兄弟 | 具有同一個雙親(Parent)的孩子(Child)之間互稱為兄弟 |
| ancestor | 祖先 | 結(jié)點的祖先(Ancestor)是從根（Root）到該結(jié)點所經(jīng)分支(Branch)上的所有結(jié)點 |
| descendant | 子孫 | 反之，以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫(Ancestor) |
| leaf | 葉子 | 沒有孩子的結(jié)點(也就是度為0的結(jié)點)稱為葉子(Leaf)或終端結(jié)點 |
| branch | 分支 | 至少有一個孩子的結(jié)點稱為分支(Branch)或非終端結(jié)點 |
| degree | 度 | 結(jié)點所擁有的子樹個數(shù)稱為結(jié)點的度(Degree) |
| edge | 邊 | 一個結(jié)點和另一個結(jié)點之間的連接被稱之為邊 |
| path | 路徑 | 連接結(jié)點和其后代的結(jié)點之間的(結(jié)點,邊)的序列 |
| level | 層次 | 結(jié)點的層次(Level)從根(Root)開始定義起，根為第0層，根的孩子為第1層。以此類推，若某結(jié)點在第i層，那么其子樹的根就在第i+1層 |
| Height of node | 結(jié)點的高度 | 結(jié)點的高度是該結(jié)點和某個葉子之間存在的最長路徑上的邊的個數(shù) |
| Height of tree | 樹的高度 | 樹的高度是其根結(jié)點的高度 |
| Depth of node | 結(jié)點的深度 | 結(jié)點的深度是從樹的根結(jié)點到該結(jié)點的邊的個數(shù) |
| Forest | 森林 | 森林是n(>=0)棵互不相交的樹的集合 |
2.1 二叉樹
每個結(jié)點至多擁有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點)，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒
其具有以下的性質(zhì)：
- 若二叉樹的層次從0開始，則在二叉樹的第i層至多有2^i個結(jié)點(i>=0)。
- 高度為k的二叉樹最多有2^(k+1) - 1個結(jié)點(k>=-1)。 (空樹的高度為-1)
- 對任何一棵二叉樹，如果其葉子結(jié)點(度為0)數(shù)為m, 度為2的結(jié)點數(shù)為n, 則m = n + 1。
2.1.1 完美二叉樹
英文：
PBT(perfect binary tree)。
定義：
一個深度為k(>=-1)且有2^(k+1) - 1個結(jié)點的二叉樹。也就是說， 除了葉子結(jié)點之外的每一個結(jié)點都有兩個孩子，每一層(當(dāng)然包含最后一層)都被完全填充。
如下圖所示：
2.1.2 完全二叉樹
英文：
CBT(Complete Binary Tree)。
定義：
從根結(jié)點到倒數(shù)第二層滿足完美二叉樹，最后一層可以不完全填充，其葉子結(jié)點都靠左對齊。
如下圖所示：
2.1.3 完滿二叉樹
英文：
FBT(Full Binary Tree)，又稱為：Strictly Binary Tree。
定義：
所有非葉子結(jié)點的度都是2。換句話說，只要你有孩子，你就必然是有兩個孩子。
如下圖所示：
2.2 二叉樹遍歷
2.2.1 前序遍歷
2.2.2 中序遍歷
2.2.3 后序遍歷
2.3 二叉樹實現(xiàn)的計算器
按照這個要求來看，需要做到的有：
* 能夠含有( )、+、-、*、/ 等運算符的實數(shù)表達式計算功能
* 能夠處理小數(shù)和負(fù)數(shù)
* 能夠處理求余運算符（%）
* 能夠處理乘方（^）
* 能夠處理exp、sin、cos、tan、ctan等常見函數(shù)
* 能夠打印包含括號的中綴表達式
