二叉樹+二叉樹搜尋樹+堆

                                          二叉樹

二叉樹的幾個性質

1在二叉樹的第i層最多有2^(i-1)個節點

2深度為k的二叉樹最少有k個節點，最多2^k-1個節點

3對于任何一顆非空二叉樹，如果其葉子節點數為n0，度為2的非葉子節點個數為n2=

n0-1

4具有n個節點的完全二叉樹的深度為log(n+1)

5有前序序列和中序序列可以唯一确定一顆二叉樹

6如果有n個節點，那麼二叉樹的不同形态有[1/(n+1)]*[(2n)!/(n!*n!)](這與1...n進棧問有幾種出棧順序相同)

7一棵有n個節點的完全二叉樹的第一個非葉子節點的編号為n/2（節點編号1~n）

                                                                                         二叉樹搜尋樹

二叉搜尋樹的性質

1 二叉搜尋樹可以是一棵空樹

2 二叉搜尋樹的每個節點的值都互不相同

3 二叉搜尋樹的左子樹上的所有節點值都小于根節點的值，右子樹上的所有

節點的值都大于根節點的值，左右子樹都是二叉搜尋樹

4 對二叉搜尋樹進行中序周遊，可以按從小到大排列起來

5 假設有n個節點，那麼就有(1/(n+1))*((2n)!/(n!*n!))種可能的二叉搜尋樹形态

6 在随機情況下具有n個節點的二叉搜尋樹的插入，删除，搜尋的時間複雜度為O(logn)。

                                             堆

堆的性質

1堆是一棵完全二叉樹

2最小堆是指所有的節點都滿足根節點的值小于等于左右兒子節點的值，最大堆則是所有的節點都滿足根節點的值大于等于左右兒子節點的值

3假設有n個元素的無序序列heap[n]編号從1~n，現在要建一個最小堆。

算法是從第一個非葉子節點開始往上調整即可。