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

数据结构之二叉树遍历

article 2024/11/15 17:30:45

二叉树的遍历

二叉树

先序遍历

先输入父节点，再遍历左子树和右子树：A、B、D、E、C、F、G

中序遍历

先遍历左子树，再输出父节点，再遍历右子树：D、B、E、A、F、C、G

后序遍历

先遍历左子树，再遍历右子树，最后输入父节点：D、E、B、F、G、C、A

核心理论

根据父节点的输出顺序来确定先序、中序、后续。
采用递归的方式对左子树和右子树进行遍历。
- 每次递归都是一个方法的入栈操作，直至到最后一个子节点为空的时候，执行方法，然后方法栈弹出。
- 每个方法栈弹出后，开始执行下一个方法栈，以此类推，相应的方法则可输出。

代码实现

package org.example.data.structure.basetree;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @author xzy
 * @since 2024/9/16 15:14
 */
public class PersonNode {

    private static final List<Person> PRE_ORDER_LIST = new ArrayList<>();

    private static final List<Person> MID_ORDER_LIST = new ArrayList<>();

    private static final List<Person> POST_ORDER_LIST = new ArrayList<>();

    private Person data;

    private PersonNode left;

    private PersonNode right;

    public PersonNode() {
    }

    public PersonNode(Person person) {
        this.data = person;
    }

    public PersonNode(Person data, PersonNode left, PersonNode right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    /**
     * 前序遍历
     */
    public List<Person> preOrder() {
        PRE_ORDER_LIST.add(this.getData());
        if (Objects.nonNull(this.getLeft())) {
            this.getLeft().preOrder();
        }
        if (Objects.nonNull(this.getRight())) {
            this.getRight().preOrder();
        }
        return PRE_ORDER_LIST;
    }

    /**
     * 中序遍历
     */
    public List<Person> midOrder() {
        if (Objects.nonNull(this.getLeft())) {
            this.getLeft().midOrder();
        }
        MID_ORDER_LIST.add(this.getData());
        if (Objects.nonNull(this.getRight())) {
            this.getRight().midOrder();
        }
        return MID_ORDER_LIST;
    }

    /**
     * 后续遍历
     */
    public List<Person> postOrder() {
        if (Objects.nonNull(this.getLeft())) {
            this.getLeft().postOrder();
        }
        if (Objects.nonNull(this.getRight())) {
            this.getRight().postOrder();
        }
        POST_ORDER_LIST.add(this.getData());
        return POST_ORDER_LIST;
    }

    public Person getData() {
        return data;
    }

    public void setData(Person data) {
        this.data = data;
    }

    public PersonNode getLeft() {
        return left;
    }

    public void setLeft(PersonNode left) {
        this.left = left;
    }

    public PersonNode getRight() {
        return right;
    }

    public void setRight(PersonNode right) {
        this.right = right;
    }
}