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

package com.jokin.learn.Jdk18;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;/** * 二叉树的创建及遍历 * https://blog.csdn.net/qq_26312651/article/details/78144966 */public class MyBinTree {    private Node root;    public MyBinTree() {        this.root = null;    }//java的访问权限有下面四种：public--都可访问(公有)   protected--包内和子类可访问（保护）不写(default)--包内可访问 （默认）private--类内可访问（私有）    private class Node {        int data;         //default修饰符        Node lchild;        Node rchild;        public Node(int data) {            this.data = data;            this.lchild = null;            this.rchild = null;        }    }    /**     *  往二叉树node 中插入数据data     * @param node     * @param data     */    //创建二叉查找树：所有节点的左子树节点都比根节点小，右子树节点都比根节点大    public void buildTree(Node node, int data) {        if (node == null) {            node = new Node(data);        /*  if(node==null){      开始没注意写成了这样，发现每次调用buildTree时，node都是null，发现底下传入的参数其实是root            node= new LinkNode(data);*/        } else {            if (data < node.data) {  //左孩子                if (node.lchild == null) {                    node.lchild = new Node(data);                } else {                    buildTree(node.lchild, data);                }            } else {                if (node.rchild == null) {                    node.rchild = new Node(data);                } else {                    buildTree(node.rchild, data);                }            }        }    }    //递归前序遍历   根----左---右    public void preOrder(Node node) {        if (node != null) {            System.out.print("  " + node.data);            preOrder(node.lchild);            preOrder(node.rchild);        }    }    //递归中序遍历    public void inOrder(Node node) {        if (node != null) {            inOrder(node.lchild);            System.out.print(" " + node.data);            inOrder(node.rchild);        }    }    //递归后序遍历    public void postOrder(Node node) {        if (node != null) {            postOrder(node.lchild);            postOrder(node.rchild);            System.out.print(" " + node.data);        }    }    //非递归前序遍历    public void preOrder2(Node node) {        Stack
   
     stack = new Stack<>();        while (node != null || !stack.isEmpty()) {            //先一路向左走，找到底，把找到的节点都压入栈，并sysout出来。            while (node != null) {                System.out.print(node.data + " ");                stack.push(node);                node = node.lchild;            }            if (!stack.isEmpty()) {  //抛出栈顶元素                node = stack.pop();                node = node.rchild;            }        }    }    //非递归的中序遍历//和前序遍历的区别就是将输出放在了栈的pop之后    public void inOrder2(Node node) {        Stack
    
      stack = new Stack<>();        while (node != null || !stack.isEmpty()) {            while (node != null) {                stack.push(node);                node = node.lchild;            }            if (!stack.isEmpty()) {                node = stack.pop();                System.out.print(node.data + " ");                node = node.rchild;            }        }    }    //后续遍历的非递归实现    public void postOrder2(Node node) {        Stack
     
       stack = new Stack<>();        Node curNode = node;        Node lastNode = node;        while (curNode != null) {            stack.push(curNode);            curNode = curNode.lchild;        }        while (!stack.isEmpty()) {            curNode = stack.pop();            if (curNode.rchild == null || curNode.rchild == lastNode) {                System.out.print(curNode.data + " ");                lastNode = curNode;            } else {                stack.push(curNode);                curNode = curNode.rchild;                while (curNode != null) {                    stack.push(curNode);                    curNode = curNode.lchild;                }            }        }    }    //层次遍历    public void levelTravel(Node node) {        Queue
      
        queue = new LinkedList<>();        queue.offer(node);        while (!queue.isEmpty()) {            node = queue.poll();            System.out.print(node.data + " ");            if (node.lchild != null) {                queue.offer(node.lchild);            }            if (node.rchild != null) {                queue.offer(node.rchild);            }        }    }    public static void main(String[] args) {        int[] a = {2, 4, 12, 45, 21, 6, 111};        MyBinTree myBinTree = new MyBinTree();        for (int i = 0; i < a.length; i++) {            myBinTree.buildTree(myBinTree.root, a[i]);        }        myBinTree.preOrder(myBinTree.root);        System.out.println();        myBinTree.preOrder2(myBinTree.root);        System.out.println();        myBinTree.inOrder(myBinTree.root);        System.out.println();        myBinTree.inOrder2(myBinTree.root);        System.out.println();        myBinTree.postOrder(myBinTree.root);        System.out.println();        myBinTree.postOrder2(myBinTree.root);        System.out.println();        myBinTree.levelTravel(myBinTree.root);    }}