樹是另一種存盤結構，跟之前說的線性結構不同，樹是一種一對多的資料結構，
一、樹
這里的樹跟現實中的大樹很像，有根有葉，但是現實的大樹根部有很多根須，而這里的樹只有一個根結點，
看圖說話，了解下常用到的術語：
- 結點點：就是圖里的一個個的圓圈了，也可以叫結點物件
- 根結點：頂部的結點A，資料結構的樹只能有一個根結點
- 父結點：B是D、E的父結點，D是H的父結點
- 子結點：F是C的子結點
- 度：結點擁有的子樹數量，B的度為2，D的度為1
- 葉結點：度為0的為葉結點，比如H、E、F、G
- 路徑：從根結點到目標結點的路線，比如找D，就是A-B-D
- 高度&深度：樹中結點的最大層數，上圖為4
- 子樹：B結點往下，C結點往下，這2部分就是A的子樹
- 有序樹：各子樹從左至右有次序的，不能互換，則為有序樹，否則為無序樹
- 森林：是互不相交的樹的集合，比如 B結點的子樹 與 C結點的子樹，就是森林
二、二叉樹
有了樹的概念，二叉樹就好理解了，首先它得是樹，上述的圖其實就是個二叉樹，
不過要注意的是，二叉樹不一定非得有2個叉，每個結點最多有2個子結點的就是二叉樹，其中又分左結點和右結點，
1.滿二叉樹：
該二叉樹所有結點都存在左子樹和右子樹，并所有葉結點都在最后一層，看起來很完美，
這里結點的總數=2^n-1，n是層數，
2.完全二叉樹：
它的描述是這樣的：對于一顆具有n個結點的二叉樹按層序編號，
如果編號為i(1<=i<=n)的結點與同樣深度的滿二叉樹中編號為i的結點
在二叉樹中位置完全相同，那么這棵樹就是完全二叉樹，
說實話，這段描述咋一看有點繞，我初次看理解了好久（太笨了），現在我來描述下幫助理解，首先關注2個點：
1 滿二叉樹
2 按層序編號
這里直接參考上述的滿二叉樹的圖，編號，就是我們給它的假想編號，就按照從上到下，從左到右來一次排序，圖中是
A~O，
-
完全二叉樹
結合示意圖可以看出，右圖存在的所有結點的編號，都與左邊的滿二叉樹中的結點位置一一對應，所以，右圖就是完全二叉樹，
-
非完全二叉樹
右圖的二叉樹中J結點實際是不存在的，未了示意用，你可以在心中給右側圖按照滿二叉樹進行編號，但是發現到J結點斷掉了，
因為此結點不存在，編號不連續了，所以就不是完全二叉樹，
接下來，就準備二叉樹的遍歷了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/270691.html
標籤：其他