二叉树遍历

电话面试

package 二叉树.二叉查找树;
import java.util.LinkedList;
public class BinaryTree<V extends Comparable<V>> {
    private Node root;  
    public BinaryTree() {  
        root = new Node();  
    }   
    /**
     * 数组构造器 ，无一定规则，只能按层次构造
         *     1
         *   2    3 
         *  4 5  6 7
         * 8
     *      9
     * 构成上面的形状
     */
    public BinaryTree(V[] values) {  
        System.out.print("新建binaryTree:");  
        for (V i : values) {  
            System.out.print(i + " ");  
        }  
        System.out.println();  
        boolean isLeft = true;  
        int len = values.length;  
        if (len == 0)  
            return ;  
        LinkedList<Node> queue = new LinkedList<Node>();  
        root = new Node(values[0]);  //先构造根节点(第一个元素)
        queue.addLast(root);  //将第一个元素添加到链表中，链表头结点始终是父节点
        Node parent = null;  
        Node current = null;  
        for (int i=1; i<len; i++) {  
            current = new Node(values[i]);  
            queue.addLast(current);    //加入第二个元素 1->2
            if (isLeft)  
                parent = queue.getFirst(); //无论插入左孩子还是右孩子，都是获取链表第一个元素  
            else                    //只是说插入左孩子，下次插入元素的父节点还是第一个元素本身，
                parent = queue.removeFirst();  //如果插入右孩子，说明下次插入的元素需要父节点更换成链表第二个元素，所以移除原来第一个元素1，让第二个元素2变为链表头
            if (isLeft) {  
                parent.leftChild = current;  //如果需要插入左孩子，就设置左孩子
                isLeft = false;    //下次插入是不再插入左孩子
            }else {  
                parent.rightChild = current;  //插入右孩子
                isLeft = true;          //下次插入左孩子，此时父节点不再是1
            }  
        }  
    }   
    /**
     * 递归先序遍历      
     */
    public void preorder() {  
        System.out.print("binaryTree递归先序遍历:");  
        preorderTraverseRecursion(root);  
        System.out.println();  
    }  
    private void preorderTraverseRecursion(Node node){  
        System.out.print(node.element+" ");  
        if (node.leftChild != null)  
            preorderTraverseRecursion (node.leftChild);  
        if (node.rightChild != null)  
            preorderTraverseRecursion (node.rightChild);  
    }  
    /**
     * 递归中序遍历  
     */
    public void inorder() {  
        System.out.print("binaryTree递归中序遍历:");  
        inorderTraverseRecursion(root);  
        System.out.println();  
    }  
    private void inorderTraverseRecursion(Node node) {  
        if (node.leftChild != null)  
            inorderTraverseRecursion(node.leftChild);  
        System.out.print(node.element+" ");  
        if (node.rightChild != null)  
            inorderTraverseRecursion(node.rightChild);  
    } 
    /**
     * 递归后序遍历  
     */
    public void postorder() {  
        System.out.print("binaryTree递归后序遍历:");  
        postorderTraverseRecursion(root);  
        System.out.println();  
    }  
    private void postorderTraverseRecursion(Node node) {  
         if (node.leftChild != null)  
             inorderTraverseRecursion(node.leftChild);  
         if (node.rightChild != null)  
             inorderTraverseRecursion(node.rightChild);  
         System.out.print(node.element+" ");  
    } 
    /**
     * 层次遍历  
     */
    public void layerorder() {  
        System.out.print("binaryTree层次遍历:");  
        LinkedList<Node> queue = new LinkedList<Node>();  
        queue.addLast(root);  
        Node current = null;  
        while(!queue.isEmpty()) {  
            current = queue.removeFirst();  
            if (current.leftChild != null)  
                queue.addLast(current.leftChild);  
            if (current.rightChild != null)  
                queue.addLast(current.rightChild);  
            System.out.print(current.element+" ");  
        }  
        System.out.println();  
    }  
    /**
     * 非递归先序遍历     
     *     1
     *   2    3 
     *  4 5  6 7
     * 
     */
    public void preorderNoRecursion() {  
        System.out.print("binaryTree非递归先序遍历:");  //用栈的思维去遍历
        LinkedList<Node> stack = new LinkedList<Node>();  
        stack.push(root);  //1
        Node current = null;  
        while (!stack.isEmpty()) {  
            current = stack.pop();                 //current=1  //current=2(1 2)弹出2并访问 //current=4（1 2 4） 
            System.out.print(current.element+" ");  
            if (current.rightChild != null)   //1 3        //1 3 5  
                stack.push(current.rightChild);  
            if (current.leftChild != null)    //1 3 2      //1 3 5 4
                stack.push(current.leftChild);  
        }  
        System.out.println();  
    }  
    /** 
     * 非递归中序遍历 
     * 栈内保存将要访问的元素 
     */  
    public void inorderNoRecursion() {  
        System.out.print("binaryTree非递归中序遍历:");  
        LinkedList<Node> stack = new LinkedList<Node>();  
        Node current = root;  
        while (current != null || !stack.isEmpty()) {  
            while(current != null) {   //左边有孩子就push
                stack.push(current);  
                current = current.leftChild; 
            }  
            if (!stack.isEmpty()) {  
                current = stack.pop();  
                System.out.print(current.element+" ");    //8
                current = current.rightChild;  //将当前节点转至右孩子，如果是叶子节点，就为空，上面的内层while不执行，直接Pop出4，输出4，获取4的右节点
            }  
        }  
        System.out.println();  
    }  
    /** 
     * 非递归后序遍历 
     * 当上一个访问的结点是右孩子或者当前结点没有右孩子则访问当前结点 
     */  
    /**
     * 数组构造器  
         *     1
         *   2    3 
         *  4 5  6 7
         * 8
     * 构成上面的形状
     */
    public void postorderNoRecursion() {  
        System.out.print("binaryTree非递归后序遍历:");  
        Node rNode = null;  
        Node current = root;  
        LinkedList<Node> stack = new LinkedList<Node>();  
        while(current != null || !stack.isEmpty()) {  
            while(current != null) {  
                stack.push(current);  
                current = current.leftChild; 
            }  
            current = stack.pop();  
            while (current != null && (current.rightChild == null || current.rightChild == rNode)) {  
                //current.getRightChild() == null保证最左端8的没有右孩子，否则先是输出右孩子
                //current.getRightChild() == rNode  应对下面的情况，current是2时，rNode是5，此时要输出2了，因为5已经输出过了
                //                                  2
                //                                4   5 
                System.out.print(current.element+" "); 
                rNode = current;  
                if (stack.isEmpty()){  
                    System.out.println();  
                    return;  
                }  
                current = stack.pop();  
            }  
            stack.push(current);  
            current = current.rightChild;  
        }    
    }   
    public void destroy(){
        System.out.println("销毁二叉树");
        destroy(root);
    }
    /**
     * 获得二叉树深度     
     * @return
     */
    public int getDepth() {  
        return getDepthRecursion(root);  
    }  
    private int getDepthRecursion(Node node){  
        if (node == null)  
            return 0;  
        int llen = getDepthRecursion(node.leftChild);  
        int rlen = getDepthRecursion(node.rightChild);  
        int maxlen = Math.max(llen, rlen);  
        return maxlen + 1;  
    }  
    /**
     * 销毁二叉树失敗了
     */
    public void destroy(Node node){
        if(node!=null){
            destroy(node.leftChild);
            destroy(node.rightChild);
            node = null;
        }
    }
    class Node{  
        private V  element;  
        private Node leftChild;  
        private Node rightChild;  
        public Node(){  
        };  
        public Node(V value) {  
            element = value;  
            leftChild = null;  
            rightChild = null;  
        }  
    }  
    public static void main(String[] args) {  
        BinaryTree<Integer> bt = new BinaryTree<Integer>(new Integer[]{1,2,3,4,5,6,7});  
        bt.preorder();  
        bt.inorder();  
        bt.postorder();
        bt.layerorder();  
        bt.preorderNoRecursion();  
        bt.inorderNoRecursion();  
        bt.postorderNoRecursion();  
        System.out.println("深度为：" + bt.getDepth());  
//        bt.destroy();
//        bt.layerorder();  
    }  
}