🐵本篇文章將對二叉樹的相關概念、性質和遍歷等知識進行講解
? 一、什么是樹
在講二叉樹之前，先了解一下什么是樹：樹是一種非線性結構，其由許多節點和子節點組成，整體形狀如一顆倒掛的樹，比如下圖：
A就是這棵樹的根，BDEF、D、CG、G等都可以看作這顆樹的一顆子樹，在樹形結構中子樹之間不能由交集，否則不能稱為樹，如下圖就不是樹：
二、樹的相關概念
1. 結點的度：一個結點含有子結點的個數稱為該結點的度，如A的度為2，B的度3，D的度為0
2. 樹的度：所有結點度的最大值稱為樹的度，比如上樹中B的度最大，則該樹的度為3
3. 葉子結點/終端結點：度為0的結點稱為葉子結點，如上樹中的D E F G
4. 雙親結點/父結點：一個結點的前驅結點稱為該結點的父結點，如B的父結點為A
5. 孩子結點/子結點：一個結點的后繼結點稱為該結點的子結點，如B的子結點有D E F
6. 根結點：沒有雙親結點的結點稱為根結點，上樹的根結點為A
7. 結點的層次：從根結點那一層開始定義，A為第一層（有時是從0開始），B C所處第二層，依此類推
8. 樹的高度：樹中結點的最大層次為稱為該樹的高度，上樹的高度為3
三、二叉樹
二叉樹是一種特殊的樹，一棵所有結點的度都小于等于2的樹稱為二叉樹
二叉樹特別講究順序，如上圖中如果G為C的左孩子，則又是一顆完全不同的二叉樹
3.1 滿二叉樹
從根結點開始，從上到下從左到右每一層都放滿了結點的樹稱為滿二叉樹，如下圖：
若一個滿二叉樹有k層，則其每一層有2^(k - 1)個結點，整個樹共有(2^k) - 1個結點
3.2 完全二叉樹
從根結點開始，從上到下從左到右依次存放結點，最后一層可以不滿，這樣的二叉樹稱為完全二叉樹，如下圖：
下圖不是完全二叉樹：
3.3?二叉樹的性質
1. 若規定根結點的層數為1，則一棵非空二叉樹的第i層上最多有2^(i - 1)個結點
2. 若規定根結點的層數為1，則一棵非空二叉樹的最大結點數是(2^i) - 1
3. 對任何一棵二叉樹，如果其葉結點個數為n0，度為2的結點個數為n2，則有n0＝n2＋1
4. 具有n個結點的完全二叉樹的高度為：log?(n + 1)向上取整，如：3.x為4；或者log?(n) + 1向下取整，如3.x為3
5. 具有n個結點的完全二叉樹，從上到下從左到右依次編號，規定根結點的編號為0，則編號為i的結點：雙親編號：(i - 1) / 2；左孩子編號：2i + 1，若2i + 1 > n則無左孩子；右孩子編號：2i + 2，若2i + 2?> n則無右孩子
下面講一道例題：
一個具有767個節點的完全二叉樹，其葉子節點個數為（）
A 383
B 384
C 385
D 386
【解析】由于二叉樹中的結點的度都不大于2，所以設度為0，1，2的結點的個數分別為n0，n1，n2，則n0 + n1 + n2 = 767，由性質3：n0 = n2 + 1得2*n0 + n1 = 768，在完全二叉樹中，度為1的結點只可能有1個或0個，如果n1 = 1，則n0不是一個整數，所以n1只可能為0，經計算n0 = 384
3.4 二叉樹的存儲
二叉樹有兩種存儲方式，分別為鏈式存儲和順序存儲，這里主要講解鏈式存儲，接下來用代碼以窮舉的方式先構造下面這個二叉樹
public class BinaryTree {static class TreeNode{public char val; public TreeNode left; //指向該結點的左孩子public TreeNode right; //指向該結點的右孩子public TreeNode(char val) {this.val = val;}}
}接下來以窮舉的方式構造二叉樹
public TreeNode creatTree() {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;E.right = H;C.left = F;C.right = G;return A; //返回這個樹的根結點}
3.5 二叉樹的遍歷
二叉樹共有3種遍歷方式，分別為：先序遍歷、中序遍歷、后序遍歷，接下來會逐個講解?
3.5.1 先序遍歷
先序遍歷一個樹，按照根、左子樹、右子樹的順序遍歷這個樹，直接看例子：
先遍歷這個樹的根A，之后遍歷A的左B，由于B又是一個子樹的根，所以要繼續遍歷B的左，B的左為空，那就遍歷B的右：F，F是一個子樹的根，所以要繼續遍歷F的左：D，D的左右都為空，那么F的左子樹全部遍歷完畢，接著遍歷F的右，F的右為空，那么B的右全部遍歷完畢，那接著就是A的左全部遍歷完畢，之后遍歷A的右：C，C又是一個子樹的根，所以要繼續遍歷C的左，C的左為空，那就遍歷C的右：G，G的左右都為空，至此A的右也全部遍歷完畢，那么整個二叉樹遍歷完畢整個遍歷的序列為：A B F D C G
3.5.2 中序遍歷
先序遍歷一個樹，按照左子樹、根、右子樹的順序遍歷這個樹，直接看例子：
先遍歷A的左，由于A的左也是一個子樹，所以要遍歷這個子樹的左：空，這個子樹的左遍歷完就要遍歷這個樹的根：B，之后遍歷這個子樹的右：F D，這也是一個子樹，所以要先遍歷這個子樹左：D，然后遍歷根：F，最后是右，右為空，那么整個二叉樹的左遍歷完畢，接著遍歷根：A，然后遍歷右子樹：C G，先遍歷這個樹的左，左為空，然后遍歷根：C，最后是右：G，至此整個二叉樹遍歷完畢，整個遍歷的序列為：B D F A C G
3.5.3 后序遍歷
先序遍歷一個樹，按照左子樹、右子樹、根的順序遍歷這個樹，直接看例子：
先遍歷這個二叉樹的左子樹：B F?D，這也是一個樹，所以先遍歷這個樹的左，左為空，然后遍歷這個樹的右子樹：F D，這也是一個樹，所以要先遍歷這個樹的左：D，然后遍歷這個樹的右，右為空，最后是根：F，那么B F D這個子樹的右遍歷完畢，然后遍歷B F D這個樹的根：B，至此整個樹的左子樹遍歷完畢，然后遍歷這個樹的右子樹：C G，先遍歷這個樹的左，左為空，然后遍歷右：G，再遍歷根C，最后遍歷整個樹的根：A，整個樹遍歷完畢，整個遍歷的序列為：D F B G C A
3.6 代碼實現二叉樹的遍歷
二叉樹的三種遍歷需要用遞歸的思想實現
先序遍歷：
public void preOrder(TreeNode root) {if (root == null) { //如果根為空則直接返回return;}System.out.print(root.val +" ");preOrder(root.left); //以根的左孩子為新的根繼續遍歷preOrder(root.right); //以根的右孩子為新的根繼續遍歷}
root為null后返回至上一個方法，遍歷D的右孩子，右孩子也為空，則以D為根的方法結束返回至上一個方法，遍歷B的右孩子
右子樹也是同樣的道理
中序遍歷：
public void inOrder(TreeNode root) {if (root == null) {return;}preOrder(root.left);System.out.print(root.val +" ");preOrder(root.right);}
后序遍歷：
public void postOrder(TreeNode root) {if (root == null) {return;}preOrder(root.left);preOrder(root.right);System.out.print(root.val +" ");}
