节点结构：
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {
}
public TreeNode(int x) {
val = x;
}
}
先序遍历
递归
public void preOrder(TreeNode tree) {
if (tree == null)
return;
processNode(tree); // 处理节点的逻辑抽象
preOrder(tree.left);
preOrder(tree.right);
}
非递归
public void preOrder(TreeNode tree) {
if (tree == null)
return;
Stack<TreeNode> s = new Stack<>();
s.push(tree);
while (!s.isEmpty()) {
TreeNode node = s.pop();
processNode(node); // 处理节点的逻辑抽象
if (node.right != null) { // 先入栈右子节点
s.push(node.right);
}
if (node.left != null) {
s.push(node.left);
}
}
}
后序遍历
递归
public void postOrder(TreeNode tree) {
if (tree == null)
return;
postOrder(tree.left);
postOrder(tree.right);
processNode(tree); // 处理节点的逻辑抽象
}
非递归
public void postOrder(TreeNode tree) {
if (tree == null)
return;
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
s1.push(tree);
while (!s1.isEmpty()) {
tree = s1.pop();
s2.push(tree);
if (tree.left != null) {
s1.push(tree.left); // 先入栈左子节点
}
if (tree.right != null) {
s1.push(tree.right);
}
}
while (!s2.isEmpty()) {
processNode(s2.pop()); // 处理节点的逻辑抽象
}
}
中序遍历
递归
public void inOrder(TreeNode tree) {
if (tree == null)
return;
inOrder(tree.left);
processNode(tree); // 处理节点的逻辑抽象
inOrder(tree.right);
}
非递归
public void inOrder(TreeNode tree) {
Stack<TreeNode> s = new Stack<>();
while (tree != null || !s.isEmpty()) {
while (tree != null) {
s.push(tree);
tree = tree.left;
}
if (!s.isEmpty()) {
tree = s.pop();
processNode(tree); // 处理节点的逻辑抽象
tree = tree.right;
}
}
}
层序遍历
public void levelOrder(TreeNode tree) {
if (tree == null)
return;
Queue<TreeNode> q = new LinkedList<>();
q.add(tree);
while (!q.isEmpty()) {
tree = q.poll();
processNode(tree); // 处理节点的逻辑抽象
if (tree.left != null)
q.add(tree.left);
if (tree.right != null)
q.add(tree.right);
}
}
类库
有了上述遍历算法实现后，我们建立类库，主要是：（1）通过泛型增加程序的通用性，（2）面向接口编程，（3）能够被实际开发生产使用。
@FunctionalInterface
public interface Node<T> {
T getValue();
}
import lombok.*;
@Data
@NoArgsConstructor
@AllArgsConstructor
@RequiredArgsConstructor
public class TreeNode<T> implements Node<T> {
@NonNull protected T value;
protected TreeNode left;
protected TreeNode right;
}
@FunctionalInterface
public interface Visitor<T> {
void process(Node<T> node);
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
@FunctionalInterface
public interface TreeVisitor<T> extends Visitor<T> {
default void preOrder(TreeNode<T> tree) {
preOrder(tree, false);
}
default void preOrder(TreeNode<T> tree, boolean recursive) {
if (recursive)
preOrderRecursive(tree);
else
preOrderNonRecursive(tree);
}
default void preOrderRecursive(TreeNode<T> tree) {
if (tree == null)
return;
process(tree);
preOrderRecursive(tree.getLeft());
preOrderRecursive(tree.right);
}
default void preOrderNonRecursive(TreeNode<T> tree) {
if (tree == null)
return;
Stack<TreeNode<T>> s = new Stack<>();
s.push(tree);
while (!s.isEmpty()) {
TreeNode<T> node = s.pop();
process(node);
if (node.right != null) { // 先入栈右子节点
s.push(node.right);
}
if (node.left != null) {
s.push(node.left);
}
}
}
default void postOrder(TreeNode<T> tree) {
postOrder(tree, false);
}
default void postOrder(TreeNode<T> tree, boolean recursive) {
if (recursive)
postOrderRecursive(tree);
else
postOrderNonRecursive(tree);
}
default void postOrderRecursive(TreeNode<T> tree) {
if (tree == null)
return;
postOrderRecursive(tree.left);
postOrderRecursive(tree.right);
process(tree);
}
default void postOrderNonRecursive(TreeNode<T> tree) {
if (tree == null)
return;
Stack<TreeNode<T>> s1 = new Stack<>();
Stack<TreeNode<T>> s2 = new Stack<>();
s1.push(tree);
while (!s1.isEmpty()) {
tree = s1.pop();
s2.push(tree);
if (tree.left != null) {
s1.push(tree.left); // 先入栈左子节点
}
if (tree.right != null) {
s1.push(tree.right);
}
}
while (!s2.isEmpty()) {
process(s2.pop());
}
}
default void inOrder(TreeNode<T> tree) {
inOrder(tree, false);
}
default void inOrder(TreeNode<T> tree, boolean recursive) {
if (recursive)
inOrderRecursive(tree);
else
inOrderNonRecursive(tree);
}
default void inOrderRecursive(TreeNode<T> tree) {
if (tree == null)
return;
inOrderRecursive(tree.left);
process(tree);
inOrderRecursive(tree.right);
}
default void inOrderNonRecursive(TreeNode<T> tree) {
Stack<TreeNode<T>> s = new Stack<>();
while (tree != null || !s.isEmpty()) {
while (tree != null) {
s.push(tree);
tree = tree.left;
}
if (!s.isEmpty()) {
tree = s.pop();
process(tree);
tree = tree.right;
}
}
}
default void levelOrder(TreeNode<T> tree) {
if (tree == null)
return;
Queue<TreeNode<T>> q = new LinkedList<>();
q.add(tree);
while (!q.isEmpty()) {
tree = q.poll();
process(tree);
if (tree.left != null)
q.add(tree.left);
if (tree.right != null)
q.add(tree.right);
}
}
}
在测试中使用上面的类库：
import org.junit.jupiter.api.Test;
public class TestClass {
@Test
void test1() {
TreeVisitor<Integer> visitor = (n) -> System.out.println(n.getValue());
TreeNode<Integer> left = new TreeNode<>(2);
TreeNode<Integer> right = new TreeNode<>(3);
TreeNode<Integer> root = new TreeNode<>(1, left, right);
visitor.inOrder(root);
}
@Test
void test2() {
TreeVisitor<Integer> visitor = node -> {
TreeNode<Integer> tn = (TreeNode<Integer>) node;
System.out.println(tn.getLeft());
};
TreeNode<Integer> left = new TreeNode<>(2);
TreeNode<Integer> right = new TreeNode<>(3);
TreeNode<Integer> root = new TreeNode<>(1, left, right);
visitor.inOrder(root);
}
}
网友评论