八旬老人彻夜难眠，竟是为了学会二叉树

前置知识：

什么是二叉树：一个递归的树形数据结构，每个节点最多有两个子节点；二叉树一般都是二分查找树，每个节点的值大于它左子节点的值，小于它右子节点的值

二叉树遍历：

递归遍历：

前序遍历：先访问根节点，再访问左子节点，最后访问右子节点
上图中前序遍历结果：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) {//如果当前根节点不存在，直接返回falseif (current == null) return false;//如果根节点存在并且值等于当前查找值，返回trueif (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~