二叉树它上线查找功能了？
多日不见，朋友们还记得什么是二叉树吗？
什么是二叉查找树
在树的任意一个节点，左子树中每个节点的值都要小于这个节点，右子树中每个节点的值都要大于这个节点，这就是二叉查找树。
查找操作
从根节点开始，如果比根节点的值小，就查询它的左子树；
如果比根节点的值大，就查询它的右子树；
如果等于我们要查找的数据，就返回这个节点元素；
按照这种逻辑，依次往下递归查询，最后到叶子节点都没有查到类似的数据，则表示数据不存在。
查找一个节点可以使用递归查询，也可以使用循环查询，一般建议使用循环操作，假设树变成一个链表，递归过深的时候，很容易出现stackoverflow 的异常。
public class BinarySearchTree { // 根节点 private Node root; /** * 循环实现方法 * * @param value 要查找的值 * @return 查找结果 */ public Node find(int value) { Node node = root; while (root != null) { if (node.value == value) { return node; } if (node.value > value) { node = node.right; } else { node = node.left; } } return null; } /** * 递归实现方法 * * @param node 起始节点，一般为根节点 * @param value 要查找的值 * @return 查找结果 */ public Node find2(Node node, int value) { if (node == null) { return null; } if (node.value > value) { return find2(node.right, value); } else if (node.value < value) { return find2(node.left, value); } else { return node; } } public class Node { private int value; private Node left; private Node right; public Node(int value) { this.value = value; } } }
插入操作
插入和查询的操作很类似，一般把新插入的节点放到叶子节点。类似查询的操作方式，查找元素应该插入的位置。
- 需要判断根节点是否为空，为空，则添加为根节点
- 如果根节点不为空，则与根节点对比大小
- 如果比根节点大，则从右子树继续查找
- 如果比根节点小，则从左子树继续查找
- 插入的条件：判断当前节点是否还有左/右节点，如果没有，则插入当前节点的左/右节点位置。
public void insert(int value) { Node node = root; if (node == null) { node = new Node(value); return; } while (node != null) { if (node.value > value) { if (node.right == null) { node.right = new Node(value); return; } node = node.right; } else { if (node.left == null) { node.left = new Node(value); return; } node = node.left; } }
删除操作
标记删除法：使用类似散列表中添加标记的删除方法，当一个数据删除以后，我们把它标记为已删除，数据并不会真的从内存中清理掉，这时候比较浪费内存。
还可以在查找的基础上进行改造，先查询节点所在位置，然后对其进行删除。
- 待删除节点为叶子节点，直接设置节点为null即可。
- 待删除节点只有一个子节点，让待删除节点的父节点指向待删除节点的子节点即可。
- 待删除节点有两个节点，删除节点以后，我们需要一个子节点填在删除的位置上，可以在它的左子树查找一个最大值，或者在右子树查找一个最小值。这个值一般在叶子节点，我们移动到删除节点位置即可。
编码思路
- 查询待删除的节点以及其父节点
- 判断节点是否为空，为空表示不存在
- 假设有两个节点，找出右子树中最小节点，替换待删除节点，然后把要删除的情况转化成叶子节点
- 假设删除的节点是叶子节点或者仅有一个子节点，或者待删除节点的子节点
- 使待删除节点的父节点指向待删除节点的子节点。
public void delete(int value) { Node delNode = tree;//要删除的节点 Node pDelNode = null;// 要删除节点的父节点 // 1.查找要删除节点，以及其父节点 while (delNode != null && delNode.value != value) { pDelNode = delNode; if (delNode.value > value) { delNode = delNode.left; } else { delNode = delNode.right; } } // 要删除的节点不存在时 if (delNode == null) { return; } // 2.假设待删除节点有两个子节点，查询出右子树最小节点 if (delNode.left != null && delNode.right != null) { Node miniRight = delNode.right; Node pMiniRight = miniRight; while (miniRight.left != null) { pMiniRight = miniRight; miniRight = miniRight.left; } // 两个节点的情况转化成 待删除节点为叶子节点，父节点为叶子节点的父节点 delNode.value = miniRight.value; delNode = miniRight; pDelNode = pMiniRight; } // 3. 假设待删除节点只有一个子节点，获取删除节点的子节点 Node child; if (delNode.left != null) { child = delNode.left; } else if (delNode.right != null) { child = delNode.right; } else { // 如果两个子节点都是空，表示要删除的节点是叶子节点 child = null; } // 设置父节点的后继节点，删除节点 if (pDelNode == null) { // 删除根节点，只有一个根节点的情况 tree = null; } else if (pDelNode.right == delNode) { pDelNode.right = child; } else { pDelNode.left = child; } }
其他
中序遍历二叉树，可以输出有序的数据序列，时间复杂度为O(n)
包含重复数据的二叉树
一、使用链表或者数组存储相同的数据，然后存放到节点中
二、把和某节点相同的值当做大于这个节点的值来处理。数据插入到这个节点的右子树。查找数据的时候，遇到值相同的节点，接着去右子树中查找数据，停止查找的条件变为遇到叶子节点。删除的时候也需要遍历右子树节点处理。
时间复杂度
二叉查找树退化成链表时，查找的时间复杂度为O(n)
如果二叉树是一个完全二叉树时，时间复杂度跟输的高度成正比，O(height)，使用层数做计算，假设层数为 k 。第一层包含1个节点，第二层包含2个节点，第三层包含4个节点，下面一层节点个数是上一层的2倍，第 k 层包含的节点个数是 2^(k-1)
假设节点个数为n，最大层数为k n >= 1+2+4+8+……+2^(k-2) n <= 1+2+4+8+……+2^(k-2)+2^(k-1)
所以 k 的范围是 [log2(n+1), log2(n)+1]，完全二叉树的层数小于等于log2(n)+1，高度小于等于log2(n)，最好的时间复杂度为O(logn)。平衡二叉树的时间复杂度可以做到稳定的O(logn)
