專欄：數據結構(Java版)
個人主頁：手握風云
目錄
一、樹型結構
1.1. 樹的定義
1.2. 樹的基本概念
1.3.?樹的表示形式
二、二叉樹
2.1. 概念
2.2. 兩種特殊的二叉樹
2.3. 二叉樹的性質
2.4. 二叉樹的存儲
三、二叉樹的基本操作
一、樹型結構
1.1. 樹的定義
? ? ? ? 樹是?種?線性的數據結構，它是由n（n>=0）個有限結點組成?個具有層次關系的集合。把它叫做 樹是因為它看起來像?棵倒掛的樹，也就是說它是根朝上，?葉朝下的。它具有以下的特點：
- 有?個特殊的結點，稱為根結點，根結點沒有前驅結點
- 除根結點外，其余結點被分成M(M > 0)個互不相交的集合T1、T2、......、Tm，其中每?個集合Ti (1 <= i <= m) ?是?棵與樹類似的?樹。每棵?樹的根結點有且只有?個前驅，可以有0個或多個后繼
- 樹是遞歸定義的
? ? ? ?注意，在樹型結構中，子樹與子樹之間不能有交集，否則就不是樹型結構。
1.2. 樹的基本概念
結點的度：?個結點含有?樹的個數稱為該結點的度； 如上圖，A的度為2
樹的度：?棵樹中，所有結點度的最?值稱為樹的度；如上圖，樹的度為3
葉子結點或終端結點：度為0的結點稱為葉結點；如上圖，G、H、I、J都是葉結點
父結點：若?個結點含有?結點，則這個結點稱為其?結點的?結點；如上圖，A是B的父節點
子結點：?個結點含有的?樹的根結點稱為該結點的?結點； 如上圖，B是A的子結點
根結點：?棵樹中，沒有父結點的結點；如上圖，A
結點的層次：從根開始定義起，根為第1層，根的?結點為第2層，以此類推
樹的高度或深度：樹中結點的最大層次；如上圖，樹的高度是4
1.3.?樹的表示形式
? ? ? ?樹結構相對線性表就比較復雜了，要存儲表示起來就?較麻煩了，實際中樹有很多種表示?式，如：雙親表示法，孩子表示法、孩子雙親表示法、孩子兄弟表示法等等。我們這?就簡單的了解其中最常用的孩子兄弟表示法。
class Node{int val;//樹中儲存的數據Node firstChild;//第一個孩子引用Node nextBrother;//下一個兄弟引用
}
二、二叉樹
2.1. 概念
? ? ? ? 一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵別稱為左子樹和右子樹的?叉樹組成。
? ? ? ?從上圖中可以看出：?叉樹不存在度?于2的結點；?叉樹的?樹有左右之分，次序不能顛倒，因此?叉樹是有序樹。
? ? ? ?注意：對于任意的?叉樹都是由以下?種情況復合?成的。
2.2. 兩種特殊的二叉樹
- 滿二叉樹：如果一棵二叉樹的層數為K，且結點總數是
，則它就是滿?叉樹。
- 完全二叉樹：完全?叉樹是由滿?叉樹?引出來的。對于深度 為K的，有n個結點的?叉樹，當且僅當其每?個結點都與深度為K的滿?叉樹中編號從0?n-1的結點一一對應。滿二叉樹是一種特殊的完全二叉樹。
2.3. 二叉樹的性質
- 若規定根結點的層數為1，則?棵?空?叉樹的第i層上最多有(i>0)個結點
- 若規定只有根結點的?叉樹的深度為1，則深度為K的?叉樹的最?結點數是(k>=0)
- 對任何?棵?叉樹, 如果其葉結點個數為 n0, 度為2的?葉結點個數為 n2,則有n0＝n2＋1
- 具有n個結點的完全?叉樹的深度k為上取整
2.4. 二叉樹的存儲
? ? ? ? 二叉樹的存儲方式分為：順序結構和類似于鏈式的結構。我們這里主要介紹鏈式存儲。?叉樹的鏈式存儲是通過?個?個的節點引?起來的。
//孩子表示法
class Node{int val;//數據域Node left;//左孩子引用Node right;//右孩子引用
}//孩子雙親表示法
class Node{int val;Node left;Node right;Node parent;//當前節點的根節點
}三、二叉樹的基本操作
我們可以自己創建一個二叉樹，我們可以參照之前創建鏈表、棧、隊列的方式來手動創建二叉樹。
public class BinaryTree {static class TreeNode{public char val;public TreeNode left;//左孩子結點引用public TreeNode right;//右孩子結點引用public TreeNode(char val) {this.val = val;}}public TreeNode CreateTree(){TreeNode A = new TreeNode('A');TreeNode B = new TreeNode('B');TreeNode C = new TreeNode('C');TreeNode D = new TreeNode('D');TreeNode E = new TreeNode('E');TreeNode F = new TreeNode('F');TreeNode G = new TreeNode('G');TreeNode H = new TreeNode('H');A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;E.right = H;return A;}
}public class Test {public static void main(String[] args) {BinaryTree binaryTree = new BinaryTree();BinaryTree.TreeNode root = binaryTree.CreateTree();//因為是靜態內部類System.out.println("========");}
}? ? ? ? 我們在打印這一行大一個斷點進行調試。先走完A結點，再通過遞歸的方法，去遍歷左孩子結點B和右孩子結點C，以此類推，再去遍歷B的左孩子結點E和右孩子結點F。
? ? ? ?二叉樹可以空樹也可以是非空樹。非空樹由根節點的左子樹、根節點的右子樹組成的。從概念中可以看出，?叉樹定義是遞歸式的，因此后序基本操作中基本都是按照該概念實現的。
