数据结构之二叉树遍历

devtools/2024/11/13 10:33:28/

二叉树的遍历

二叉树

先序遍历

先输入父节点，再遍历左子树和右子树：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;}
}