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

package BinaryTree;import java.util.Scanner;import java.util.Stack;//二叉树的节点public class Node {    String value;    Node left;    Node right;    public Node(String value){        this.value = value;    }    /**     * 创建一个二叉树     * 规定:不允许输入空数据，即输入的二叉树得至少有一个节点     * para:data是一个字符串数组，存储二叉树先序遍历得到的节点值，     * start是节点值在数组中开始下标,end是节点值在数组中的结束下标，如果数组中没有值，start = -1, end = -1     * 在进行判断时，不能使用data.length进行判断，因为递归函数使用的是同一个字符串数组作为输入变量，只是start和end的值不一样     * 输入的形式是作为一个满二叉树进行输入，空节点用$号代替     * 采用先序的方式创建一个二叉树     */    public static Node createBinaryTree(String[] data,int start,int end){//由于使用递归算法，所有得多设置几个参数        if((end == start)){//只有一个节点的情况下,这就是递归结束条件,不可能出现end小于start的情况            if(data[start].equals("$")){                return null;            }else{                return new Node(data[start]);            }        }else{            if(data[start].equals("$")){//如果说某个子树的根节点为$，直接返回null,下面也不用计算了1，                return null;            }            Node root = new Node(data[start]);            int halfLength = (end - start)/2;            Node leftChild = createBinaryTree(data,start+1,start+halfLength);            Node rightChild = createBinaryTree(data,start+halfLength+1,start+2*halfLength);            root.left = leftChild;            root.right = rightChild;            return root;        }    }    /**     * 先序递归输出二叉树     */    public static void preOrder(Node root){        if(root != null){            System.out.print(root.value+" ");            preOrder(root.left);            preOrder(root.right);        }    }    /**     * 中序递归输出二叉树     */    public static void inOrder(Node root){        if(root != null){            inOrder(root.left);            System.out.print(root.value+" ");            inOrder(root.right);        }    }    /**     * 后序递归遍历二叉树     */    public static void postOrder(Node root){        if(root != null){            postOrder(root.left);            postOrder(root.right);            System.out.print(root.value+" ");        }    }    /**     * 后序非递归遍历二叉树     * 后序非递归得使用到栈的结构     * 两层循环     * 我们要记得的是非递归遍历的栈中保存的是一个路径上的节点     * 出栈时访问，在栈中就没有访问     * 如果是回退到一个节点，那么只有可能该节点右子树和该节点没有被访问，该节点的左子树肯定被访问了     * 总结一下:外循环栈不为空，内循环一个左分支持续入栈，右分支持续出栈，出栈判断栈是否为空     */    public static void postOrderNotRecursive(Node root){        Stack
   
     stack = new Stack<>();//<>是泛型机制        if(root == null){            return;        }        Node node = root;        stack.push(node);        node = node.left;        //两层循环、最外层循环就是栈不为空，因为根节点是第一个进栈，最后一个出栈的,但是得先进栈根节点        while(!stack.isEmpty()){            while(node != null){                stack.push(node);                node = node.left;            }            //到这儿是左遍历结束，现在的目的是访问栈顶节点的右子树，先把这个节点拿出来，不能pull出来            //当这个时候,弹出栈中的右分支,直到遇到左节点,这里稍微难写一点,注意,右分支不是右子树为空的节点，而是栈上节点是栈下节点的右子节点            //上一次弹出的节点如果是栈顶节点的右节点，则弹出栈顶节点            Node rightNode = null;            node = stack.peek();            while(node.right == rightNode){                rightNode = stack.pop();                System.out.print(rightNode.value+" ");                if(!stack.isEmpty()) {                    node = stack.peek();                }else{                    return;                }            }            node = node.right;        }    }    /**     * 先序遍历非递归形式     * 也要使用栈     */    //仍然使用栈结构    //循环条件是什么呢？    //因为栈中元素是没访问过的，而根节点是第一个访问的。    //之前想过，只有后序遍历栈中的元素有规律，而先序和中序都没有什么规律。    //其实先序遍历的非递归形式很简单，我们要记住:一个节点访问过了就一定出栈了,如果在栈中，就一定是没有访问过的。    //那么就很简单了，根节点，压入，弹出，但是弹出之前得先把它的左右节点压入栈中,不然的话，左右子树的信息会全部丢失,那么又有问题来了    //先压入哪个节点呢？因为栈是先进后出，也就是先压入的后访问，那么我们自然得先把右节点压进去了,如果有子节点不为空,那就不用压入了，    //因为节点的访问是从栈中取出再访问，节点的压入，也是把一个节点弹出，然后拿它的左右子节点压入，那如果栈中没元素了，就没元素访问，也没元素压入了    //所有循环条件也是栈不为空    public static void preOrderNotRecursive(Node root){        if(root == null){            return;        }        Stack
    
      stack = new Stack<>();        Node node = root;        stack.push(node);        while(!stack.isEmpty()) {            node = stack.pop();            System.out.print(node.value+" ");            if (node.right != null) {//先压入右节点，再压入左节点                stack.push(node.right);            }            if (node.left != null) {                stack.push(node.left);            }        }    }    /**     * 中序遍历的非递归形式     * 中序的外层循环结束条件变了,不是栈不为空了，而是弹出节点的右节点不为空，     */    public static void inOrderNotRecursive(Node root){        if(root == null){            return;        }        Stack
     
       stack = new Stack<>();        Node node = root;        while(node !=null) {            while (node != null) {                stack.push(node);                node = node.left;            }            do {                node = stack.pop();                System.out.print(node.value + " ");                node = node.right;            } while(!stack.isEmpty()&&node == null);//和非递归后续遍历一样，在进行持续出栈的时候一定要判断栈不为空。        }    }    /**     * 测试函数     */    public static void main(String[] args){        Scanner sc = new Scanner(System.in);        String s = sc.nextLine();        String[] data = s.split(",");        Node root = createBinaryTree(data,0,data.length-1);        inOrderNotRecursive(root);    }}
     
    
   

算法时间复杂度是O(N),空间复杂度是O(h)，h是树的高度。

转载地址：http://iizji.baihongyu.com/