二叉樹
概念
- 樹的最大度為2
- 孩子分為左右
- 每層的節(jié)點數量：2^層號
- 所欲的節(jié)點數量：2層數－1棉姐，不是2(層數－1)
- 斜樹請直接使用線性表
- 一般二叉樹是沒有規(guī)律的庇绽，所以無法使用
- 滿二叉樹也是一種特殊的完全二叉樹
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/binary_tree.png
滿二叉樹
- 所有葉子節(jié)點都在一層
- 所有分支節(jié)點密度為2
- 滿二叉樹層數：2^3-1=7 => log2(7+1) => log2(n+1)
完全二叉樹
- 第i個元素的位置與滿二叉樹位置相同
- 節(jié)點順序為先左后右
- 所有葉子節(jié)點都分布在倒數后2層
- log2(n)<完全二叉樹層數<log2(n)+1
二叉樹遍歷
這里有兩個關鍵詞：訪問＋次序
訪問：對每個數據節(jié)點需要做的處理，例如：打印艾疟、加法運算
次序：不同的應用場景該有不同的訪問順序啡省。例如：給公司所有人員發(fā)年終獎的圆，按照崗位重要性逐個發(fā)放
總結
所有的數據都是存在磁盤上的贮配，然后通過程序將其加載進內存力九，然后在內存中形成一棵樹耍铜。好的，開始讀寫吧～
