-
二叉树的定义：二叉树由根节点，左子树和右子树构成；左子树和右子树都是树。
-
二叉树的插入
public class BST<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node(E e) { this.e = e; left = null; right = null; } } public E e; public Node left,right; private Node root; private int size; public void BST(){ root = null; size = 0; } public int size(){ return size; } public boolean isEmpty(){ return size==0; } //向二分搜索树中添加元素 public void insert(E e){ if(root == null){ //根节点为空，直接当做根节点 root = new Node(e); size++; return; } insert(root,e); } //向以Node为根的树中插入元素E private void insert(Node node,E e){ if(e.equals(node.e)){ return; }else if(e.compareTo(node.e)<0 && node.left==null){ node.left = new Node(e); size++; return; }else if(e.compareTo(node.e)>0 && node.right==null){ node.right = new Node(e); size++; return; } if(e.compareTo(node.e)<0){ insert(node.left,e); }else{ insert(node.right,e); } } }
-
插入算法的优化
//向以Node为根的二叉搜索树中插入元素e，递归算法 //返回插入新节点后二叉搜索树的根 private Node insert(Node node,E e){ if(node == null){ size++; return new Node(e); } if(e.compaerTo(node.e)<0){ node.left = insert(node.left,e); } else if(e.compareTo(node.e)>0){ node.right = insert(node.right,e); } return node; }
-
二叉树遍历的递归实现
二叉树的遍历方式可以分为前序遍历，中序遍历，后续遍历以及层序遍历。其中，前三种遍历方式属于深度优先遍历，而最后一种属于广度优先遍历。 需要注意的是，遍历的前中后是对根节点而言的，对于左子树和右子树而言，总是左子树在前。
-
前序遍历
private void preOrder(Node node){ if(node == null) return; System.out.println(node.e); //遍历左子树和右子树 //if(node.left != null) preOrder(node.left); //if(node.right != null) preOrder(node.right); }
-
中序遍历
private void inOrder(Node node){ if(node == null) return; //if(node.left != null) inOrder(node.left); System.out.println(node.e); //if(node.right != null) inOrder(node.right); } //左右子树的if判断语句是多余的，如果子树为空，第一行的if语句就可以判断
-
后序遍历
private void postOrder(Node node){ if(node == null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.e); } //在这里需要注意，不要把左右子树的顺序写反了
-
-
二叉树遍历的非递归实现
-
前序遍历
树的非递归遍历需要借助于栈来实现
private void preOrderNR(Node node) { Stack<Node> stack = new Stack<>(); if (node == null) return; stack.push(node); while (!stack.isEmpty()) { Node cur = stack.pop(); System.out.println(cur.e); //此处要注意压栈的顺序，右子树先压栈 if (cur.right != null) stack.push(node.right); if (cur.left != null) stack.push(node.left); } }
-
中序遍历
private void inOrderNR(Node node) { Stack<Node> stack = new Stack<>(); if (node == null) return; Node cur = node; //为什么要加cur!=null? //因为当走到最后一个右子树节点时，栈已经空了，但是当前cur指向的节点还没有访问到 while (cur != null || !stack.isEmpty()) { if (cur != null) { stack.push(cur); cur = cur.left; } else { cur = stack.pop(); System.out.println(cur.e); cur = cur.right; } } }
-
后序遍历
解法来自leetcode 143，将广度优先遍历的输出顺序进行改变得到后序遍历。
广度优先遍历：从上到下，从左到右---------->从上到下，从右到左----------->逆序输出-------->后续遍历
后序遍历：从下到上，从左到右
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> postorderTraversal(TreeNode root) { LinkedList<TreeNode> queue = new LinkedList<>(); LinkedList<Integer> output = new LinkedList<>(); if(root == null) return output; //做广度优先遍历 queue.add(root); while (!queue.isEmpty()){ TreeNode cur = queue.pollLast(); output.addFirst(cur.val); if(cur.left!=null) queue.add(cur.left); if(cur.right!=null) queue.add(cur.right); } return output; } } /** //用栈也可以完成 class Solution { public List<Integer> postorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); LinkedList<Integer> output = new LinkedList<>(); if(root == null) return output; //做广度优先遍历 stack.push(root); while (!stack.isEmpty()){ TreeNode cur = stack.pop(); output.addFirst(cur.val); if(cur.left!=null) stack.push(cur.left); if(cur.right!=null) stack.push(cur.right); } return output; } } */
先序遍历的顺序为 root,left,right，而后续遍历的结果为 left,right,root。如果我们将先序遍历的左右孩子的遍历顺序互换，则可以得到后续遍历的逆序，最后得到的也是上面的思路。
private void postOrderNR(Node node){ Stack<TreeNode> stack = new Stack<>(); Stack<TreeNode> output = new Stack<>(); ArrayList<Integer> list = new ArrayList<>(); if(root == null) return; stack.push(root); while(!stack.isEmpty()){ TreeNode p = stack.pop(); output.push(p); if(p.left!=null) stack.push(p.left); if(p.right!=null) stack.push(p.right); } while(!output.isEmpty()){ list.add(output.pop().val); } }
-
-
层序遍历
//层序遍历 private void levelOrder(Node node) { Queue<Node> queue = new LinkedList<>(); //将节点加入队列 queue.add(node); while (!queue.isEmpty()) { //取出并遍历节点 Node topNode = queue.remove(); System.out.println(topNode.e); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } }
-
寻找树中的最小值
对于二叉树而言，树的左孩子总是小于根节点小于右孩子
private Node getMin(Node root){ if(root == null) return null; //包含了没有左孩子的情况 Node p = root; while(p.left != null) p = p.left; return p; } //递归写法 public E getMin(){ if(size == 0) throw new IllegalArgumentException("BST is empty!"); return getMin(root).e; } private Node getMin(Node node){ if(node.left == null) return node; return getMin(node.left); }
-
寻找树中的最大值
private Node getMax(Node root){ if(root == null) return null; //包含了没有右孩子的情况 Node p = root; while(p.right != null) p = p.right; return p; } //递归写法 private E getMax(){ if(size == 0) throw new RuntimeException("BST is empty!"); return maximum(node).e; } private Node maximun(Node node){ if(node.right == null) return node; return maximum(node.right); }
-
从二叉树中删除最小值节点，返回删除节点后新的二叉树的根
private Node removeMin(Node root){ if(root == null) return null; if(root.left == null){ //避免直接返回 //直接返回时root依旧指向右孩子 Node right = root.right; root.right = null; size--; return right; } Node p = root; Node pre = p; while(p.left != null){ pre = p; p = p.left; } //要考虑删除的节点是否有右孩子 pre.left = p.right; //断开右子树连接 p.right = null; size--; return root; } //递归写法 public E removeMin(){ Node min = getMin(); root = removeMinimum(root); return min; } //返回删除最小节点后的树的根节点 private Node removeMinimum(Node node){ if(node.left == null){ Node right = node.right; node.right = null; size--; return right; } node.left = removeMinimum(node.left); return node; }
-
从树中删除最大值，并返回删除节点后树的根
private Node removeMax(Node node){ if(node == null) return null; if(node.right == null){ Node left = node.left; node.left = null; size--; return left; } Node p = node; Node pre = p; while(p.right!=null){ pre = p; p = p.right; } pre.right = null; size--; return root; } //递归写法 public E removeMax(){ Node max = getMax(); return removeMaximum(root); } //返回删除最大节点后的树的根 private removeMaximum(Node node){ if(node.right == null){ Node left = node.left; node.left = null; size--; return left; } node.right = removeMaximum(node.right); return node; }
-
删除树中的节点
删除掉以node为根的二分搜索树中值为e的节点, 递归算法，返回删除节点后新的二分搜索树的根
//删除掉以node为根的二分搜索树中值为e的节点, 递归算法 //返回删除节点后新的二分搜索树的根 public Node remove(Node node,E e){ if(node == null) return node; if(e.compareTo(node.e)<0){ //去左子树寻找 node.left = remove(node.left,e); }else if(e.compareTo(node.e)>0){ //去右子树寻找 node.right = remove(node.right,e); }else{ //找到了该节点 //1 节点的左子树为空 if(node.left == null){ //删除当前节点，将节点的右子树作为上层节点的左子树 Node rightNode = node.right; node.right = null; size--; return rightNode; } //2 节点的右子树为空 if(node.right == null){ //删除当前节点，将节点的左子树作为上层节点的右子树 Node leftNode = node.left; node.left = null; size--; return leftNode; } //3 节点的左右子树都不为空 //寻找右子树中的最小值代替该节点 Node min = minimum(node.right);//不会删除最小节点 min.right = removeMinimum(node.right); min.left = node.left; node.left = node.right = null; size--; return min; } }
-
树的深度打印
public String toString(){ StringBuilder sb = new StringBuilder(); generateBSTString(root,0,sb); sb.toString(); } //递归打印树的节点 private void generateBSTString(Node node,int depth,StringBuilder str){ if(node == null || node.size() == 0){ return "NULL"; } //树的根节点不为空，那么就打印根节点然后分别打印左子树和右子树 str.append(generateDepthString(depth)+node.e+"\n"); generateBSTString(node.left,depth+1,str); generateBSTString(node.right,depth+1,str); } private String generateDepthString(int depth){ StringBuilder sb = new StringBuilder(); for(int i=0;i<depth;i++) sb.append("--"); return sb.toString(); }