[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)