二叉树遍历
网站首页 文章专栏 二叉树遍历
二叉树遍历
编辑时间:2019-10-08 16:06 作者:毛毛小妖 浏览量:124 评论数:0

一、前序遍历

/**
 * 前序遍历:通过栈保留待操作值
 */
public static void preOrder(TreeNode head){
    if(head == null){
        return;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(head);
    while(!stack.isEmpty()){
        TreeNode treeNode = stack.pop();
        System.out.print(treeNode.value + " ");
        if(treeNode.right != null){
            stack.push(treeNode.right);
        }
        if(treeNode.left != null){
            stack.push(treeNode.left);
        }
    }
    System.out.println();
}

二、中序遍历

/**
 * 中序遍历:当有结点时入栈,当没结点时出栈并输出
 */
public static void midOrder(TreeNode head){
    if(head == null){
        return;
    }

    Stack<TreeNode> stack = new Stack<>();
    while(head != null || !stack.isEmpty()){
        if(head != null){
            stack.push(head);
            head = head.left;
        }else {
            TreeNode treeNode = stack.pop();
            System.out.print(treeNode.value + " ");
            head = treeNode.right;
        }
    }
    System.out.println();
}

三、后序遍历

/**
 * 后序遍历:通过栈保留待操作值,类似于前序遍历
 */
public static void postOrder(TreeNode head){
    if(head == null){
        return;
    }

    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(head);
    while(!stack1.isEmpty()){
        TreeNode treeNode = stack1.pop();
        stack2.push(treeNode);//头结点是最后一个
        if(treeNode.left != null){
            stack1.push(treeNode.left);
        }
        if(treeNode.right != null){
            stack1.push(treeNode.right);
        }
    }

    while(!stack2.isEmpty()){
        System.out.print(stack2.pop().value + " ");
    }
    System.out.println();
}

 

来说两句吧
验证码:
最新评论
    还没有人评论哦,快来坐沙发吧!