[数据结构与算法]20210710二叉树遍历

1.递归遍历

// 前序: 根、左、右
public static void pre(TreeNode node){
    if(node == null){
        return;
    }
    System.out.print(node.getVal()+" ");
    pre(node.getLeft());
    pre(node.getRight());
}

// 中序: 左、根、右
public static void mid(TreeNode node){
    if(node == null){
        return;
    }
    mid(node.getLeft());
    System.out.print(node.getVal()+" ");
    mid(node.getRight());
}


// 后序：左、右、根
public static void post(TreeNode node){
    if(node == null){
        return;
    }
    post(node.getLeft());
    post(node.getRight());
    System.out.print(node.getVal()+" ");
}

2.非递归遍历（单栈实现）

// 前序: 根、左、右
public static void pre(TreeNode node){
    if(node == null){
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = node;
    while (treeNode != null || !stack.isEmpty()){
        // 迭代访问节点左节点
        while(treeNode != null){
            System.out.print(treeNode.getVal()+" ");
            stack.push(treeNode);
            treeNode = treeNode.getLeft();
        }
        if(!stack.isEmpty()){
            treeNode = stack.pop();
            treeNode = treeNode.getRight();
        }

    }
}

// 中序: 左、根、右
public static void mid(TreeNode node){
    if(node == null){
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = node;
    while(treeNode != null || !stack.isEmpty()){
        while (treeNode != null){
            stack.push(treeNode);
            treeNode = treeNode.getLeft();
        }
        if(!stack.isEmpty()){
            treeNode = stack.pop();
            System.out.print(treeNode.getVal()+" ");
            treeNode = treeNode.getRight();
        }

    }
}


// 后序：左、右、根
public static void post(TreeNode node){
    if(node == null){
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = node;
    TreeNode pre = null; // 上一次节点
    while(treeNode != null || !stack.isEmpty()){
        while (treeNode != null){
            stack.push(treeNode);
            treeNode = treeNode.getLeft();  // 判断有没有左孩子
        }
        if(!stack.isEmpty()){
            treeNode = stack.peek();
            // 如果没有右孩子，或者右孩子是否已经访问过
            if(treeNode.getRight() == null || treeNode.getRight() == pre){  // 判断有没有右孩子
                treeNode = stack.pop();
                System.out.print(treeNode.getVal()+" ");
                pre = treeNode;
                treeNode = null;   // 为了不再进行push，而直接进入peek逻辑
            }else{
                treeNode = treeNode.getRight();
            }

        }

    }
}


//构建二叉树
public static TreeNode create(LinkedList<Integer> linkedList){
    if(linkedList == null || linkedList.size() == 0){
        return null;
    }
    TreeNode node = null;
    Integer data = linkedList.removeFirst();
    if(data != null){
        node = new TreeNode(data);
        node.setLeft(create(linkedList));
        node.setRight(create(linkedList));
    }
    return node;
}



public static void main(String[] args) {
    LinkedList<Integer> linkedList = new LinkedList<>();
    List<Integer> integers = Arrays.asList(new Integer[]{3, 2, 9, null, null, 10, null, null, 8, 77, null, null,4,88,null});
    linkedList.addAll(integers);

    TreeNode treeNode = create(linkedList);
    //pre(treeNode);  // 3 2 9 10 8 77 4 88
    //mid(treeNode);  // 9 2 10 3 77 8 88 4
    post(treeNode); // 9 10 2 77 88 4 8 3
    System.out.println("----------------------------");
}

/**pre
 3 2 9 10 8 77 4 88
 ----------------------------
 mid
 9 2 10 3 77 8 88 4
 ----------------------------
 post
 9 10 2 77 88 4 8 3
 *
 * */

/**                   3
 *            2              8
 *         9    10      77       4
 *                            88
 * */

@Data
public class TreeNode {

private Object val;
private TreeNode left;
private TreeNode right;

public TreeNode(int data){
    this.val = data;
}

}

层序遍历

public static void lev(TreeNode node){
    if(node == null){
        return;
    }
    LinkedList<TreeNode> linkedList = new LinkedList<>();
    linkedList.add(node);
    while (!linkedList.isEmpty()){
        TreeNode poll = linkedList.poll();
        System.out.print(poll.getVal()+" ");
        if(poll.getLeft() != null){
            linkedList.add(poll.getLeft());
        }
        if(poll.getRight() != null){
            linkedList.add(poll.getRight());
        }
    }

}