当前位置：首页 > article >正文

基础数据结构——二叉树（深度优先遍历，前序遍历，中序遍历，后序遍历）

article 2025/2/28 19:46:11

一.概述

二叉树是这么一种树状结构：每个节点最多有两个孩子，左孩子和右孩子

重要的二叉树结构

完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右
平衡二叉树（balance binary tree）是一种二叉树结构，其中每个节点的左右子树高度相差不超过 1

二.存储

存储方式分为两种

定义树节点与左、右孩子引用（TreeNode）
使用数组，前面讲堆时用过，若以 0 作为树的根，索引可以通过如下方式计算
- 父 = floor((子 - 1) / 2)
- 左孩子 = 父 * 2 + 1
- 右孩子 = 父 * 2 + 2

定义树节点

public TreeNode left;
    public int val;
    public TreeNode right;

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

    public TreeNode(TreeNode left, int val, TreeNode right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }
}

三.遍历

遍历也分为两种

广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历
深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点）
1. pre-order 前序遍历，对于每一棵子树，先访问该节点，然后是左子树，最后是右子树
2. in-order 中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是右子树
3. post-order 后序遍历，对于每一棵子树，先访问左子树，然后是右子树，最后是该节点

1.广度优先遍历

在这里插入图片描述

初始化，将根节点加入队列
循环处理队列中每个节点，直至队列为空
每次循环内处理节点后，将它的孩子节点（即下一层的节点）加入队列

注意

以上用队列来层序遍历是针对 TreeNode 这种方式表示的二叉树

对于数组表现的二叉树，则直接遍历数组即可，自然为层序遍历的顺序

2.深度优先遍历

在这里插入图片描述

规则	说明
前序遍历	先访问该节点，然后是左子树，最后是右子树
中序遍历	先访问左子树，然后是该节点，最后是右子树
后序遍历	先访问左子树，然后是右子树，最后是该节点

定义节点信息

TreeNode root = new TreeNode(
        new TreeNode(
                new TreeNode(4),
                2,
                null
        ),
        1,
        new TreeNode(
                new TreeNode(5),
                3,
                new TreeNode(6)
        )
);

前序遍历

先访问该节点
然后是左子树
最后是右子树

private static void preOder(TreeNode node) {
    //方式一：递归实现
    /*if (node == null) {
        return;
    }
    System.out.print(node.val + "\t");
    preOder(node.left);
    preOder(node.right);*/

    //方式二：结合栈来实现
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode pointer = node;
    while (pointer != null || !stack.isEmpty()) {
        if (pointer != null) {
            System.out.println(pointer.val);
            stack.push(pointer);//压入栈，记住来时的路
            pointer = pointer.left;
        } else {
            TreeNode n = stack.pop();
            pointer = n.right;
        }
    }
}

中序遍历

先访问左子树
然后是该节点
最后是右子树

private static void midOder(TreeNode node) {
    //方式一：递归实现
    /*if (node == null) {
        return;
    }
    midOder(node.left);
    System.out.print(node.val + "\t");
    midOder(node.right);*/

    //方式二：结合栈来实现
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode pointer = node;
    while (pointer != null || !stack.isEmpty()) {
        if (pointer != null) {
            stack.push(pointer);
            pointer = pointer.left;
        } else {
            TreeNode pop = stack.pop();
            System.out.println(pop.val);
        }
    }
}

后序遍历

先访问左子树
然后是右子树
最后是该节点

private static void postOder(TreeNode node) {
    //方式一：递归实现
    /*if (node == null) {
        return;
    }
    postOder(node.left);
    postOder(node.right);
    System.out.print(node.val + "\t");*/

    //方式二：结合栈来实现
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode pointer = node;
    TreeNode pop = null;
    while (pointer != null || !stack.isEmpty()) {
        if (pointer != null) {
            stack.push(pointer);
            pointer = pointer.left;
        } else {
            TreeNode peek = stack.peek();//栈顶元素
            if (peek.right != null && peek.right != pop) {//有兄弟节点，不加 peek.right != pop 会进入死循环
                //一直找最左侧的节点
                pointer = peek.right;
            } else {
                pop = stack.pop();
                System.out.println(pop.val);
            }
        }
    }
}