一、樹的概念及結構

1、樹的概念

// 孩子兄弟表示法
typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一個孩子結點struct Node* pNextBrother; // 指向其下一個兄弟結點DataType data; // 結點中的數據域
};

二、二叉樹的概念及結構

1、概念

一棵二叉樹是結點的一個有限集合，該集合:

1. 或者為空
2. 由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成

從上圖可以看出：

1. 二叉樹不存在度大于 2 的結點。
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。

注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

---

2、現實生活中的二叉樹

3、特殊的二叉樹

1. 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為 K，且結點總數是 2^K-1，則它就是滿二叉樹。

   

2. 完全二叉樹：完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為?K 的，有 n?個結點的二叉樹，當且僅當其每一個結點都與深度為?K?的滿二叉樹中編號從?1?至?n?的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。前 K?層都是滿的，最后一層不一定滿，但最后一層從左到右必須是連續的。深度為 K?的完全二叉樹的節點個數最多為 2^K?- 1，最少為 2^(K-1) - 1 + 1（前 K 層結點個數總和 +1，因為第 K 層至少有一個結點），所以節點個數范圍是：[ 2K-1, 2K?- 1 ]。

4、二叉樹的性質?

1. 若規定根節點的層數為?1，則一棵非空二叉樹的第 i 層上最多有 2^(i-1)?個結點。
2. 若規定根節點的層數為?1，則深度為?h?的二叉樹的最大結點數是 2^h-1。
3. 對任何一棵二叉樹, 如果度為?0?其葉結點個數為 n?, 度為?2?的分支結點個數為 m?,則有?n＝ m＋1。
4. 若規定根節點的層數為?1，具有?n?個結點的滿二叉樹的深度，h= log(n+1). (ps：log(n+1)是?log?以?2 為底，n+1 為對數)。
5. 對于具有?n?個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從 0 開始編號，則對于序號為 i 的結點有： ??????????????

?

• 若?i>0，i 位置節點的雙親序號：(i-1)/2；i=0，i?為根節點編號，無雙親節點。
• 若?2i+1<n，左孩子序號：2i+1，2i+1>=n 否則無左孩子。
• 若?2i+2<n，右孩子序號：2i+2，2i+2>=n 否則無右孩子。

5、二叉樹的存儲結構

?

typedef int BTDataType;// 二叉鏈
struct BinaryTreeNode
{struct BinaryTreeNode* left; // 指向當前節點左孩子struct BinaryTreeNode* right; // 指向當前節點右孩子BTDataType data; // 當前節點值域
}// 三叉鏈
struct BinaryTreeNode
{struct BinaryTreeNode* parent; // 指向當前節點的雙親struct BinaryTreeNode* left; // 指向當前節點左孩子struct BinaryTreeNode* right; // 指向當前節點右孩子BTDataType data; // 當前節點值域
}；