一、樹的概念
樹是一種分組的層次結構。
樹的定義：
樹是n(n>=0)個數據元素的集合,在任意一棵非空樹中，有如下特征
- 有且只有一個根結點（無前驅結點）
- 當n>1時，其他結點被分為若干個互不相交集合，并且每個集合又是一棵樹
我們可以看到樹的定義引用了集合的概念和迭代的概念。
二、樹的表示方法
- 文氏圖
- 圓括號
- 凹入法
- 樹形圖
三、基本術語
- 結點：樹的結點包含一個數據元素和若干指向其他子樹的分支
- 結點的度：結點的子節點的個數
- 樹的度：樹的所有結點的度的最大值
- 葉子結點：結點的度為0的結點
- 分支結點：結點的度不為0的結點
- 兄弟結點：同一個父結點下的子節點稱為兄弟結點
- 層數：根節點的層數為1，其他結點的層數為父節點的層數加1
- 樹的深度：所有結點層數的最大值
- 森林：零棵或者有限棵互不相交的樹稱為森林
- 有序樹和無序數：結點的各子節點從左到右無序（可以互換）的樹稱之為無序樹，否則稱為有序樹
四、二叉樹
1、二叉樹的定義
一種特殊的樹，除了有樹的特征外，還有如下特征：
- 當結點數大于0時，該樹由根節點和兩個子樹組成，分別稱之為左子樹和右子樹
- 左子樹和右子樹又是二叉樹
2、二叉樹的基本操作
- CreateTree創建一棵二叉樹
- ShowTree用凹入法或者圓括號法顯示一棵二叉樹
- PreOrder按照先序（根，左，右）遍歷一棵二叉樹上的所有結點
- InOrder按照中序（左，根，右）遍歷一棵二叉樹上的所有結點
- PostOrder按照后序（左，右，根）遍歷一棵二叉樹上的所有結點
- LevelOrder按層次遍歷一棵二叉樹上的所有結點
- Leafnum求一棵二叉樹上的所有葉子結點
- TreeDepth求一棵二叉樹的深度
3、二叉樹的性質
- 一棵二叉樹的第i層至多有2分之i-1個結點
- 深度為h的一棵二叉樹至多有2分之h-1個結點
- 對于一棵有n個結點的完全二叉樹，若按照滿二叉樹的方式對結點進行編號，對于任意編號為i的結點，有如下性質
- i等于1的結點為根結點，當i>1時，該結點的父節點編號為i/2
- 當2i<=n時，該結點的左子結點編號為2i，當2i>n時,該結點沒有左子節點
- 當2i+1<=n時，該結點的右子節點編號為2i+1，當2i+1>n時，該結點沒有右子節點
- 具有n（n>0）個結點的完全二叉樹，其深度為floor（log2n）+1,floor表示向下取整
- 對于一棵非空的二叉樹，設結點的度為0,1,2的結點的個數分別為n0,n1,n2，那么有：n0=n2+1
?
