一裂垦、二叉樹的定義
????????在計(jì)算機(jī)科學(xué)中，樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀的看砂碉，它是數(shù)據(jù)元素按分支關(guān)系組織起來的結(jié)構(gòu)吟秩。二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的有序樹。通常子樹的根被稱作“左子樹”和“右子樹”绽淘。二叉樹常被用做二叉查找樹和二叉堆或是二叉排序樹。二叉樹的每個(gè)節(jié)點(diǎn)至多只有兩顆子樹闹伪，二叉樹有左右之分沪铭，次序不能顛倒。簡(jiǎn)單來說只要滿足下面兩個(gè)條件就是二叉樹：
1.本身是有序樹偏瓤；
2.樹中包含的各個(gè)節(jié)點(diǎn)的度不能超過 2杀怠，即只能是 0、1 或者 2厅克；
二叉樹具有的性質(zhì)：
1.二叉樹中赔退，第 i 層最多有2的i-1次方個(gè)結(jié)點(diǎn)。
2.如果二叉樹的深度為 K证舟，那么此二叉樹最多有 2K-1 個(gè)結(jié)點(diǎn)硕旗。
3.二叉樹中，終端結(jié)點(diǎn)數(shù)（葉子結(jié)點(diǎn)數(shù)）為 n0女责，度為 2 的結(jié)點(diǎn)數(shù)為 n2漆枚，則 n0=n2+1。
1抵知、滿二叉樹
? ? ? ?二叉樹中墙基，除了葉子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的度都為2刷喜，及每個(gè)節(jié)點(diǎn)都有左右兩個(gè)子節(jié)點(diǎn)残制。這時(shí)候的二叉樹稱之為“滿二叉樹”。
滿二叉樹除了具有二叉樹的基本心智以外還具有以下性質(zhì)：
1.滿二叉樹中第 i 層的節(jié)點(diǎn)數(shù)為 2的i-1次方個(gè)掖疮。
2.深度為?K?的滿二叉樹必有? 個(gè)節(jié)點(diǎn) 初茶，葉子數(shù)為 2的K-1次方。
3.滿二叉樹中不存在度為 1 的節(jié)點(diǎn)浊闪，每一個(gè)分支點(diǎn)中都兩棵深度相同的子樹纺蛆，且葉子節(jié)點(diǎn)都在最底層。
4.具有 n 個(gè)節(jié)點(diǎn)的滿二叉樹的深度為 规揪。
2桥氏、完全二叉樹
? ? ? ?如果二叉樹中除去最后一層節(jié)點(diǎn)外，其它層為滿二叉樹猛铅，且最后一層的結(jié)點(diǎn)依次從左到右分布字支，則此二叉樹被稱為完全二叉樹。滿二叉樹一定是個(gè)完全二叉樹。
? ? ? ?如圖 3a) 所示是一棵完全二叉樹堕伪，圖 3b) 由于最后一層的節(jié)點(diǎn)沒有按照從左向右分布青灼，因此只能算作是普通的二叉樹娄蔼。
? ? ? ?完全二叉樹除了具有普通二叉樹的性質(zhì)，它自身也具有一些獨(dú)特的性質(zhì)，比如說炸渡，n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 ?log2n?+1。
PS：?log2n? 表示取小于 log2n 的最大整數(shù)眼刃。例如截歉，?log24? = 2，而 ?log25? 結(jié)果也是 2霍比。
對(duì)于任意一個(gè)完全二叉樹來說幕袱，如果將含有的結(jié)點(diǎn)按照層次從左到右依次標(biāo)號(hào)（如圖 3a)），對(duì)于任意一個(gè)結(jié)點(diǎn) i 悠瞬，完全二叉樹還有以下幾個(gè)結(jié)論成立：
1.當(dāng) i>1 時(shí)们豌，父親結(jié)點(diǎn)為結(jié)點(diǎn) [i/2] 。（i=1 時(shí)浅妆，表示的是根結(jié)點(diǎn)望迎，無父親結(jié)點(diǎn)）
2.如果 2*i>n（總結(jié)點(diǎn)的個(gè)數(shù)） ，則結(jié)點(diǎn) i 肯定沒有左孩子（為葉子結(jié)點(diǎn)）凌外；否則其左孩子是結(jié)點(diǎn) 2*i 擂煞。
3.如果 2*i+1>n ，則結(jié)點(diǎn) i 肯定沒有右孩子趴乡；否則右孩子是結(jié)點(diǎn) 2*i+1 对省。
3、二叉搜索樹
? ? ? ? 從節(jié)點(diǎn)出發(fā)晾捏，左子樹節(jié)點(diǎn)的數(shù)據(jù)是小于節(jié)點(diǎn)蒿涎，右子樹節(jié)點(diǎn)的數(shù)據(jù)都是大于節(jié)點(diǎn)，這樣的二叉樹稱為“二叉搜索樹”惦辛。
4劳秋、平衡二叉搜索樹
? ? ? ? 在二叉搜索樹的基礎(chǔ)上，左子樹和右子樹高度差的絕對(duì)值不能超過1胖齐。
如圖5所示玻淑，左子樹的高度為4，右子樹的高度為2呀伙，高度差為2补履，所以它不是平衡二叉樹。
二剿另、二叉樹的存儲(chǔ)
1.線性存儲(chǔ)：用一個(gè)字符數(shù)組來保存箫锤，將二叉樹的節(jié)點(diǎn)按照層級(jí)從左到右標(biāo)識(shí)下標(biāo)贬蛙，如下圖所示：
?按照下標(biāo)最終排的結(jié)果為：abcdefg，那如何找到節(jié)點(diǎn)的左右子節(jié)點(diǎn)呢谚攒？假設(shè)?i?為字符數(shù)組的下標(biāo)阳准，則它的左節(jié)點(diǎn)的數(shù)組下標(biāo)為2*i+1，右節(jié)點(diǎn)的數(shù)組下標(biāo)為2*i+2馏臭。
2.鏈?zhǔn)酱鎯?chǔ)：內(nèi)部有兩個(gè)指針分別指向左右兩個(gè)子節(jié)點(diǎn)野蝇。常用的存儲(chǔ)方式。
三括儒、二叉樹的遍歷
1绕沈、深度遍歷
? ? ? ? 從根節(jié)點(diǎn)出發(fā)，使用遞歸的方式遍歷塑崖。前、中痛倚、后序遍歷都是屬于深度遍歷规婆，使用的方法就是遞歸。除了遞歸蝉稳，還可以使用迭代法遍歷抒蚜。大多數(shù)情況下，迭代都能通過棧模擬出來遞歸耘戚，只是可能實(shí)現(xiàn)的方法要麻煩一些嗡髓。
前序遍歷：中左右
中序遍歷：左中右
后序遍歷：左右中
? ? ? ?簡(jiǎn)單理解一下，所謂的前收津、中饿这、后遍歷方式，只需要記住中（根）的位置在哪兒撞秋，在最前就是前序长捧，在中間就是中序，在最后就是后序吻贿，左右是不會(huì)變的串结。所謂的前中后的單位都是樹，如下圖所示舅列，a的左為b子樹肌割，b子樹包含了de節(jié)點(diǎn)，處理a的左子樹的時(shí)候帐要，會(huì)將bde看作一棵樹把敞，然后再在這棵樹中使用左來遍歷。
2榨惠、廣度遍歷
? ? ? ? 一層一層的從左到右遍歷先巴。
3其爵、使用Java代碼實(shí)現(xiàn)二叉樹的插入和遍歷
public class BinarySearchTree{
? ? private int data;
? ? private BinarySearchTreeleft;
? ? private BinarySearchTreeright;
? ? public BinarySearchTree(int data) {
? ? ? ? this.data = data;
? ? }
? ? public BinarySearchTree(int data, BinarySearchTree left, BinarySearchTree right) {
? ? ? ? this.data = data;
? ? ? ? this.left = left;
? ? ? ? this.right = right;
? ? }
? ? /**
? ? * 插入二叉搜索樹，比節(jié)點(diǎn)數(shù)據(jù)大的數(shù)據(jù)插入右子樹伸蚯，反之插入左子樹
? ? */
? ? public static BinarySearchTreeinsert(BinarySearchTree root, int val) {
? ? ? ? if (null == root) {
? ? ? ? ? ? return new BinarySearchTree(val);
? ? ? ? }
? ? ? ? if (root.data < val) {
? ? ? ? ? ? root.right =insert(root.right, val);
? ? ? ? }
? ? ? ? if (root.data > val) {
? ? ? ? ? ? root.left =insert(root.left, val);
? ? ? ? }
? ? ? ? return root;
? ? }
? ? /**
? ? * 遍歷二叉樹--遞歸--前序
? ? */
? ? public static List<Integer> preTraverse(BinarySearchTree root, List<Integer> rlt) {
? ? ? ? if (null == root) {
? ? ? ? ? ? return rlt;
? ? ? ? }
? ? ? ? rlt =null == rlt ?new ArrayList<>() : rlt;
? ? ? ? rlt.add(root.data);
? ? ? ? preTraverse(root.left, rlt);
? ? ? ? preTraverse(root.right, rlt);
? ? ? ? rlt.add(root.data);
? ? ? ? return rlt;
? ? }
? ? /**
? ? * 遍歷二叉樹--遞歸--中序
? ? */
? ? public static List<Integer> midTraverse(BinarySearchTree root, List<Integer> rlt) {
? ? ? ? if (null == root) {
? ? ? ? ? ? return rlt;
? ? ? ? }
? ? ? ? rlt =null == rlt ?new ArrayList<>() : rlt;
? ? ? ? preTraverse(root.left, rlt);
? ? ? ? rlt.add(root.data);
? ? ? ? preTraverse(root.right, rlt);
? ? ? ? return rlt;
? ? }
? ? /**
? ? * 遍歷二叉樹--遞歸--后序
? ? */
? ? public static List<Integer> posTraverse(BinarySearchTree root, List<Integer> rlt) {
? ? ? ? if (null == root) {
? ? ? ? ? ? return rlt;
? ? ? ? }
? ? ? ? rlt =null == rlt ?new ArrayList<>() : rlt;
? ? ? ? preTraverse(root.left, rlt);
? ? ? ? preTraverse(root.right, rlt);
? ? ? ? rlt.add(root.data);
? ? ? ? return rlt;
? ? }
? ? /**
? ? * 遍歷二叉樹--迭代--前序
? ? */
? ? public static List<Integer> preIteration(BinarySearchTree root, List<Integer> rlt) {
? ? ? ? if (null == root) {
? ? ? ? ? ? return rlt;
? ? ? ? }
? ? ? ? rlt =null == rlt ?new ArrayList<>() : rlt;
? ? ? ? Stack<BinarySearchTree> stack =new Stack<>();
? ? ? ? BinarySearchTree cur = root;
? ? ? ? while (cur !=null || !stack.isEmpty()) {
? ? ? ? ? ? while (cur !=null) {
? ? ? ? ? ? ? ? stack.push(cur);
? ? ? ? ? ? ? ? rlt.add(cur.data);
? ? ? ? ? ? ? ? cur = cur.left;
? ? ? ? ? ? }
? ? ? ? ? ? BinarySearchTree top = stack.pop();
? ? ? ? ? ? cur = top.right;
? ? ? ? }
? ? ? ? return rlt;
? ? }
? ? /**
? ? * 遍歷二叉樹--迭代--中序
? ? */
? ? public static List<Integer> midIteration(BinarySearchTree root, List<Integer> rlt) {
? ? ? ? if (null == root) {
? ? ? ? ? ? return rlt;
? ? ? ? }
? ? ? ? rlt =null == rlt ?new ArrayList<>() : rlt;
? ? ? ? Stack<BinarySearchTree> stack =new Stack<>();
? ? ? ? BinarySearchTree cur = root;
? ? ? ? while (cur !=null || !stack.isEmpty()) {
? ? ? ? ? ? while (cur !=null) {
? ? ? ? ? ? ? ? stack.push(cur);
? ? ? ? ? ? ? ? cur = cur.left;
? ? ? ? ? ? }
? ? ? ? ? ? BinarySearchTree top = stack.pop();
? ? ? ? ? ? rlt.add(cur.data);
? ? ? ? ? ? cur = top.right;
? ? ? ? }
? ? ? ? return rlt;
? ? }
? ? /**
? ? * 遍歷二叉樹--迭代--后序
? ? */
? ? public static List<Integer> posIteration(BinarySearchTree root, List<Integer> rlt) {
? ? ? ? if (null == root) {
? ? ? ? ? ? return rlt;
? ? ? ? }
? ? ? ? rlt =null == rlt ?new ArrayList<>() : rlt;
? ? ? ? Stack<BinarySearchTree> stack =new Stack<>();
? ? ? ? BinarySearchTree pre =null;
? ? ? ? BinarySearchTree cur = root;
? ? ? ? while (cur !=null || !stack.isEmpty()) {
? ? ? ? ? ? while (cur !=null) {
? ? ? ? ? ? ? ? stack.push(cur);
? ? ? ? ? ? ? ? cur = cur.left;
? ? ? ? ? ? }
? ? ? ? ? ? cur = stack.peek();
? ? ? ? ? ? if (cur.right ==null || pre == cur.right) {
? ? ? ? ? ? ? ? BinarySearchTree top = stack.pop();
? ? ? ? ? ? ? ? rlt.add(top.data);
? ? ? ? ? ? ? ? pre = cur;
? ? ? ? ? ? ? ? cur =null;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? cur = cur.right;
? ? ? ? ? ? }
}
? ? ? ? return rlt;
? ? }
? ? /**
? ? * 廣度遍歷--迭代--層級(jí)
? ? */
? ? public static List<Integer> levelOderTraversal(BinarySearchTree root) {
? ? ? ? Queue<BinarySearchTree> q1 =new LinkedList<>();
? ? ? ? if (root ==null) {
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? q1.offer(root);
? ? ? ? List<Integer> rlt =new ArrayList<>();
? ? ? ? while (!q1.isEmpty()) {
? ? ? ? ? ? BinarySearchTree top = q1.poll();
? ? ? ? ? ? rlt.add(top.data);
? ? ? ? ? ? if (top.left !=null) {
? ? ? ? ? ? ? ? q1.offer(top.left);
? ? ? ? ? ? }
? ? ? ? ? ? if (top.right !=null) {
? ? ? ? ? ? ? ? q1.offer(top.right);
? ? ? ? ? ? }
}
? ? ? ? return rlt;
? ? }
}
