27
2017
09

算法

(一)二叉树遍历

四种主要的遍历思想为:

深度优先:
前序遍历:根结点 —> 左子树 —> 右子树
中序遍历:左子树—> 根结点 —> 右子树
后序遍历:左子树 —> 右子树 —> 根结点

广度优先:
层次遍历:只需按层次遍历即可

例如,求下面二叉树的各种遍历

这里写图片描述

前序遍历:1 2 4 5 7 8 3 6

中序遍历:4 2 7 5 8 1 3 6

后序遍历:4 7 8 5 2 6 3 1

层次遍历:1 2 3 4 5 6 7 8

1、前序遍历
递归版本:

public void preOrderTraverse1(TreeNode root) {  
        if (root != null) {  
            System.out.print(root.val+" ");  
            preOrderTraverse1(root.left);  
            preOrderTraverse1(root.right);  
        }  
    }  

非递归版本:(LinkedList替换成Stack也可以,下同)

public void preOrderTraverse2(TreeNode root) {  
        LinkedList<TreeNode> stack = new LinkedList<>();  
        TreeNode pNode = root;  
        while (pNode != null || !stack.isEmpty()) {  
            if (pNode != null) {  
                System.out.print(pNode.val+" ");  
                stack.push(pNode);  
                pNode = pNode.left;  
            } else { //pNode == null && !stack.isEmpty() 
                TreeNode node = stack.pop();  
                pNode = node.right;  
            }  
        }  
    }  

这里写图片描述

2、中序遍历
递归版本:

public void inOrderTraverse1(TreeNode root) {  
        if (root != null) {  
            inOrderTraverse1(root.left);  
            System.out.print(root.val+" ");  
            inOrderTraverse1(root.right);  
        }  
    }  

非递归版本:

public void inOrderTraverse2(TreeNode root) {  
        LinkedList<TreeNode> stack = new LinkedList<>();  
        TreeNode pNode = root;  
        while (pNode != null || !stack.isEmpty()) {  
            if (pNode != null) {  
                stack.push(pNode);  
                pNode = pNode.left;  
            } else { //pNode == null && !stack.isEmpty() 
                TreeNode node = stack.pop();  
                System.out.print(node.val+" ");  
                pNode = node.right;  
            }  
        }  
    }  

这里写图片描述

3.后序遍历
递归版本:

public void postOrderTraverse1(TreeNode root) {  
        if (root != null) {  
            postOrderTraverse1(root.left);  
            postOrderTraverse1(root.right);  
            System.out.print(root.val+" ");  
        }  
    }  

非递归版本:

public void posOrder1(TreeNode root)
    {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        TreeNode pNode = root;
        int i = 1;
        while(pNode != null || !stack1.empty()){
            while (pNode != null){
                stack1.push(pNode);
                stack2.push(0);
                pNode = pNode.left;
            }

            while(!stack1.empty() && stack2.peek() == i){
                stack2.pop();
                System.out.print(stack1.pop().element + " ");
            }

            if(!stack1.empty()){
                stack2.pop();
                stack2.push(1);
                pNode = stack1.peek();
                pNode = pNode.right;
            }
        }
    }

4、层次遍历

public void levelTraverse(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        LinkedList<TreeNode> queue = new LinkedList<>();  
        queue.offer(root);  
        while (!queue.isEmpty()) {  
            TreeNode node = queue.poll();  
            System.out.print(node.val+" ");  
            if (node.left != null) {  
                queue.offer(node.left);  
            }  
            if (node.right != null) {  
                queue.offer(node.right);  
            }  
        }  
    }  

5、深度优先遍历
其实深度遍历就是上面的前序、中序和后序。但是为了保证与广度优先遍历相照应,也写在这。代码也比较好理解,其实就是前序遍历,代码如下:

public void depthOrderTraverse(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        LinkedList<TreeNode> stack = new LinkedList<>();  
        stack.push(root);  
        while (!stack.isEmpty()) {  
            TreeNode node = stack.pop();  
            System.out.print(node.val+" ");  
            if (node.right != null) {  
                stack.push(node.right);  
            }  
            if (node.left != null) {  
                stack.push(node.left);  
            }  
        }  
    }  
上一篇:一步步实现三方操作功能模块封装(一),三方登录 下一篇:win 10使用模拟器蓝屏解决方案