算法学习之二叉树的遍历

二叉树定义

二叉树是每个节点最多有两个子树的树结构，二叉树的子树有左右之分，次序不能颠倒。

二叉树结构

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}

二叉树创建

二叉树递归方法创建

public static TreeNode createTree()
{
    Scanner scan = new Scanner(System.in);
    TreeNode node = new TreeNode();
    if (scan.hasNextInt()) {
        // 判断输入的是否是整数
        int i = scan.nextInt();
        node.val = i;
        node.left = createTree();
        node.right = createTree();
    } else {
        // 输入的空节点
        System.out.println("空节点！");
        return null;
    }
    return node;
}

二叉树遍历

先序遍历(前序遍历)

按照“根节点-左子树-右子树”的顺序进行访问。

递归遍历

public static void pre_out(TreeNode node)
{
    if(node == null)
        return;
    System.out.print(node.val + " ");
    pre_out(node.left);
    pre_out(node.right);
}

非递归遍历

对于任一节点P，
1）输出节点P，然后将其入栈，再看P的左孩子是否为空；
2）若P的左孩子不为空，则置P的左孩子为当前节点，重复1）的操作；
3）若P的左孩子为空，则将栈顶节点出栈，但不输出，并将出栈节点的右孩子置为当前节点，看其是否为空；
4）若不为空，则循环至1）操作；
5）如果为空，则继续出栈，但不输出，同时将出栈节点的右孩子置为当前节点，看其是否为空，重复4）和5）操作；
6）直到当前节点P为NULL并且栈空，遍历结束。

public static void print_tree_stack_pre(TreeNode node)
{
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = node;

    while (!stack.isEmpty() || cur != null)
    {
        System.out.print(cur.val + " ");
        stack.push(cur);
        cur = cur.left;

        while (!stack.isEmpty() && cur == null)
        {
            cur = stack.pop();
            cur = cur.right;
        }
    }
}

另一种方法

public static void preOrderUnRecur(Node head) {
    if (head != null) {
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.value + " ");
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);
        }
    }
    System.out.println();
}

中序遍历

中序遍历——按照“左子树-根节点-右子树”的顺序进行访问。

递归遍历

public static void mid_out(TreeNode node)
{

    if(node == null)
        return;
    mid_out(node.left);
    System.out.print(node.val + " ");
    mid_out(node.right);
}

非递归遍历

对于任一节点P，
1）若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
2）若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
3）若不为空，则重复1）和2）的操作；
4）若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；
5）直到当前节点P为NULL并且栈为空，则遍历结束。

public static void print_tree_stack_mid(TreeNode node)
{
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = node;
    while(!stack.isEmpty() || cur != null)
    {
        stack.push(cur);
        cur = cur.left;
        while(!stack.isEmpty() && cur == null)
        {
            cur = stack.pop();
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
    }
}

另一种方法

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

后序遍历

后序遍历——按照“左子树-右子树-根节点”的顺序进行访问

递归遍历

public static void after_out(TreeNode node)
{

    if(node == null)
        return;
    after_out(node.left);
    after_out(node.right);
    System.out.print(node.val + " ");

}

非递归遍历

对于任一节点P，
1）先将节点P入栈；
2）若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出，则可以直接输出节点P，并将其出栈，将出栈节点P标记为上一个输出的节点，再将此时的栈顶结点设为当前节点；
3）若不满足2）中的条件，则将P的右孩子和左孩子依次入栈，当前节点重新置为栈顶结点，之后重复操作2）；
4）直到栈空，遍历结束。

public static void print_tree_stack_after(TreeNode node)
{
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = node;
    TreeNode pre = null;
    stack.push(cur);
    while(!stack.isEmpty())
    {
        if((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right)))
        {
            System.out.print(cur.val + " ");
            pre = stack.pop();
            if(!stack.isEmpty())
                cur = stack.peek();
        }
        else
        {
            if(cur.right != null)
            {
                stack.push(cur.right);
            }
            if(cur.left != null)
            {
                stack.push(cur.left);
            }
            cur = stack.peek();
        }
    }
}

另一种方法

public static void posOrderUnRecur1(Node head) {
    if(head != null){
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack1.push(head);
        while (!stack1.isEmpty()){
            head = stack1.pop();
            stack2.push(head);
            if(head.left != null){
                stack1.push(head.left);
            }
            if(head.right != null){
                stack1.push(head.right);
            }
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().value + " ");
        }
    }
    System.out.println();
}

public static void posOrderUnRecur2(Node h) {

    if (h != null) {
        Stack<Node> stack = new Stack<Node>();
        stack.push(h);
        Node c = null;
        while (!stack.isEmpty()) {
            c = stack.peek();
            if (c.left != null && h != c.left && h != c.right) {
                stack.push(c.left);
            } else if (c.right != null && h != c.right) {
                stack.push(c.right);
            } else {
                System.out.print(stack.pop().value + " ");
                h = c;
            }
        }
    }
    System.out.println();
}

层次遍历

即从左到右输出节点的值

public static void print_tree_queue(TreeNode node)
{
    Queue<TreeNode> queueList = new LinkedList<>();
    queueList.offer(node);
    while(!queueList.isEmpty())
    {
        TreeNode n = queueList.poll();
        System.out.print(n.val + " ");
        if(n.left != null)
            queueList.offer(n.left);
        if(n.right != null)
            queueList.offer(n.right);
    }

}

打赏