相比之前的文章，對其進行了增添和完善。
ps：本顔色的字型是後續添加内容
——————————————————
參考連結：
大話資料結構.pdf
圖解資料結構（6）——樹及樹的周遊
http://www.cnblogs.com/yc_sunniwell/archive/2010/06/27/1766233.html
1.什麼是樹？
是一種資料結構，可以用來表示層次關系，因表示的樣子很像一顆倒立的樹而得名。
在資料結構中的特點，是一對多（連結清單是一對一，圖是多對多）
最上面；樹根
中間：樹枝
最下：樹葉
2.樹的定義。
如圖：
樹定義（無根樹）：
①一個無根樹是一個二進制組(v,e); //v是頂點集（非空集合），e是邊集（v中元素構成的無序二進制組的集合）
（注：個人了解，就是有至少1個點，可以有很多個，這些點的集合，就是v，稱為頂點集，我覺得可以了解為結點的集合；
然後這些結點，将會連城一些線段，并且每條線段都沒有方向(這裡的方向，我認為可以了解為從一個點連向另外一個點，至于為什麼說沒有方向，我覺得是因為沒有起點和終點，線段隻是将兩個點連起來而已，是以稱為沒有方向)，而這些線段的結合，就是e，稱為邊集）
在離散數學中，無根樹指無環連通無向圖。
所謂的 無向圖，就是一個圖中若每條邊都是沒有方向的，則稱為無向圖。
參考連結：http://baike.baidu.com/view/93110.htm
無向圖中的邊，均是頂點的無序對，無序對通常用圓括号表示。
（注：據我了解，所謂的無序對，就是拿出某個圖中的兩個點，例如v1和v2，然後(v1,v2)表示的邊，和(v2,v1)表示的邊是一樣的。而像(v1,v2)這樣表示，就是指的是無序對，正是因為邊沒有方向，是以兩種表示方法表示的線段才是一樣的）
無根樹要求每個頂點之間都是直接或者間接相連，且圖中沒有環（即隻有簡單路徑）。
（注：因為不能有環，是以任意兩個點之間，隻有一條路徑能走的通，假如有兩條路徑能走得通，就形成了一個環了）
由于樹是圖的子集（圖是什麼？推測指的是資料結構？），這一類圖具有樹的特征，但不具備數的形式，沒有特定的根結點，故稱為無根樹。
（注：這說明，無根樹和有根樹幾乎是一樣的，除了有根樹有根結點，而根結點又是指定的，即給一個無根樹，然後指定一個結點為根，那麼這個無根樹就成為了有根樹）
樹是n（n≥0）個結點的有限集。n=0時稱為空樹，在任意一棵非空樹中：
（1）有且僅有一個特定的稱為根（root）的結點；
（2）當n＞1時，其餘結點可分為m（m>0）個互不相交的有限集t1、t2、t3......、tm，其中每個集合本身又是一棵樹，并且稱為根的子樹。
用上圖舉例子的話，就是a為根時，是一棵樹，然後這棵樹從根部分離出以b、c、d三個結點為根的子樹，其中b子樹有2個結點，c子樹有7個結點，d有1個結點。
注：
①當n>0時，即至少有一個結點時，那麼樹必然有一個根結點，且隻有一個根結點；
②子樹之間必然是互不相交的（否則就會出現多個上級結點指向同一個下級結點，或者是同級結點之間互相連接配接）
有根樹：
①樹根：在無根樹中，可取樹中任意一個結點為根r，使樹變為一顆有根樹。
②父子關系：（1）對于任意非根結點v，v到樹根r的路徑上的第一個結點p，定義為v的父結點，而v是p的子結點。
（2）一個結點可以有多個子結點（也可以是0個，例如這個樹中，隻有一條線連接配接着這個結點）；
（3）非根結點隻能有一個父結點（如果是根出來的第一個結點，那麼這個結點就是自己的父結點麼？）
（4）樹根沒有父結點。
資料結構中的樹一般是有根樹。
①有根樹的遞歸定義：
（1）沒有結點是一棵樹（可稱為空結點）；
（2）單獨的一個結點是一顆樹；
（3）如果t0、t1、t2、……、tk-1是一顆樹，t是一個結點，則将t0、t1、t2、……、tk-1作為t的子結點後，組成的樹t，也是一棵樹，樹根為t。（注意：一般有根樹使用根結點來辨別）
——我猜測，從t0到tk-1之間應該也可以将其分别視為一個結點，然後進行連接配接（以樹的形式，即任意兩個結點之間隻有一條路徑），就形成了一個有根樹（樹根為t）
樹的深度和高度：
樹的高度和樹的深度似乎不一樣，貌似說法有幾種（比如某些大學教科書）：
有的說高度和深度一樣；
有的說高度比深度少一；
有的說根結點從0開始計算；
有的說根結點從1開始計算。
根據我個人了解，如圖那樣，有5層，根直接相連的，其深度則為1，高度為3；最下層的，其深度為4，高度為0。
推測，深度就是指從根開始的距離（即從根開始計算，假如根為第0個結點，那麼連接配接他和根的線段中，他是第幾個結點，深度就是幾）；
而高度就是指，一個結點，和最底層距離有多遠，假如最多是5層，這個結點和根的距離隻有1（即位于第4層），那麼他的高度就是4。
3.二叉樹
二叉樹是樹的一種。
二叉樹的特征是，除了葉以外的結點，都有兩個子。（葉就是在它和根的路徑上，沒有比他更遠的結點了，也可以了解為，隻有一個結點和它相連，并且它不是根，那麼他就是葉）
簡單來說，就是在有根樹的基礎上，一個結點，往更深的地方延伸時，最多隻能延伸出來零個，或者兩個結點（隻能是0個或者2個，不能是1個。如果是0個就是葉，否則就是結點），那麼他就是二叉樹。
例如：圖中延伸出0個結點（葉）有：e，g,h,i,j,k
而延伸出2個結點的有：a,b,c,d,f
4.樹的周遊
所謂樹的周遊，是指對樹中所有結點的資訊的通路。
其重點有2個：
①對所有結點進行通路（假如有結點沒有被通路，肯定算不上周遊了）
②對每個結點隻通路一次；
說起周遊，那麼前提是樹必須有順序。
假如a結點是根結點，b和c是他的子（二叉樹）。那麼如何周遊呢？
先通路a再通路b最後c？還是a->c->b？又或者是先通路b或者c？
這些都是不一樣的。
隻有有了順序，才能決定怎麼通路。同樣以a、b、c三個結點為例，a是根結點，b左c右，或者是b右c左，其并非是同一個樹。
根據我個人所知推斷，假如有這樣一個樹，他最終是要存儲到硬碟裡的，如果b在a左邊，c在a右邊，其必然是有一定原因和規律的。例如，三個數都是int值，b=10，a=20，c=30。那麼以數組形式存儲，其為{b,a,c}。比a小的放a左邊，比a大的放a右邊，數組以增序排列。假如值不變，形式為{c,a,b}，那麼數組就變為以減序排列了。增序和減序，顯然是不一樣的。
是以，樹的左右順序是不能颠倒的。
疑問：我找的資料上說的是二叉樹其左右是不能颠倒的，那麼三叉樹，或者其他樹可以颠倒麼？我推測應該也是不能的吧，至于為什麼，需要查查資料。
二叉樹的周遊方法主要有三種：
①前序周遊；（先通路根結點，再通路子結點）
②後序周遊；（先通路子結點，再通路根結點）
③中序周遊（隻适用于二叉樹）
前序周遊：
順序：通路根結點——》通路左子樹——》通路右子樹
在通路子樹，依然按該順序進行通路。
以上圖中的二叉樹為例，前序周遊的順序是
其邏輯是：
（1）先通路根；
（2）目前如果是根，且無子結點，則結束；如果是根，有子結點，第二次傳回根的時候結束；（在程式設計時如何做到這一點？）
（3）檢視有沒有沒有通路過的子結點（問題，如何判斷是不是通路過的）：
（3.1）如果有，則通路子結點的左邊部分，重複（2）；
（3.2）如果沒有，則判斷目前結點是不是子結點的左結點：
（3.2.1）如果是，則通路右結點，重複（2）；
（3.2.2）如果不是，傳回父結點，重複（2）
後序周遊：
順序：通路根結點——》通路右子樹——》通路左子樹
順序正好和前序周遊相反。
是以，具體的就省略了。
中序周遊：
所謂的中序周遊，就是指，先通路左子樹，再通路根，再通路右子樹。
具體到每一個子樹時，也是如此。
與前序周遊和後序周遊不同的是，中序周遊在通路子樹的過程中，并不直接通路路徑上的，而是先要确定該子樹還有沒有子結點，如果沒有了，才通路它，如果有，則繼續通路子樹的子樹。
例如：
以圖為例，由于b是a的子，d是b的子，h是d的子，而h沒有子了。是以，先通路h。
然後通路h的父（d），通路d。
然後d的右子是i，是以通路i。
i沒有子了，傳回d；d的子樹通路完了，是以傳回d的父（b），通路b；
b的右子，是以通路e；
e沒有子了，是以傳回b，而b的子樹也通路完了，是以傳回a，通路a；
a的右子樹是c，而c有子（f），f有子（j），j無子，是以通路j；
傳回j的父f，通路f；
f的右子是k，通路k；
k無子，傳回f，f的子樹通路完了，傳回c，c的右子是g，g無子，通路g。
樹的周遊結束。其順序是：h-d-i-b-e-a-j-f-k-c-g。
形象的說，就是先通路左子樹，假如左子樹沒有子，則通路結點，并傳回，通路父，再通路父的右子樹。然後重複即可。——左-父-右的順序
樹的結點：
包括一個資料元素，和從這個元素，指向其各個子樹的分支（但不包括指向其父樹的分支）。
結點擁有的子樹數，稱為結點的度（degree），度為0的結點，稱為葉結點（leaf）或終端節點；
度不為0的結點，稱為非終端結點或分支結點。
除根結點外，分支結點也稱為内部結點。
樹的度為樹内各節點的度的最大值。
簡單來說，樹的每個結點都有度，看他往下連向幾個結點（隻考慮下一層，不考慮更深部分），其度就是幾，沒有就是0。
沒有繼續往下連接配接的（葉），就是葉結點；
不是根也不是葉的，就是内部結點；
每個結點都有度，所有結點中，度最大的結點的度，就是樹的度。
樹的順序：
之前說過，二叉樹的結點的左右子樹是不能交換的，也就是說，有順序的。
假如一個樹，其結點的子樹之間的左右順序，是有次序的，不能互相交換，那麼就說這個樹是有序樹，否則就是無序樹。