二叉树的三种遍历方式

深藏阁楼爱情的钟 2021-09-22 13:22 316阅读 0赞

public class Node {
        public String value;
        public Node left;
        public Node right;
    
        public Node(String value){
            this.value = value;
        }
    
        public Node(){}
    }
    
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    public class Tree {
        public Node root;
    
        /**
         * 构建一个测试树
         */
        public void init() {
            root = new Node("A");
            Node b = new Node("B");
            root.left = b;
            Node c = new Node("C");
            root.right = c;
            Node d = new Node("D");
            b.right = d;
            Node e = new Node("E");
            c.right = e;
            Node f = new Node("F");
            d.left = f;
            Node g = new Node("G");
            d.right = g;
            Node h = new Node("H");
            e.right = h;
     //       Node i = new Node("I");
       //     h.right=i;
        }
    
        public static void visit(Node node) {
            System.out.print(node.value + " ");
        }
    
        /**
         * 得到树的高度（递归实现）
         */
        public int getTreeHight(Node root) {
            if (root == null) return 0;
            int nleft = getTreeHight(root.left);
            int nright = getTreeHight(root.right);
            return (nleft > nright) ? nleft + 1 : nright + 1;
        }
    
        /**
         * 广度优先遍历（利用队列实现）
         */
        public void levelOrder() {
            if (root == null) return;
            Queue<Node> queue = new LinkedList<Node>();
            Node temp = root;
            queue.add(temp);
            while (!queue.isEmpty()) {
                temp = queue.poll();
                visit(temp);
                if (temp.left != null)
                    queue.add(temp.left);
                if (temp.right != null)
                    queue.add(temp.right);
            }
        }
    
        /**
         * 树的先根（序）遍历(递归方式实现)
         * */
         public void preOrder(Node root) {
             if(root != null) {
                 visit(root);
                 preOrder(root.left);
                 preOrder(root.right);
             }
         }
    
        /**
         * 树的先根（序）遍历(利用栈非递归方式实现)
         * */
        public void preOrderWithoutRecursion(Node root) {
            if (root == null) return;
            Stack<Node> stack = new Stack<Node>();
            Node temp = root;
            stack.push(temp);
            while(!stack.isEmpty()){
                temp = stack.pop();
                visit(temp);
                if(temp.right != null)
                    stack.push(temp.right);
                if(temp.left != null){
                    stack.push(temp.left);
                }
            }
        }
    
        /**
         * 树的中根遍历（递归实现方式）
         * */
        public void inOrder(Node root){
            if(root != null){
                inOrder(root.left);
                visit(root);
                inOrder(root.right);
            }
        }
    
        /**
         * 树的中根遍历（利用栈非递归实现方式）
         * */
        public void inOrderWithoutRecursion(Node root){
            Stack<Node> stack = new Stack<Node>();
            Node temp = root;
            while (!stack.isEmpty() || temp!=null) {
                if(temp != null) {
                    stack.push(temp);
                    temp = temp.left;
                } else {
                    temp = stack.pop();
                    visit(temp);
                    temp= temp.right;
                }
            }
        }
    
        /**
         * 树的后根遍历（递归实现）
         * */
        public void postOrder(Node root){
            if(root != null) {
                postOrder(root.left);
                postOrder(root.right);
                visit(root);
            }
        }
    
        /**
         * 树的后根遍历（利用栈的非递归实现方式）
         * */
        public void postOrderWithoutRecursion(Node root){
            Stack<Node> stack = new Stack();
            Node temp = root;
            Node pre =root;
            while(temp !=null){
                for(;temp.left!=null;temp = temp.left)
                    stack.push(temp);
                while(temp != null && (temp.right == null || temp.right == pre)){
                    visit(temp);
                    pre = temp;
                    if(stack.isEmpty()) return;
                    temp = stack.pop();
                }
                stack.push(temp);
                temp=temp.right;
            }
        }
    
        public static void main(String args[]) {
            Tree t = new Tree();
            t.init();
            //   System.out.println("树的高度为：" + t.getTreeHight(t.root));
           //System.out.println("树的广度优先遍历结果为：");
           //t.levelOrder();
           // System.out.println("树的先根遍历结果为：");
          // t.preOrderWithoutRecursion(t.root);
           // System.out.println("树的中根遍历结果为:");
            //t.inOrderWithoutRecursion(t.root);
            System.out.println("树的后根遍历结果为:");
            t.postOrderWithoutRecursion(t.root);
        }
    }