1、樹的對象
具有相同特性的數據元素的集合
2、關系
如果沒有對象叫做空樹
否則：
在存在唯一的成為根的數據元素root
當元素個數大於1的時候，其他節點可以
分為互不相交的樹，成為根root的子樹
a
b c d
e f g
i j
b c d 叫做a為root節點的子樹
e f 叫做以b為root節點的子樹
以此類推
3、相關術語
結點：數據元素+若干指向子樹的分支
如上數據元素a+指向子樹b c d的指針叫做結點
結點的度：分支的個數 比如a的度就為3
樹的度：所有結點的度的最大值
葉子結點：度為0的結點
分支結點：度大約0的結點，也就是葉子結點以外的
特殊的就是root根結點
從根到結點的路徑：從根到結點所經歷的分支和結點構成
孩子結點：子樹的根對於樹的根叫做孩子結點
雙親結點：樹的根對於子樹的根叫做雙親結點
兄弟結點：有相同根的子樹叫做兄弟結點
祖先節點：從根到結點之間的全部節點叫做祖先節點
子孫節點：一個根下的所有的節點叫做子孫節點
結點的層次：角色根結點的層次為1，第L層的節點的子樹
根結點的層次是L+1層
樹的深度：樹中葉子節點所在的最大層次
如上例子：第3層的i的層次為3+1=4層，整個樹的深度為4
森林：是多棵互不相交的樹的集合，從定義可以看出，如果一棵樹去掉root根結點明顯他
就是一個森林，如果一個森林加上一個root結點那麼就是一棵樹
有向樹：
1、有確定的根
2、樹根和子樹根之間為有向關系
一般討論無序樹，同一個層次之間無序
和線性表的區別：
第一個元素無前驅 根結點無前驅
最後一個數據元素 多個葉子結點
無後繼 無後繼
其他數據元素 樹中其他節點
一個前驅， 一個前驅、多個後繼
一個後繼
由於樹的不確定性和復雜性我們一般討論二叉樹
二叉樹
定義：
二叉樹或為空樹；或者由一個根結點加上
兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成
並且一個根結點有且只有兩個子樹為左子樹和右子樹
A
B E
C F
D G
H K
左子樹 右子樹
二叉樹2種形態
1、空樹
2、只有根結點的樹
3、左子樹非空右子樹空
4、左子樹空右子樹非空
5、都不為空
對於3和4不同二叉樹必須明確是左子樹為空還是右子樹為空，雖然
只有一個子樹但是必須明確是左子樹還是右子樹
重要特性：
1、在二叉樹的第i層上最多有2^(i-1)個結點(i>=1)
2、深度為h的樹結點樹最多為2^h-1
3、對於任何一棵二叉樹，如果他含有n0個葉子節點，
n2個度為2的節點，這必然存在關系n0=n2+1
注：二叉樹有3種節點：n0代表度為0的節點
n1代表度為1的節點
n2代表度為2的節點
n0+n1+n2=n 總的結點
b為分支數量
n=b+1=1+n1+2n2
及：1+n1+2n2=n0+n1+n2
及：n0=n2+1
滿二叉樹：深度為k的樹含有2^k-1個結點，其實就是在一棵樹中
不包含度為1的節點的樹，只有深度為k的層末尾節點
才為葉子結點
完全二叉樹：如果給滿二叉樹編號，按照編號一一對應的一棵樹
及知道結點個數就知道樹的結構，且如果無左孩子
結點那麼它就是葉子結點
如：
1
2 3
4 5 6 7
為滿二叉樹
1
2 3
4 5 6
為完全二叉樹
1
2 3
4 5
不為完全二叉樹
關於完全二叉樹的特性：
1、具有n個結點的完全二叉樹的深度為 [log2 n]+1
符號[]為不大於log2 n的最大整數
2、如果i=1，則結點i是二叉樹的根，無雙親，如果i>1，
這其雙親parent(i)結點為[i/2]
3、如果2i>n則結點i無左孩子，否則左孩子是節點2i
4、如果2i+1>n則結點無右孩子，否則其右孩子是節點2i+1
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
根據二叉樹的前序數組和中序序遍歷數組生成二叉樹 http://www.linuxidc.com/Linux/2016-09/135514.htm
後序遍歷求解判斷一顆二叉樹是否為平衡二叉樹 http://www.linuxidc.com/Linux/2016-08/134054.htm
判斷二叉樹是否為完全二叉樹 http://www.linuxidc.com/Linux/2016-08/134050.htm
求二叉樹中兩個節點的最遠距離 http://www.linuxidc.com/Linux/2016-08/134049.htm
