为什么要使用树结构
网络异常，图片无法展示
|
二叉树
网络异常，图片无法展示
|
网络异常，图片无法展示
|
二分搜索树
- 存储的元素都必须具有可比较性。
网络异常，图片无法展示
|
二分搜索树的设计
// 定义内部类，设置节点 private class Node { public E e; public Node left, right; public Node(E e) { this.e = e; left = null; right = null; } } // 根节点 private Node root; private int size;
插入元素
不考虑重复元素的插入
网络异常，图片无法展示
|
这个是比较容易理解的递归
网络异常，图片无法展示
|
下面是更简洁的递归算法，不需要判断根节点是否为空。注意，这里返回的node是每次遍历的根节点。
- 不管node是否插入成功，他都将返回当前二叉树的根节点
- 以此来连接整个树结构。
// 插入元素 public void add(E e) { root = add(root, e); } private Node add(Node node, E e) { if(node == null) { size++; return new Node(e); } if(e.compareTo(node.e) > 0) { // 加入的节点大于当前根节点 node.right = add(node.right, e); }else if(e.compareTo(node.e) < 0){ node.left = add(node.left, e); } return node; // 最后返回根节点 }
网络异常，图片无法展示
|
非递归实现插入元素
// 插入元素非递归写法 public void addNotRecursion(E e) { if(root == null) { // 如果头结点为空 root = new Node(e); }else { // 头结点不为空 Node cur = root; while (cur != null) { if(e.compareTo(cur.e) > 0) { // 大于根节点 if(cur.right == null) { // 插入元素 cur.right = new Node(e); size++; return; } cur = cur.right; }else if(e.compareTo(cur.e) < 0){ if(cur.left == null) { // 插入元素 cur.left = new Node(e); size++; return; } cur = cur.left; }else { return; } } } }
查询元素
思路和插入元素差不多。
// 查询元素 public boolean contains(E e) { return contains(root, e); } private boolean contains(Node node, E e) { if(node == null) { // 如果树为空，那么返回false return false; } if(e.compareTo(node.e) == 0) { // 查到 return true; }else if(e.compareTo(node.e) > 0) { // 查右边树 return contains(node.right, e); }else { // 查左边的元素 return contains(node.left, e); } }
递归实现遍历元素
我们需要理解递归的过程，当我们递归到最后时，会返回结果，然后释放当前函数上下文，然后继续向后执行，所以每个节点都会查找左中右三个部分。
前序遍历
网络异常，图片无法展示
|
网络异常，图片无法展示
|
// 前序遍历 public void preOrder() { preOrder(root); } private void preOrder(Node node) { if(node == null) { // System.out.println("null"); return ; } System.out.println(node.e); // 遍历该节点的左子树 preOrder(node.left); // 遍历该节点的右子树 preOrder(node.right); }
中序遍历
就是从小到大遍历
网络异常，图片无法展示
|
网络异常，图片无法展示
|
// 中序遍历 public void inOrder() { inOrder(root); } private void inOrder(Node node) { if(node == null) { return ; } inOrder(node.left); System.out.println(node.e); inOrder(node.right); }
后序遍历
网络异常，图片无法展示
|
网络异常，图片无法展示
|
// 后序遍历 public void postOrder() { postOrder(root); } private void postOrder(Node node) { if(node == null) { return ; } postOrder(node.left); postOrder(node.right); System.out.println(node.e); }
非递归实现遍历元素
通过栈来对元素进行遍历。
- 将栈顶元素弹出后
- 将该弹出元素的右孩子压入栈
- 再将弹出元素的左孩子压入栈。
- 在压入栈的过程中，孩子为空的情况，将不压入。循环条件是栈不能为空。
网络异常，图片无法展示
|
网络异常，图片无法展示
|
// 前序遍历非递归实现 private void preOrderRn() { Stack<Node> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()) { Node pop = stack.pop(); System.out.println(pop.e); // 如果栈不为空，那么将叶子节点加入栈中 // 先加入右节点 if(pop.right != null) stack.push(pop.right); if(pop.left != null) stack.push(pop.left); } }
层次遍历, 广度优先遍历
通过队列实现，当我们出队的时候，将叶子结点加入到队列中。循环条件是队列不能为空。
// 层次遍历，使用队列实现 public void levelOrder() { Queue<Node> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { // 如果队列不为空 // 出队 Node cur = queue.remove(); System.out.println(cur.e); if(cur.left != null) { queue.add(cur.left); } if(cur.right != null) { queue.add(cur.right); } } }
网络异常，图片无法展示
|
删除二分搜索树的最小值
一直找树的left, 知道left为空，即是最小值。
网络异常，图片无法展示
|
网络异常，图片无法展示
|
// 查找最小值节点，指定根节点 public Node findMin(Node root) { if(root == null) { return null; } Node cur = root; while (cur.left != null) { cur = cur.left; } return cur; } // 删除最小值 public E removeMin() { // 删除的过程，将最小值的右子树添加到上一个根的左子树 root = removeMin(root); return findMin(root).e; } private Node removeMin(Node node) { if(node.left == null) { Node currentItemRight = node.right; node.right = null; size--; // 返回当前元素的右子树 return currentItemRight; } node.left = removeMin(node.left); return node; }
删除二分搜索树的最大值
一直找树的right, 直到right为空，即是最大值。
网络异常，图片无法展示
|
网络异常，图片无法展示
|
// 查找最大值节点，指定根节点 public Node findMax(Node root) { if(root == null) { return null; } Node cur = root; while (cur.right != null) { cur = cur.right; } return cur; } // 删除最大值 public E removeMax() { // 删除的过程，将最小值的右子树添加到上一个根的左子树 root = removeMax(root); return findMax(root).e; } private Node removeMax(Node node) { if(node.right == null) { Node currentItemLeft = node.left; node.left = null; // 这里别忘记了size-- size--; // 返回当前元素的左子树 return currentItemLeft; } node.right = removeMax(node.right); return node; }
删任意节点 Hibbard Deletion
删除只有一个叶子节点的节点和上面的差不多，但是删除有左右叶子节点的节点就很麻烦了。
网络异常，图片无法展示
|
网络异常，图片无法展示
|
// 删除任意元素 public void remove(E e) { root = remove(root, e); } private Node remove(Node node, E e) { if(node == null) { return null; } // 查看删除的元素是否有左右节点 if(e.compareTo(node.e) < 0) { node.left = remove(node.left, e); return node; }else if(e.compareTo(node.e) > 0) { node.right = remove(node.right, e); return node; }else { // node.e = e; if(node.left == null) { // 当前节点左子树为空，可能右子树不为空 Node rightNode = node.right; node.right = null; size --; return rightNode; // 返回删除节点的右子树 } if(node.right == null) { // 当前节点的右子树为空，可能左子树不为空 Node leftNode = node.left; node.left = null; size --; return leftNode; // 返回给上个节点，即上一个函数执行上下文，所以即是改删除节点的父节点。 } // 处理该节点有左右子树 // 找到比待删除节点大的最小节点，即待删除节点的右子树的最小节点。被称为后继节点 // 然后用这个节点代替待删除节点的位置。 Node successor = findMin(node.right); // 改变该后继节点的left指向 successor.left = node.left; // 改变该后继节点的right指向。即删除了该后继节点的子树 successor.right = removeMin(node.right); node.left = node.right = null; return successor; } }
对树的递归调用的总结
- 注意将节点连接起来
- 当当前值小于node，那么传入左子树。
- 当当前值大于node, 那么传入右子树。
- 找到终止递归的条件。node == null。
