前置知识：
什么是二叉树：一个递归的树形数据结构，每个节点最多有两个子节点；二叉树一般都是二分查找树，每个节点的值大于它左子节点的值，小于它右子节点的值
二叉树遍历：
递归遍历：
前序遍历：先访问根节点，再访问左子节点，最后访问右子节点
上图中前序遍历结果：30、20、5、28、50、38、58
中序遍历：先访问左子节点，再访问根节点，最后访问右子节点
上图中中序遍历结果：5、20、28、30、38、50、58
后序遍历：先访问左子节点，再访问右子节点，最后访问根节点
上图中后序遍历结果：5、28、20、38、58、50、30
非递归遍历：
常用的是利用栈的先进后出特性，不断地将节点入栈，然后再出栈
非递归前序遍历和非递归中序遍历两种方式很好理解，控制遍历时机即可，而非递归后序遍历较为复杂，需要额外维护一个最后访问节点
二叉树demo
详细实现原理都在注释中，花了几天写的，球球你好好看看，来都来了
public class MyBinaryTree { //根节点 private MyNode root; //注意，这是私有方法，对用户开放的新增方法在下面,其它几个方法也是 private MyNode addNode(MyNode current, int value) { //如果根节点为空，直接new个新节点 if (current == null) return new MyNode(value); if (value < current.value) { //如果当前插入节点的值小于根节点，则在树的左边递归插入 current.left = addNode(current.left, value); } else if (value > current.value) { //如果当前插入节点的值大于根节点，则在树的右边递归插入 current.right = addNode(current.right, value); } else { //如果等于，直接返回 return current; } return current; } public void addNode(int value) { //指定当前根节点 root = addNode(root, value); } private boolean isContainNode(MyNode current, int value) { //如果当前根节点不存在，直接返回false if (current == null) return false; //如果根节点存在并且值等于当前查找值，返回true if (current.value == value) return true; //如果目标值大于当前节点值，则在右子树递归查找，反之在左子树递归查找 return value > current.value ? isContainNode(current.right, value) : isContainNode(current.left, value); } public boolean isContainNode(int value) { //从根节点开始找 return isContainNode(root, value); } //删除节点比较复杂，或许会让你看了以后疯狂怀疑自己，请酌情查看 private MyNode deleteNode(MyNode current, int value) { //如果节点不存在，就不删咯 if (!isContainNode(value) || current == null) return null; //如果目标节点等于根节点 if (current.value == value) { //目标节点无子节点，直接删除目标节点 if (current.left == null && current.right == null) return null; //目标节点只有左子节点，直接删除目标节点，并将目标节点的父节点指向左子节点 if (current.right == null) return current.left; //目标节点只有右子节点，直接删除目标节点，并将目标节点的父节点指向右子节点 if (current.left == null) return current.right; //目标节点既有左子节点又有右子节点，这种比较复杂 //需要将目标节点右子节点的最左节点，或者目标节点左子节点的最右节点替换成目标节点，然后将目标节点删除 //我们这里是替换目标节点右子节点的最左节点，所以需要找到目标节点右子节点下面最小的那个节点，即左最节点 int i = findSmallerNode(current.right); //将目标节点替换成找到的最左节点 current.value = i; //递归删除，满足上面能删除的三种情况 current.right = deleteNode(current.right, i); return current; } else if (current.value > value) { current.left = deleteNode(current.left, value); return current; } else { current.right = deleteNode(current.right, value); return current; } } public boolean deleteNode(int value) { MyNode node = deleteNode(root, value); if (node == null) return false; return true; } //中序递归遍历 private void centerShow(MyNode root) { if (root != null) { //先递归遍历左子树 centerShow(root.left); //遍历根节点 System.out.print(root.value + " "); //再递归遍历右子树 centerShow(root.right); } } public void centerShow() { System.out.print("\n中序递归遍历："); centerShow(root); } public void centerShowPro() { System.out.print("\n中序非递归遍历："); //利用栈的先进后出 Stack<MyNode> nodeStack = new Stack<>(); while (root != null || !nodeStack.isEmpty()) { //将根节点遍历入栈 while (root != null) { nodeStack.push(root); root = root.left; } //取出栈顶元素作为根节点并删除栈顶元素，此时栈顶元素为最左节点的值 root = nodeStack.pop(); //遍历左节点，因为是从根往左入栈，所以出栈是从左到根 System.out.print(root.value + " "); //找到下一个节点，依次往右遍历 root = root.right; } } private void preShow(MyNode root) { if (root != null) { //先遍历根节点 System.out.print(root.value + " "); //然后遍历左节点 preShow(root.left); //再遍历右节点 preShow(root.right); } } public void preShow() { System.out.print("\n先序递归遍历："); preShow(root); } public void preShowPro() { System.out.print("\n先序非递归遍历："); Stack<MyNode> nodeStack = new Stack<>(); while (root != null || !nodeStack.isEmpty()) { while (root != null) { //同中序非递归遍历，只是这里先遍历根节点 System.out.print(root.value + " "); nodeStack.push(root); root = root.left; } root = nodeStack.pop(); root = root.right; } } private void afterShow(MyNode root) { if (root != null) { afterShow(root.left); afterShow(root.right); System.out.print(root.value + " "); } } public void afterShow() { System.out.print("\n后序递归遍历："); afterShow(root); } public void afterShowPro() { System.out.print("\n后序非递归遍历："); Stack<MyNode> nodeStack = new Stack<>(); MyNode lastNode = null; while (root != null || !nodeStack.isEmpty()) { while (root != null) { nodeStack.push(root); root = root.left; } //取出栈顶元素但不删除 root = nodeStack.peek(); //如果栈顶元素的右节点为空或者它是最后一次访问的节点 if (root.right == null || root.right == lastNode) { //遍历当前节点 System.out.print(root.value + " "); lastNode = nodeStack.pop(); root = null; } else { root = root.right; } } } private int findSmallerNode(MyNode root) { //删除节点用的，用来找到节点的最左子节点 return root.left == null ? root.value : findSmallerNode(root.right); } //节点，为了演示方便，只支持存放int数字 private class MyNode { private int value; private MyNode left; private MyNode right; public MyNode(int value) { this.value = value; this.left = null; this.right = null; } } }
测试：
public class MyBinaryTest { public static void main(String[] args) { deleteTest(); testPre(); testPrePro(); testCenter(); testCenterPro(); testAfter(); testAfterPro(); } public static void deleteTest() { MyBinaryTree tree = new MyBinaryTree(); tree.addNode(30); tree.addNode(20); tree.addNode(5); tree.addNode(28); tree.addNode(50); tree.addNode(38); tree.addNode(58); System.out.println("是否存在28："+tree.isContainNode(28)); tree.deleteNode(28); System.out.println("删除28后是否还存在28："+tree.isContainNode(28)); } public static void testCenter() { MyBinaryTree tree = new MyBinaryTree(); tree.addNode(30); tree.addNode(20); tree.addNode(5); tree.addNode(28); tree.addNode(50); tree.addNode(38); tree.addNode(58); tree.centerShow(); } public static void testCenterPro() { MyBinaryTree tree = new MyBinaryTree(); tree.addNode(30); tree.addNode(20); tree.addNode(5); tree.addNode(28); tree.addNode(50); tree.addNode(38); tree.addNode(58); tree.centerShowPro(); } public static void testPre() { MyBinaryTree tree = new MyBinaryTree(); tree.addNode(30); tree.addNode(20); tree.addNode(5); tree.addNode(28); tree.addNode(50); tree.addNode(38); tree.addNode(58); tree.preShow(); } public static void testPrePro() { MyBinaryTree tree = new MyBinaryTree(); tree.addNode(30); tree.addNode(20); tree.addNode(5); tree.addNode(28); tree.addNode(50); tree.addNode(38); tree.addNode(58); tree.preShowPro(); } public static void testAfter() { MyBinaryTree tree = new MyBinaryTree(); tree.addNode(30); tree.addNode(20); tree.addNode(5); tree.addNode(28); tree.addNode(50); tree.addNode(38); tree.addNode(58); tree.afterShow(); } public static void testAfterPro() { MyBinaryTree tree = new MyBinaryTree(); tree.addNode(30); tree.addNode(20); tree.addNode(5); tree.addNode(28); tree.addNode(50); tree.addNode(38); tree.addNode(58); tree.afterShowPro(); } }
运行结果：
是否存在28：true 删除28后是否还存在28：false 先序递归遍历：30 20 5 28 50 38 58 先序非递归遍历：30 20 5 28 50 38 58 中序递归遍历：5 20 28 30 38 50 58 中序非递归遍历：5 20 28 30 38 50 58 后序递归遍历：5 28 20 38 58 50 30 后序非递归遍历：5 28 20 38 58 50 30
还是那句话，家里有条件的一定一定一定复制到idea跑一跑
ok我话说完，skr~
