[TOC] ### 二叉樹 參考：[https://blog.csdn.net/u011240877/article/details/53242179](https://blog.csdn.net/u011240877/article/details/53242179) ### **二叉排序樹概念** ***** 二叉排序樹，又稱二叉查找樹、二叉搜索樹。 二叉排序樹是具有下列性質的二叉樹： ``` 1. 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 2. 若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 任意節點的左、右子樹也分別為二叉查找樹。 3. 沒有鍵值相等的節點（no?duplicate?nodes）。 ``` 也就是說，二叉排序樹中，左子樹都比節點小，右子樹都比節點大，遞歸定義。 ### **二叉排序樹的關鍵操作** ***** #### **查找** 根據二叉排序樹的定義，我們可以知道在查找某個元素時： * 先比較它與根節點，相等就返回；或者根節點為空，說明樹為空，也返回； * 如果它比根節點小，就從根的左子樹里進行遞歸查找； * 如果它比根節點大，就從根的右子樹里進行遞歸查找。 可以看到，這就是一個**二分查找**。 代碼示例 ``` public class BinarySearchTree { private BinaryTreeNode mRoot; //根節點 public BinarySearchTree(BinaryTreeNode root) { mRoot = root; } /** * 在整個樹中查找某個數據 * * @param data * @return */ public BinaryTreeNode search(int data) { return search(mRoot, data); } /** * 在指定二叉排序樹中查找數據 * * @param node * @param data * @return */ public BinaryTreeNode search(BinaryTreeNode node, int data) { if (node == null || node.getData() == data) { //節點為空或者相等，直接返回該節點 return node; } if (data < node.getData()) { //比節點小，就從左子樹里遞歸查找 return search(node.getLeftChild(), data); } else { //否則從右子樹 return search(node.getRightChild(), data); } } } ``` 可以看到，在二叉排序樹中**查找是十分簡單的**，但是這**依賴于每次插入、刪除元素時對整個 排序樹 結構的維護**。 ` ` 二叉樹中的插入，主要分兩步：查找、插入： * 先查找有沒有整個元素，有的話就不用插入了，直接返回； * 沒有就插入到之前查到（對比）好的合適的位置。 ` ` 插入時除了設置數據，還需要跟父節點綁定，讓父節點意識到有你這個孩子：比父節點小的就是左孩子，大的就是右孩子。 代碼實現： ``` /** * 插入到整個樹中 * * @param data */ public void insert(int data) { if (mRoot == null) { //如果當前是空樹，新建一個 mRoot = new BinaryTreeNode(); mRoot.setData(data); return; } searchAndInsert(null, mRoot, data); //根節點的父親為 null } /** * 兩步走：查找、插入 * * @param parent 要綁定的父節點 * @param node 當前比較節點 * @param data 數據 */ private BinaryTreeNode searchAndInsert(BinaryTreeNode parent, BinaryTreeNode node, int data) { if (node == null) { //當前比較節點為 空，說明之前沒有這個數據，直接新建、插入 node = new BinaryTreeNode(); node.setData(data); if (parent != null) { //父節點不為空，綁定關系 if (data < parent.getData()) { parent.setLeftChild(node); } else { parent.setRightChild(node); } } return node; } //對比的節點不為空 if (node.getData() == data) { //已經有了，不用插入了 return node; } else if (data < node.getData()) { //比節點小，從左子樹里查找、插入 return searchAndInsert(node, node.getLeftChild(), data); } else { return searchAndInsert(node, node.getRightChild(), data); } } ``` #### **刪除** 刪除 * 插入操作和查找比較類似，而刪除則相對復雜一點，需要根據刪除節點的情況分類來對待： * 如果要刪除的節點正好是葉子節點，直接刪除就 Ok 了； * 如果要刪除的節點還有子節點，就需要建立父節點和子節點的關系： * 如果只有左孩子或者右孩子，直接把這個孩子上移放到要刪除的位置就好了； * 如果有兩個孩子，就需要選一個合適的孩子節點作為新的根節點，該節點稱為 繼承節點。 代碼示例： ``` /** * 在整個樹中 查找指定數據節點的父親節點 * * @param data * @return */ public BinaryTreeNode searchParent(int data) { return searchParent(null, mRoot, data); } /** * 在指定節點下 查找指定數據節點的父親節點 * * @param parent 當前比較節點的父節點 * @param node 當前比較的節點 * @param data 查找的數據 * @return */ public BinaryTreeNode searchParent(BinaryTreeNode parent, BinaryTreeNode node, int data) { if (node == null) { //比較的節點為空返回空 return null; } if (node.getData() == data) { //找到了目標節點，返回父節點 return parent; } else if (data < node.getData()) { //數據比當前節點小，左子樹中遞歸查找 return searchParent(node, node.getLeftChild(), data); } else { return searchParent(node, node.getRightChild(), data); } } /** * 刪除指定數據的節點 * * @param data */ public void delete(int data) { if (mRoot == null || mRoot.getData() == data) { //根節點為空或者要刪除的就是根節點，直接刪掉 mRoot = null; return; } //在刪除之前需要找到它的父親 BinaryTreeNode parent = searchParent(data); if (parent == null) { //如果父節點為空，說明這個樹是空樹，沒法刪 return; } //接下來該找要刪除的節點了 BinaryTreeNode deleteNode = search(parent, data); if (deleteNode == null) { //樹中找不到要刪除的節點 return; } //刪除節點有 4 種情況 //1.左右子樹都為空，說明是葉子節點，直接刪除 if (deleteNode.getLeftChild() == null && deleteNode.getRightChild() == null) { //刪除節點 deleteNode = null; //重置父節點的孩子狀態，告訴他你以后沒有這個兒子了 if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) { parent.setLeftChild(null); } else { parent.setRightChild(null); } return; } else if (deleteNode.getLeftChild() != null && deleteNode.getRightChild() == null) { //2.要刪除的節點只有左子樹，左子樹要繼承位置 if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) { parent.setLeftChild(deleteNode.getLeftChild()); } else { parent.setRightChild(deleteNode.getLeftChild()); } deleteNode = null; return; } else if (deleteNode.getRightChild() != null && deleteNode.getRightChild() == null) { //3.要刪除的節點只有右子樹，右子樹要繼承位置 if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) { parent.setLeftChild(deleteNode.getRightChild()); } else { parent.setRightChild(deleteNode.getRightChild()); } deleteNode = null; } else { //4.要刪除的節點兒女雙全，既有左子樹又有右子樹，需要選一個合適的節點繼承，這里使用右子樹中最左節點 BinaryTreeNode copyOfDeleteNode = deleteNode; //要刪除節點的副本，指向繼承節點的父節點 BinaryTreeNode heresNode = deleteNode.getRightChild(); //要繼承位置的節點，初始為要刪除節點的右子樹的樹根 //右子樹沒有左孩子了，他就是最小的，直接上位 if (heresNode.getLeftChild() == null) { //上位后，兄弟變成了孩子 heresNode.setLeftChild(deleteNode.getLeftChild()); } else { //右子樹有左孩子，循環找到最左的，即最小的 while (heresNode.getLeftChild() != null) { copyOfDeleteNode = heresNode; //copyOfDeleteNode 指向繼承節點的父節點 heresNode = heresNode.getLeftChild(); } //找到了繼承節點，繼承節點的右子樹（如果有的話）要上移一位 copyOfDeleteNode.setLeftChild(heresNode.getRightChild()); //繼承節點先繼承家業，把自己的左右孩子變成要刪除節點的孩子 heresNode.setLeftChild(deleteNode.getLeftChild()); heresNode.setRightChild(deleteNode.getRightChild()); } //最后就是確認位置，讓要刪除節點的父節點認識新兒子 if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) { parent.setLeftChild(heresNode); } else { parent.setRightChild(heresNode); } } } ``` ### 先序，中序，后序遍歷  如圖所示，三種遍歷方法(人工)得到的結果分別是： > 先序：1 2 4 6 7 8 3 5 > 中序：4 7 6 8 2 1 3 5 > 后序：7 8 6 4 2 5 3 1 **三種遍歷方法的考查順序一致，得到的結果卻不一樣，原因在于：** **先序：**考察到一個節點后，即刻輸出該節點的值，并繼續遍歷其左右子樹。(根左右) **中序：**考察到一個節點后，將其暫存，遍歷完左子樹后，再輸出該節點的值，然后遍歷右子樹。(左根右) **后序：**考察到一個節點后，將其暫存，遍歷完左右子樹后，再輸出該節點的值。(左右根) #### 遞歸先序遍歷 遞歸先序遍歷很容易理解，先輸出節點的值，再遞歸遍歷左右子樹。中序和后序的遞歸類似，改變根節點輸出位置即可。 ``` // 遞歸先序遍歷 public static void recursionPreorderTraversal(TreeNode root) { if (root != null) { System.out.print(root.val + " "); recursionPreorderTraversal(root.left); recursionPreorderTraversal(root.right); } } ``` >遞歸先序遍歷： 1 2 4 6 7 8 3 5 #### 遞歸中序遍歷 ``` // 遞歸中序遍歷 public static void recursionMiddleorderTraversal(TreeNode root) { if (root != null) { recursionMiddleorderTraversal(root.left); System.out.print(root.val + " "); recursionMiddleorderTraversal(root.right); } } ``` >遞歸中序遍歷： 4 7 6 8 2 1 3 5 #### 遞歸后序遍歷 ``` // 遞歸后序遍歷 public static void recursionPostorderTraversal(TreeNode root) { if (root != null) { recursionPostorderTraversal(root.left); recursionPostorderTraversal(root.right); System.out.print(root.val + " "); } } ``` > 遞歸后序遍歷： 7 8 6 4 2 5 3 1 ### **總結** ***** 　二叉排序樹的性能取決于二叉樹的層數： * 最好的情況是 O(logn)，存在于完全二叉排序樹情況下，其訪問性能近似于折半查找； * 最差時候會是 O(n)，比如插入的元素是有序的，生成的二叉排序樹就是一個鏈表，這種情況下，需要遍歷全部元素才行（見下圖 b）  ### 面試題 ***** ``` 輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只調整指針的指向。 比如將二元查找樹： 1 10 2 / \ 3 6 14 4 / \ /　 \ 5 4 8 12 　 16 轉換成雙向鏈表后為：4=6=8=10=12=14=16 解析： 這題據說是微軟的面試題，乍看起來貌似很麻煩，又是二叉排序樹又是雙向鏈表的，其實考察的都是很基礎的東西，明眼人一看就發現只要將這棵樹中序遍歷后就是將二叉樹節點排序（不然它為啥叫二叉排序樹呢…），那么我們只要將這棵樹中序遍歷，遍歷到一個節點就將該節點的左指針指向上一個遍歷的節點，并將上一個遍歷的節點的右指針指向現在正在遍歷的節點，那么當我們遍歷完整棵樹后，我們的雙向鏈表也改好啦！這樣既不用添加多余節點，也不用添加多余的指針變量。 ``` ### **紅黑樹** 紅黑樹，一種二叉查找樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或Black。 **紅黑樹詳情參考**：[紅黑樹](%E7%BA%A2%E9%BB%91%E6%A0%91.md)