存儲結構

二叉樹是一種特殊的樹，給個結點最多有兩個子節點，并且子節點有左右之分，并且兄弟，父親，孩子可以很方便的通過編號得到

1.在二叉樹的第i層上最多有2i-1個結點（i>=1）

2.深度為k的二叉樹至多有2i-1個結點

3.對于一個二叉樹，假設它有n個結點，對結點進行從1開始編號，對任一結點i滿足下面

????a.它的雙親是節點i/2(除了i=1的情況)

? ? b.左孩子是2i，右孩子是2i+1

? ? c.如果2i>i說明無左孩子 2i+1>n說明無右孩子

二叉樹的遍歷

二叉樹的遍歷是指從根結點出發，按照某種次序依次訪問二叉樹中的所有結點，使每個結點被訪問一次且僅被訪問一次

1.前序遍歷

先輸出當前結點的數據，再依次遍歷輸出左結點和右結點

2.中序遍歷

先遍歷輸出左結點，再輸出當前結點的數據，再遍歷輸出右結點

3.后序遍歷

先遍歷輸出左結點，再遍歷輸出右結點，最后輸出當前結點的數據

4.層序遍歷

從樹的第一層開始，從上到下逐層遍歷，再同一層中，從左到右對結點逐個訪問輸出

以下代碼可以在c#中實現遍歷