随笔记录

算法-二叉树遍历

2022-4-9 diaba 数据结构

package com.jiucaiyuan.net.algrithm.tree;

import java.util.Stack;

/**
 * 二叉树的遍历（前序、中序、后续遍历）递归+非递归
 *
 * @Author jiucaiyuan  2022/4/9 22:16
 * @mail services@jiucaiyuan.net
 */
public class PreInPostTraversal {
    /**
     * 先序遍历-非递归
     */
    public static void preOrderUnRecur(Node root) {
        System.out.print("pre-order:");
        if (root != null) {
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                root = stack.pop();
                System.out.print(root.value + " ");
                //注意：先压right，再压left
                if (root.right != null) {
                    stack.push(root.right);
                }
                if (root.left != null) {
                    stack.push(root.left);
                }
            }
            System.out.println();
        }
    }

    /**
     * 中序遍历-非递归
     * 处理过程：指定root节点的整棵树左边树进栈，弹出时打印，针对弹出节点右树重复该节点的左树进栈
     */
    public static void inOrderUnRecur(Node root) {
        System.out.print("in-order:");
        if (root != null) {
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || root != null) {
                //不停的把左边树进栈
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    //如果没有左树了，弹出，处理该节点的右子树（再次进入while时还是处理该节点的左边树进栈）
                    root = stack.pop();
                    System.out.print(root.value + " ");
                    root = root.right;
                }
            }
            System.out.println();
        }
    }

    /**
     * 后序遍历-非递归
     * 借助类似前序遍历搞定：准备两个栈，通过类似前序遍历时，该访问时不访问，
     * 直接加入辅助栈，所有的都处理完，再弹出辅助栈进行处理
     */
    public static void postOrderUnRecur(Node root) {
        System.out.print("post-order:");
        if (root != null) {
            Stack<Node> stack = new Stack<>();
            Stack<Node> help = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                root = stack.pop();
//                System.out.print(root.value + " ");
                help.push(root);
                //注意：先压left，再压right
                if (root.left != null) {
                    stack.push(root.left);
                }
                if (root.right != null) {
                    stack.push(root.right);
                }
            }
            while (!help.isEmpty()) {
                System.out.print(help.pop().value + " ");
            }
            System.out.println();
        }
    }

    /**
     * 后序遍历-非递归
     */
    public static void postOrderUnRecur2(Node root) {
        System.out.print("post-order:");
        if (root != null) {
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            Node c = null;
            while (!stack.isEmpty()) {
                c = stack.peek();
                if (c.left != null && root != c.left && root != c.right) {
                    stack.push(c.left);
                } else if (c.right != null && root != c.right) {
                    stack.push(c.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    root = c;
                }
            }
            System.out.println();
        }
    }
    //------------------------------------------------

    /**
     * 遍历序
     *
     * @param root
     */
    public static void f(Node root) {
        //1
        if (root == null) {
            return;
        }
        //1
        f(root.left);
        //2
        //2
        f(root.right);
        //3
        //3
    }

    /**
     * 先序遍历-递归
     */
    public static void preOrderRecur(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.value + " ");
        preOrderRecur(root.left);
        preOrderRecur(root.right);
    }

    /**
     * 中序遍历-递归
     */
    public static void inOrderRecur(Node root) {
        if (root == null) {
            return;
        }
        inOrderRecur(root.left);
        System.out.print(root.value + " ");
        inOrderRecur(root.right);
    }

    /**
     * 后序遍历-递归
     */
    public static void postOrderRecur(Node root) {
        if (root == null) {
            return;
        }
        postOrderRecur(root.left);
        postOrderRecur(root.right);
        System.out.print(root.value + " ");
    }

}