本文共 10610 字，大约阅读时间需要 35 分钟。

1 原理

2 实现

定义二叉树节点：

/** * 二叉树节点 * * @author wgm * @since 2021/4/18 */public class BinaryTreeNode {       private Integer data;    private BinaryTreeNode leftChild;    private BinaryTreeNode rightChild;    public BinaryTreeNode(Integer data) {           this.data = data;    }    public BinaryTreeNode setLeftChild(int data) {           BinaryTreeNode node = new BinaryTreeNode(data);        this.setLeftChild(node);        return node;    }    public BinaryTreeNode setRightChild(int data) {           BinaryTreeNode node = new BinaryTreeNode(data);        this.setRightChild(node);        return node;    }    @Override    public String toString() {           return data.toString();    }    public Integer getData() {           return data;    }    public void setData(Integer data) {           this.data = data;    }    public BinaryTreeNode getLeftChild() {           return leftChild;    }    public void setLeftChild(BinaryTreeNode leftChild) {           this.leftChild = leftChild;    }    public BinaryTreeNode getRightChild() {           return rightChild;    }    public void setRightChild(BinaryTreeNode rightChild) {           this.rightChild = rightChild;    }}

定义二叉树：

import java.util.LinkedList;import java.util.Stack;/** * 二叉树 * 二叉树的遍历，无论使用栈还是堆，都有绝对一致的遍历逻辑，区别仅仅在于元素打印语句的位置不一样。 * * @author wgm * @since 2021/4/18 */public class BinaryTree {       private BinaryTreeNode root;    public BinaryTree(BinaryTreeNode root) {           this.root = root;    }    public static BinaryTree getInit() {           BinaryTreeNode node0 = new BinaryTreeNode(0);        BinaryTreeNode node1 = node0.setLeftChild(1);        BinaryTreeNode node2 = node0.setRightChild(2);        BinaryTreeNode node3 = node1.setLeftChild(3);        BinaryTreeNode node4 = node1.setRightChild(4);        BinaryTreeNode node5 = node2.setLeftChild(5);        BinaryTreeNode node6 = node2.setRightChild(6);        BinaryTreeNode node7 = node4.setLeftChild(7);        BinaryTreeNode node8 = node4.setRightChild(8);        BinaryTreeNode node9 = node6.setLeftChild(9);        BinaryTreeNode node10 = node8.setRightChild(10);        return new BinaryTree(node0);    }    /**     * 前序遍历（递归/栈）     *     * @param recursion 是否使用递归     */    public void dlr(boolean recursion) {           if (recursion) {               dlr(this.root);        } else {               dlr(this);        }        System.out.println();    }    private void dlr(BinaryTreeNode parent) {           if (parent == null) {               return;        }        System.out.print(parent + " ");        dlr(parent.getLeftChild());        dlr(parent.getRightChild());    }    private void dlr(BinaryTree tree) {           if (tree == null || tree.root == null) {               return;        }        BinaryTreeNode preVisit = null;        BinaryTreeNode visit = tree.root;        Stack
   
     stack = new Stack<>();        while (!stack.empty() || visit != null) {               // 处理左分支            while (visit != null) {                   System.out.print(visit + " "); // 前序遍历，第一次访问时打印                stack.push(visit);                visit = visit.getLeftChild();            }            // 处理右分支            visit = stack.peek();            BinaryTreeNode rightChild = visit.getRightChild();            if (rightChild == null) {                   // 没有右节点                stack.pop();                preVisit = visit;                visit = null; // 若令visit = stack.peek()，则会陷入访问左分支的死循环。            } else if (preVisit != rightChild) {                   // 没有访问过右节点                visit = rightChild;            } else {                   // 已经访问过右节点                stack.pop();                preVisit = visit;                visit = null;            }        }    }    /**     * 中序遍历（递归/栈）     *     * @param recursion 是否使用递归     */    public void ldr(boolean recursion) {           if (recursion) {               ldr(this.root);        } else {               ldr(this);        }        System.out.println();    }    private void ldr(BinaryTreeNode parent) {           if (parent == null) {               return;        }        ldr(parent.getLeftChild());        System.out.print(parent + " ");        ldr(parent.getRightChild());    }    private void ldr(BinaryTree tree) {           if (tree == null || tree.root == null) {               return;        }        BinaryTreeNode preVisit = null;        BinaryTreeNode visit = tree.root;        Stack
    
      stack = new Stack<>();        while (!stack.empty() || visit != null) {               // 处理左分支            while (visit != null) {                   stack.push(visit);                visit = visit.getLeftChild();            }            // 处理右分支            visit = stack.peek();            BinaryTreeNode rightChild = visit.getRightChild();            if (rightChild == null) {                   // 没有右节点                System.out.print(visit + " "); // 中序遍历，第二次访问时打印                stack.pop();                preVisit = visit;                visit = null; // 若令visit = stack.peek()，则会陷入访问左分支的死循环。            } else if (preVisit != rightChild) {                   // 没有访问过右节点                System.out.print(visit + " "); // 中序遍历，第二次访问时打印                visit = rightChild;            } else {                   // 已经访问过右节点                stack.pop();                preVisit = visit;                visit = null;            }        }    }    /**     * 后序遍历（递归/栈）     *     * @param recursion 是否使用递归     */    public void lrd(boolean recursion) {           if (recursion) {               lrd(this.root);        } else {               lrd(this);        }        System.out.println();    }    private void lrd(BinaryTreeNode parent) {           if (parent == null) {               return;        }        lrd(parent.getLeftChild());        lrd(parent.getRightChild());        System.out.print(parent + " ");    }    private void lrd(BinaryTree tree) {           if (tree == null || tree.root == null) {               return;        }        BinaryTreeNode preVisit = null;        BinaryTreeNode visit = tree.root;        Stack
     
       stack = new Stack<>();        while (!stack.empty() || visit != null) {               // 处理左分支            while (visit != null) {                   stack.push(visit);                visit = visit.getLeftChild();            }            // 处理右分支            visit = stack.peek();            BinaryTreeNode rightChild = visit.getRightChild();            if (rightChild == null) {                   // 没有右节点                System.out.print(visit + " "); // 后序遍历，第三次访问时打印                stack.pop();                preVisit = visit;                visit = null; // 若令visit = stack.peek()，则会陷入访问左分支的死循环。            } else if (preVisit != rightChild) {                   // 没有访问过右节点                visit = rightChild;            } else {                   // 已经访问过右节点                System.out.print(visit + " "); // 后序遍历，第三次访问时打印                stack.pop();                preVisit = visit;                visit = null;            }        }    }    /**     * 层序遍历（队列）     */    public void level() {           if (this.root == null) {               return;        }        BinaryTreeNode visit = this.root;        LinkedList
      
        queue = new LinkedList<>();        queue.offer(visit);        while (!queue.isEmpty()) {               visit = queue.poll();            System.out.print(visit + " ");            BinaryTreeNode leftChild = visit.getLeftChild();            if (leftChild != null) {                   queue.offer(leftChild);            }            BinaryTreeNode rightChild = visit.getRightChild();            if (rightChild != null) {                   queue.offer(rightChild);            }        }        System.out.println("\r\n");    }    @Override    public String toString() {           return "BinaryTree{" +                "root=" + root +                '}';    }    public BinaryTreeNode getRoot() {           return root;    }    public void setRoot(BinaryTreeNode root) {           this.root = root;    }}
      
     
    
   

编写测试类：

/** * 测试 * * @author wgm * @since 2021/4/18 */public class BinaryTreeTest {       public static void main(String[] args) {           BinaryTree tree = BinaryTree.getInit();        System.out.print("\r\n前序遍历（递归）：\t");        tree.dlr(true);        System.out.print("前序遍历（栈）：\t");        tree.dlr(false);        System.out.print("\r\n中序遍历（递归）：\t");        tree.ldr(true);        System.out.print("中序遍历（栈）：\t");        tree.ldr(false);        System.out.print("\r\n后序遍历（递归）：\t");        tree.lrd(true);        System.out.print("后序遍历（栈）：\t");        tree.lrd(false);        System.out.print("\r\n层序遍历（队列）：\t");        tree.level();    }}

3 测试

D:\program\Java\jdk1.8.0_241\bin\java.exe -agentlib:jdwp=transport=dt_socket,address=127.0.0.1:55438,suspend=y,server=n "-javaagent:C:\Users\GMWANG~1\AppData\Local\Temp\captureAgent2401jars\debugger-agent.jar" -Dfile.encoding=UTF-8 -classpath "D:\program\Java\jdk1.8.0_241\jre\lib\charsets.jar;D:\program\Java\jdk1.8.0_241\jre\lib\deploy.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\access-bridge-64.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\cldrdata.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\dnsns.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\jaccess.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\jfxrt.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\localedata.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\nashorn.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunec.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunjce_provider.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunmscapi.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunpkcs11.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\zipfs.jar;D:\program\Java\jdk1.8.0_241\jre\lib\javaws.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jce.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jfr.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jfxswt.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jsse.jar;D:\program\Java\jdk1.8.0_241\jre\lib\management-agent.jar;D:\program\Java\jdk1.8.0_241\jre\lib\plugin.jar;D:\program\Java\jdk1.8.0_241\jre\lib\resources.jar;D:\program\Java\jdk1.8.0_241\jre\lib\rt.jar;D:\project\untitled\out\production\untitled;D:\program\JetBrains\IntelliJ IDEA 2020.1\lib\idea_rt.jar" BinaryTreeTestConnected to the target VM, address: '127.0.0.1:55438', transport: 'socket'前序遍历（递归）：	0 1 3 4 7 8 10 2 5 6 9 前序遍历（栈）：	0 1 3 4 7 8 10 2 5 6 9 中序遍历（递归）：	3 1 7 4 8 10 0 5 2 9 6 中序遍历（栈）：	3 1 7 4 8 10 0 5 2 9 6 后序遍历（递归）：	3 7 10 8 4 1 5 9 6 2 0 后序遍历（栈）：	3 7 10 8 4 1 5 9 6 2 0 层序遍历（队列）：	0 1 2 3 4 5 6 7 8 9 10 Disconnected from the target VM, address: '127.0.0.1:55438', transport: 'socket'Process finished with exit code 0