发布于 由admin

手写实现一个自定义的深度遍历（DFS）与广度遍历（BFS）算法：针对树形对象结构

树形结构是计算机科学中最常见也是最重要的非线性数据结构之一。它以层次化的方式组织数据，广泛应用于文件系统、数据库索引、网络路由、编译器语法分析等众多领域。对树进行操作的核心技术之一就是遍历（Traversal），即系统地访问树中的每一个节点一次。深度优先搜索（DFS）和广度优先搜索（BFS）是两种最基本也是最强大的遍历策略，它们为解决各种树形问题提供了基础框架。

本文将深入探讨如何手写实现针对自定义树形对象结构的DFS和BFS算法。我们将从定义一个通用的树节点结构开始，然后详细讲解DFS和BFS的原理、递归与迭代实现、各自的特点、适用场景以及如何在实际应用中进行定制化。

1. 定义自定义树形结构

在实现遍历算法之前，我们首先需要一个清晰、可操作的树节点定义。为了实现通用性，我们考虑N叉树（N-ary Tree），即每个节点可以有任意数量的子节点。

一个典型的树节点至少需要包含两个基本属性：

  1. 节点值 (Value): 存储该节点的数据。
  2. 子节点列表 (Children): 存储指向其所有子节点的引用。

以下是使用Python、JavaScript和Java定义这样一个节点结构的示例。

Python 示例

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = [] # A list to hold child TreeNode objects

    def add_child(self, child_node):
        if not isinstance(child_node, TreeNode):
            raise TypeError("Child must be a TreeNode instance")
        self.children.append(child_node)

    def __repr__(self):
        return f"TreeNode({self.value})"

# 示例：构建一个简单的树
#       A
#      /|
#     B C D
#    /    |
#   E   F  G
#
# root = TreeNode('A')
# node_b = TreeNode('B')
# node_c = TreeNode('C')
# node_d = TreeNode('D')
# node_e = TreeNode('E')
# node_f = TreeNode('F')
# node_g = TreeNode('G')
#
# root.add_child(node_b)
# root.add_child(node_c)
# root.add_child(node_d)
#
# node_b.add_child(node_e)
# node_b.add_child(node_f)
#
# node_d.add_child(node_g)

JavaScript 示例

class TreeNode {
    constructor(value) {
        this.value = value;
        this.children = []; // An array to hold child TreeNode objects
    }

    addChild(childNode) {
        if (!(childNode instanceof TreeNode)) {
            throw new Error("Child must be a TreeNode instance");
        }
        this.children.push(childNode);
    }

    toString() {
        return `TreeNode(${this.value})`;
    }
}

// 示例：构建一个简单的树
/*
//       A
//      /|
//     B C D
//    /    |
//   E   F  G
//
// const root = new TreeNode('A');
// const nodeB = new TreeNode('B');
// const nodeC = new TreeNode('C');
// const nodeD = new TreeNode('D');
// const nodeE = new TreeNode('E');
// const nodeF = new TreeNode('F');
// const nodeG = new TreeNode('G');
//
// root.addChild(nodeB);
// root.addChild(nodeC);
// root.addChild(nodeD);
//
// nodeB.addChild(nodeE);
// nodeB.addChild(nodeF);
//
// nodeD.addChild(nodeG);
*/

Java 示例

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

class TreeNode {
    Object value; // Using Object for generic value type
    List<TreeNode> children; // A list to hold child TreeNode objects

    public TreeNode(Object value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    public void addChild(TreeNode childNode) {
        if (childNode == null) {
            throw new IllegalArgumentException("Child node cannot be null");
        }
        this.children.add(childNode);
    }

    public Object getValue() {
        return value;
    }

    public List<TreeNode> getChildren() {
        return children;
    }

    @Override
    public String toString() {
        return "TreeNode(" + value + ")";
    }
}

/*
// 示例：构建一个简单的树
//       A
//      /|
//     B C D
//    /    |
//   E   F  G
//
// TreeNode root = new TreeNode("A");
// TreeNode nodeB = new TreeNode("B");
// TreeNode nodeC = new TreeNode("C");
// TreeNode nodeD = new TreeNode("D");
// TreeNode nodeE = new TreeNode("E");
// TreeNode nodeF = new TreeNode("F");
// TreeNode nodeG = new TreeNode("G");
//
// root.addChild(nodeB);
// root.addChild(nodeC);
// root.addChild(nodeD);
//
// nodeB.addChild(nodeE);
// nodeB.addChild(nodeF);
//
// nodeD.addChild(nodeG);
*/

通过这些定义，我们有了一个统一的接口来构建和操作树。接下来，我们将基于这个结构实现DFS和BFS。

2. 深度优先搜索 (DFS)

深度优先搜索是一种沿着树的深度方向遍历树的策略。它尽可能深地探索树的分支，直到到达叶子节点或不能再深入为止，然后回溯到上一个节点，继续探索其他分支。DFS的核心思想是“一头扎到底”。

2.1 DFS 原理与直观理解

想象你正在一个迷宫中寻找出口。DFS的策略是选择一条路径，一直走下去，直到遇到死胡同。如果走到死胡同，就原路返回，直到遇到一个之前有岔路口的地方，然后选择另一条未探索的路径继续深入。这个“走到底再返回”的过程就是深度优先。

在数据结构层面，DFS通常使用栈（Stack）来实现。栈的LIFO（Last-In, First-Out）特性天然地支持这种“深入”和“回溯”的行为。当使用递归实现时，语言的函数调用栈就充当了这个隐式的栈。

2.2 递归实现 DFS (隐式栈)

递归是实现DFS最简洁、最直观的方式。函数的调用栈会自动管理待访问的节点和回溯点。

核心逻辑：

  1. 访问当前节点。
  2. 对当前节点的每一个子节点，递归地调用DFS函数。

这种遍历方式通常被称为“前序遍历”（Pre-order Traversal），因为节点在处理其子节点之前被访问。对于N叉树，这是最常见的递归DFS形式。

Python 递归 DFS 示例

class TreeNode:
    # ... (之前的 TreeNode 定义) ...
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child_node):
        self.children.append(child_node)

    def __repr__(self):
        return f"TreeNode({self.value})"

def custom_dfs_recursive(root_node, visitor_func):
    """
    递归实现的深度优先搜索 (前序遍历)。
    :param root_node: 树的根节点。
    :param visitor_func: 一个函数，用于处理当前访问的节点。
                         例如：lambda node: print(node.value)
    """
    if root_node is None:
        return

    # 1. 访问当前节点 (前序行为)
    visitor_func(root_node)

    # 2. 递归访问所有子节点
    for child in root_node.children:
        custom_dfs_recursive(child, visitor_func)

# 示例用法
# 构建树：
#       A
#      /|
#     B C D
#    /    |
#   E   F  G
root = TreeNode('A')
node_b = TreeNode('B')
node_c = TreeNode('C')
node_d = TreeNode('D')
node_e = TreeNode('E')
node_f = TreeNode('F')
node_g = TreeNode('G')

root.add_child(node_b)
root.add_child(node_c)
root.add_child(node_d)

node_b.add_child(node_e)
node_b.add_child(node_f)

node_d.add_child(node_g)

print("Python Recursive DFS (Pre-order):")
# 定义一个简单的访问函数来打印节点值
def print_node_value(node):
    print(node.value, end=" ")

custom_dfs_recursive(root, print_node_value) # 预期输出: A B E F C D G
print("n")

# 示例：定制化DFS - 收集所有节点的值
all_values = []
custom_dfs_recursive(root, lambda node: all_values.append(node.value))
print(f"Collected all values (Python): {all_values}") # 预期输出: ['A', 'B', 'E', 'F', 'C', 'D', 'G']

# 示例：定制化DFS - 查找特定值的节点
def find_node_by_value_dfs_recursive(root, target_value):
    if root is None:
        return None
    if root.value == target_value:
        return root
    for child in root.children:
        found_node = find_node_by_value_dfs_recursive(child, target_value)
        if found_node:
            return found_node
    return None

target_node = find_node_by_value_dfs_recursive(root, 'F')
print(f"Found node with value 'F' (Python): {target_node}") # 预期输出: TreeNode(F)

JavaScript 递归 DFS 示例

class TreeNode {
    // ... (之前的 TreeNode 定义) ...
    constructor(value) {
        this.value = value;
        this.children = [];
    }

    addChild(childNode) {
        this.children.push(childNode);
    }

    toString() {
        return `TreeNode(${this.value})`;
    }
}

function customDfsRecursive(rootNode, visitorFunc) {
    /**
     * 递归实现的深度优先搜索 (前序遍历)。
     * @param {TreeNode} rootNode - 树的根节点。
     * @param {Function} visitorFunc - 一个函数，用于处理当前访问的节点。
     *                                 例如：(node) => console.log(node.value)
     */
    if (!rootNode) {
        return;
    }

    // 1. 访问当前节点 (前序行为)
    visitorFunc(rootNode);

    // 2. 递归访问所有子节点
    for (const child of rootNode.children) {
        customDfsRecursive(child, visitorFunc);
    }
}

// 示例用法
// 构建树 (与Python示例相同结构)
const root = new TreeNode('A');
const nodeB = new TreeNode('B');
const nodeC = new TreeNode('C');
const nodeD = new TreeNode('D');
const nodeE = new TreeNode('E');
const nodeF = new TreeNode('F');
const nodeG = new TreeNode('G');

root.addChild(nodeB);
root.addChild(nodeC);
root.addChild(nodeD);

nodeB.addChild(nodeE);
nodeB.addChild(nodeF);

nodeD.addChild(nodeG);

console.log("JavaScript Recursive DFS (Pre-order):");
// 定义一个简单的访问函数来打印节点值
function printNodeValue(node) {
    process.stdout.write(node.value + " "); // 使用 process.stdout.write 避免换行
}

customDfsRecursive(root, printNodeValue); // 预期输出: A B E F C D G
console.log("n");

// 示例：定制化DFS - 收集所有节点的值
const allValuesJS = [];
customDfsRecursive(root, (node) => allValuesJS.push(node.value));
console.log(`Collected all values (JavaScript): ${allValuesJS}`); // 预期输出: ['A', 'B', 'E', 'F', 'C', 'D', 'G']

// 示例：定制化DFS - 查找特定值的节点
function findNodeByValueDfsRecursive(root, targetValue) {
    if (!root) {
        return null;
    }
    if (root.value === targetValue) {
        return root;
    }
    for (const child of root.children) {
        const foundNode = findNodeByValueDfsRecursive(child, targetValue);
        if (foundNode) {
            return foundNode;
        }
    }
    return null;
}

const targetNodeJS = findNodeByValueDfsRecursive(root, 'F');
console.log(`Found node with value 'F' (JavaScript): ${targetNodeJS}`); // 预期输出: TreeNode(F)

Java 递归 DFS 示例

import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer; // 用于定制化访问函数

class TreeNode {
    // ... (之前的 TreeNode 定义) ...
    Object value;
    List<TreeNode> children;

    public TreeNode(Object value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    public void addChild(TreeNode childNode) {
        this.children.add(childNode);
    }

    public Object getValue() {
        return value;
    }

    public List<TreeNode> getChildren() {
        return children;
    }

    @Override
    public String toString() {
        return "TreeNode(" + value + ")";
    }
}

public class DFSTraversal {

    public static void customDfsRecursive(TreeNode rootNode, Consumer<TreeNode> visitorFunc) {
        /**
         * 递归实现的深度优先搜索 (前序遍历)。
         * @param rootNode - 树的根节点。
         * @param visitorFunc - 一个函数，用于处理当前访问的节点。
         *                      例如：node -> System.out.print(node.getValue() + " ")
         */
        if (rootNode == null) {
            return;
        }

        // 1. 访问当前节点 (前序行为)
        visitorFunc.accept(rootNode);

        // 2. 递归访问所有子节点
        for (TreeNode child : rootNode.children) {
            customDfsRecursive(child, visitorFunc);
        }
    }

    // 示例：定制化DFS - 查找特定值的节点
    public static TreeNode findNodeByValueDfsRecursive(TreeNode root, Object targetValue) {
        if (root == null) {
            return null;
        }
        if (root.getValue().equals(targetValue)) {
            return root;
        }
        for (TreeNode child : root.getChildren()) {
            TreeNode foundNode = findNodeByValueDfsRecursive(child, targetValue);
            if (foundNode != null) {
                return foundNode;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        // 构建树 (与Python示例相同结构)
        TreeNode root = new TreeNode("A");
        TreeNode nodeB = new TreeNode("B");
        TreeNode nodeC = new TreeNode("C");
        TreeNode nodeD = new TreeNode("D");
        TreeNode nodeE = new TreeNode("E");
        TreeNode nodeF = new TreeNode("F");
        TreeNode nodeG = new TreeNode("G");

        root.addChild(nodeB);
        root.addChild(nodeC);
        root.addChild(nodeD);

        nodeB.addChild(nodeE);
        nodeB.addChild(nodeF);

        nodeD.addChild(nodeG);

        System.out.println("Java Recursive DFS (Pre-order):");
        // 定义一个简单的访问函数来打印节点值
        customDfsRecursive(root, node -> System.out.print(node.getValue() + " ")); // 预期输出: A B E F C D G
        System.out.println("n");

        // 示例：定制化DFS - 收集所有节点的值
        List<Object> allValuesJava = new ArrayList<>();
        customDfsRecursive(root, node -> allValuesJava.add(node.getValue()));
        System.out.println("Collected all values (Java): " + allValuesJava); // 预期输出: ['A', 'B', 'E', 'F', 'C', 'D', 'G']

        TreeNode targetNodeJava = findNodeByValueDfsRecursive(root, "F");
        System.out.println("Found node with value 'F' (Java): " + targetNodeJava); // 预期输出: TreeNode(F)
    }
}

递归DFS的优缺点：

  • 优点： 代码简洁、易于理解，符合直观的“向下探索”思维。
  • 缺点： 存在栈溢出的风险，当树的深度非常大时（例如几十万层），函数调用栈可能会耗尽。难以控制遍历的中间状态或在遍历过程中终止。

2.3 迭代实现 DFS (显式栈)

为了避免递归深度限制，或者需要更精细地控制遍历过程，我们可以使用一个显式的栈来模拟递归的行为。

核心逻辑：

  1. 创建一个栈，并将根节点压入栈中。
  2. 当栈不为空时：
    a. 弹出栈顶节点 current_node。
    b. 访问 current_node。
    c. 将 current_node 的所有子节点（通常是逆序）压入栈中。逆序压入是为了确保它们在后续被弹出时能按照从左到右（或指定顺序）被处理。

Python 迭代 DFS 示例

from collections import deque # deque for efficient stack operations

def custom_dfs_iterative(root_node, visitor_func):
    """
    迭代实现的深度优先搜索 (前序遍历)。
    :param root_node: 树的根节点。
    :param visitor_func: 一个函数，用于处理当前访问的节点。
    """
    if root_node is None:
        return

    stack = deque() # 使用 deque 作为栈
    stack.append(root_node)

    while stack:
        current_node = stack.pop() # 弹出栈顶节点
        visitor_func(current_node) # 访问当前节点

        # 将子节点逆序压入栈，以确保它们按正确的顺序（从左到右）被访问
        # 如果子节点是 [c1, c2, c3]，逆序压入栈则栈中为 [c3, c2, c1]
        # 下一个弹出的是 c1，实现了前序遍历从左到右的顺序
        for child in reversed(current_node.children):
            stack.append(child)

print("Python Iterative DFS (Pre-order):")
custom_dfs_iterative(root, print_node_value) # 预期输出: A B E F C D G
print("n")

# 示例：定制化DFS - 收集所有节点的值
all_values_iter = []
custom_dfs_iterative(root, lambda node: all_values_iter.append(node.value))
print(f"Collected all values (Python Iterative): {all_values_iter}") # 预期输出: ['A', 'B', 'E', 'F', 'C', 'D', 'G']

# 示例：定制化DFS - 查找特定值的节点
def find_node_by_value_dfs_iterative(root, target_value):
    if root is None:
        return None

    stack = deque()
    stack.append(root)

    while stack:
        current_node = stack.pop()
        if current_node.value == target_value:
            return current_node

        for child in reversed(current_node.children):
            stack.append(child)
    return None

target_node_iter = find_node_by_value_dfs_iterative(root, 'F')
print(f"Found node with value 'F' (Python Iterative): {target_node_iter}") # 预期输出: TreeNode(F)

JavaScript 迭代 DFS 示例

function customDfsIterative(rootNode, visitorFunc) {
    /**
     * 迭代实现的深度优先搜索 (前序遍历)。
     * @param {TreeNode} rootNode - 树的根节点。
     * @param {Function} visitorFunc - 一个函数，用于处理当前访问的节点。
     */
    if (!rootNode) {
        return;
    }

    const stack = []; // 使用数组作为栈
    stack.push(rootNode);

    while (stack.length > 0) {
        const currentNode = stack.pop(); // 弹出栈顶节点
        visitorFunc(currentNode); // 访问当前节点

        // 将子节点逆序压入栈
        // 注意：JavaScript的pop()和push()操作数组尾部，
        // 所以为了实现从左到右访问子节点，我们需要将子节点从右到左压入栈。
        for (let i = currentNode.children.length - 1; i >= 0; i--) {
            stack.push(currentNode.children[i]);
        }
    }
}

console.log("JavaScript Iterative DFS (Pre-order):");
customDfsIterative(root, printNodeValue); // 预期输出: A B E F C D G
console.log("n");

// 示例：定制化DFS - 收集所有节点的值
const allValuesJSIter = [];
customDfsIterative(root, (node) => allValuesJSIter.push(node.value));
console.log(`Collected all values (JavaScript Iterative): ${allValuesJSIter}`); // 预期输出: ['A', 'B', 'E', 'F', 'C', 'D', 'G']

// 示例：定制化DFS - 查找特定值的节点
function findNodeByValueDfsIterative(root, targetValue) {
    if (!root) {
        return null;
    }

    const stack = [];
    stack.push(root);

    while (stack.length > 0) {
        const currentNode = stack.pop();
        if (currentNode.value === targetValue) {
            return currentNode;
        }

        for (let i = currentNode.children.length - 1; i >= 0; i--) {
            stack.push(currentNode.children[i]);
        }
    }
    return null;
}

const targetNodeJSIter = findNodeByValueDfsIterative(root, 'F');
console.log(`Found node with value 'F' (JavaScript Iterative): ${targetNodeJSIter}`); // 预期输出: TreeNode(F)

Java 迭代 DFS 示例

import java.util.Collections;
import java.util.Deque; // for Stack-like operations
import java.util.LinkedList; // for Deque implementation
import java.util.function.Consumer;

// ... (TreeNode 类定义) ...

public class DFSTraversal {
    // ... (customDfsRecursive, findNodeByValueDfsRecursive 方法) ...

    public static void customDfsIterative(TreeNode rootNode, Consumer<TreeNode> visitorFunc) {
        /**
         * 迭代实现的深度优先搜索 (前序遍历)。
         * @param rootNode - 树的根节点。
         * @param visitorFunc - 一个函数，用于处理当前访问的节点。
         */
        if (rootNode == null) {
            return;
        }

        Deque<TreeNode> stack = new LinkedList<>(); // 使用 LinkedList 作为 Deque (栈)
        stack.push(rootNode);

        while (!stack.isEmpty()) {
            TreeNode currentNode = stack.pop(); // 弹出栈顶节点
            visitorFunc.accept(currentNode); // 访问当前节点

            // 将子节点逆序压入栈
            // Java 的 Deque.push() 将元素添加到头部，pop() 从头部移除。
            // 因此，为了实现从左到右访问子节点，需要将子节点从右到左压入栈。
            List<TreeNode> children = new ArrayList<>(currentNode.getChildren()); // 创建副本以逆序
            Collections.reverse(children); // 逆序子节点列表
            for (TreeNode child : children) {
                stack.push(child);
            }
        }
    }

    // 示例：定制化DFS - 查找特定值的节点
    public static TreeNode findNodeByValueDfsIterative(TreeNode root, Object targetValue) {
        if (root == null) {
            return null;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode currentNode = stack.pop();
            if (currentNode.getValue().equals(targetValue)) {
                return currentNode;
            }

            List<TreeNode> children = new ArrayList<>(currentNode.getChildren());
            Collections.reverse(children);
            for (TreeNode child : children) {
                stack.push(child);
            }
        }
        return null;
    }

    public static void main(String[] args) {
        // ... (构建树代码) ...

        System.out.println("Java Iterative DFS (Pre-order):");
        customDfsIterative(root, node -> System.out.print(node.getValue() + " ")); // 预期输出: A B E F C D G
        System.out.println("n");

        // 示例：定制化DFS - 收集所有节点的值
        List<Object> allValuesJavaIter = new ArrayList<>();
        customDfsIterative(root, node -> allValuesJavaIter.add(node.getValue()));
        System.out.println("Collected all values (Java Iterative): " + allValuesJavaIter); // 预期输出: ['A', 'B', 'E', 'F', 'C', 'D', 'G']

        TreeNode targetNodeJavaIter = findNodeByValueDfsIterative(root, "F");
        System.out.println("Found node with value 'F' (Java Iterative): " + targetNodeJavaIter); // 预期输出: TreeNode(F)
    }
}

迭代DFS的优缺点：

  • 优点： 避免了递归深度限制，可以在非常深的树上安全运行。更容易在遍历过程中实现暂停、恢复或更复杂的逻辑控制。
  • 缺点： 代码通常比递归版本更冗长，需要手动管理栈。

2.4 DFS 变种：中序和后序遍历（N叉树的视角）

对于二叉树，我们有前序（根-左-右）、中序（左-根-右）和后序（左-右-根）遍历。对于N叉树，"中序"的概念并不那么直接，因为没有明确的“左”和“右”子节点。然而，我们可以泛化前序和后序的概念：

  • 前序遍历 (Pre-order): 访问根节点 -> 访问所有子节点（从左到右）。这是我们上面实现的默认DFS。
  • 后序遍历 (Post-order): 访问所有子节点（从左到右） -> 访问根节点。在处理完一个节点的所有后代之后才处理该节点。这对于释放资源、计算子树大小或删除树非常有用。

Python 后序遍历 DFS 示例 (递归)

def custom_dfs_post_order_recursive(root_node, visitor_func):
    """
    递归实现的深度优先搜索 (后序遍历)。
    """
    if root_node is None:
        return

    # 1. 递归访问所有子节点
    for child in root_node.children:
        custom_dfs_post_order_recursive(child, visitor_func)

    # 2. 访问当前节点 (后序行为)
    visitor_func(root_node)

print("Python Recursive DFS (Post-order):")
custom_dfs_post_order_recursive(root, print_node_value) # 预期输出: E F B C G D A
print("n")

Python 后序遍历 DFS 示例 (迭代)

迭代实现后序遍历比前序复杂一些，因为它需要在访问父节点之前确保所有子节点都被访问。一种常见的方法是使用两个栈，或者一个栈并记录节点的状态（是否所有子节点已处理）。

这里提供一个使用一个栈和“窥探”技巧的实现：

def custom_dfs_post_order_iterative(root_node, visitor_func):
    """
    迭代实现的深度优先搜索 (后序遍历)。
    """
    if root_node is None:
        return

    stack = deque()
    last_visited_node = None # 记录上一个被访问的节点

    while root_node or stack:
        # 将当前节点及其所有左侧子节点压入栈
        while root_node:
            stack.append(root_node)
            # 对于N叉树，没有明确的“左侧子节点”，我们将其第一个子节点视为“左侧”
            # 或者更通用的做法是，将其所有子节点逆序压入一个临时栈，然后处理
            # 这里的逻辑更接近于二叉树的后序遍历思想：先深入一个分支
            # 对于N叉树，要实现严格的后序迭代，通常需要更复杂的逻辑，
            # 比如跟踪每个节点已访问的子节点数量。
            # 为了简化，我们假定这里模拟的是二叉树的左侧深入逻辑，
            # 对于N叉树，通常递归更直接或使用双栈法。

            # 暂时简化为：如果第一个子节点存在，就深入第一个子节点
            # 严格N叉树后序遍历迭代需要更复杂的逻辑，这里展示的是一种简化思路
            if root_node.children:
                root_node = root_node.children[0]
            else:
                root_node = None # 没有子节点了，停止深入

        # 此时 root_node 为 None，栈顶是当前最深层的节点
        peek_node = stack[-1] # 窥探栈顶

        # 如果栈顶节点没有右子节点（对于N叉树，是除第一个子节点外的其他子节点）
        # 或者其右子节点已经被访问过，那么就可以访问栈顶节点
        # 这里的条件需要针对N叉树进行调整。
        # 一个更通用的迭代后序遍历（单栈）对于N叉树会比较复杂，
        # 通常采用双栈法或递归。

        # 为了N叉树的通用性，我们使用一个更直接的双栈法来展示迭代后序遍历
        # 这种单栈模拟二叉树后序遍历的思路对N叉树不直接适用
        break # 退出循环，因为这里需要切换到双栈法

# --------------------------------------------------------------------------
# 真正的N叉树迭代后序遍历（使用两个栈）
# stack1 用于模拟前序遍历的顺序（根-右-左），stack2 用于存储最终的后序遍历结果
# --------------------------------------------------------------------------
def custom_dfs_post_order_iterative_two_stacks(root_node, visitor_func):
    if root_node is None:
        return

    stack1 = deque()
    stack2 = deque() # 用于存储后序遍历的结果

    stack1.append(root_node)

    while stack1:
        current_node = stack1.pop()
        stack2.append(current_node) # 将当前节点压入结果栈

        # 将子节点从左到右压入 stack1
        # 这样在下次迭代中，右侧的子节点会先被处理 (LIFO)
        # 从而保证 stack2 中的顺序是 根-右-左 (被逆序后就是 左-右-根)
        for child in current_node.children:
            stack1.append(child)

    # 从 stack2 中弹出节点，即为后序遍历的顺序
    while stack2:
        visitor_func(stack2.pop())

print("Python Iterative DFS (Post-order, Two Stacks):")
custom_dfs_post_order_iterative_two_stacks(root, print_node_value) # 预期输出: E F B C G D A
print("n")

Java/JavaScript的迭代后序遍历也同样推荐使用双栈法，其逻辑与Python类似。

3. 广度优先搜索 (BFS)

广度优先搜索是一种逐层遍历树的策略。它首先访问所有位于同一深度的节点（即同一层级的节点），然后再移到下一层。BFS的核心思想是“一层一层地毯式搜索”。

3.1 BFS 原理与直观理解

想象你向池塘中投入一块石头，水波会从中心向外扩散。BFS的遍历方式就像这些水波，从起点（根节点）开始，首先访问所有直接相邻的节点（第一层），然后是所有距离为2的节点（第二层），以此类推。

在数据结构层面，BFS通常使用队列（Queue）来实现。队列的FIFO（First-In, First-Out）特性天然地支持这种“逐层”和“按顺序”访问的行为。

3.2 迭代实现 BFS (显式队列)

BFS几乎总是以迭代方式实现，因为递归难以直接表达“逐层”的概念，需要额外的数据结构来模拟层级。

核心逻辑：

  1. 创建一个队列，并将根节点加入队列。
  2. 当队列不为空时：
    a. 从队列头部取出一个节点 current_node。
    b. 访问 current_node。
    c. 将 current_node 的所有子节点（从左到右）依次加入队列尾部。

Python BFS 示例

from collections import deque # deque for efficient queue operations

def custom_bfs(root_node, visitor_func):
    """
    广度优先搜索。
    :param root_node: 树的根节点。
    :param visitor_func: 一个函数，用于处理当前访问的节点。
                         例如：lambda node: print(node.value)
    """
    if root_node is None:
        return

    queue = deque() # 使用 deque 作为队列
    queue.append(root_node)

    while queue:
        current_node = queue.popleft() # 从队列头部取出节点
        visitor_func(current_node) # 访问当前节点

        # 将所有子节点（从左到右）添加到队列尾部
        for child in current_node.children:
            queue.append(child)

print("Python BFS (Level-order):")
custom_bfs(root, print_node_value) # 预期输出: A B C D E F G
print("n")

# 示例：定制化BFS - 收集所有节点的值
all_values_bfs = []
custom_bfs(root, lambda node: all_values_bfs.append(node.value))
print(f"Collected all values (Python BFS): {all_values_bfs}") # 预期输出: ['A', 'B', 'C', 'D', 'E', 'F', 'G']

# 示例：定制化BFS - 查找特定值的节点 (BFS通常用于查找最短路径)
def find_node_by_value_bfs(root, target_value):
    if root is None:
        return None

    queue = deque()
    queue.append(root)

    while queue:
        current_node = queue.popleft()
        if current_node.value == target_value:
            return current_node

        for child in current_node.children:
            queue.append(child)
    return None

target_node_bfs = find_node_by_value_bfs(root, 'F')
print(f"Found node with value 'F' (Python BFS): {target_node_bfs}") # 预期输出: TreeNode(F)

JavaScript BFS 示例

function customBfs(rootNode, visitorFunc) {
    /**
     * 广度优先搜索。
     * @param {TreeNode} rootNode - 树的根节点。
     * @param {Function} visitorFunc - 一个函数，用于处理当前访问的节点。
     */
    if (!rootNode) {
        return;
    }

    const queue = []; // 使用数组作为队列
    queue.push(rootNode);

    while (queue.length > 0) {
        const currentNode = queue.shift(); // 从队列头部取出节点 (shift() 性能开销较大，实际应用可用链表实现队列)
        visitorFunc(currentNode); // 访问当前节点

        // 将所有子节点（从左到右）添加到队列尾部
        for (const child of currentNode.children) {
            queue.push(child);
        }
    }
}

console.log("JavaScript BFS (Level-order):");
customBfs(root, printNodeValue); // 预期输出: A B C D E F G
console.log("n");

// 示例：定制化BFS - 收集所有节点的值
const allValuesBFSJS = [];
customBfs(root, (node) => allValuesBFSJS.push(node.value));
console.log(`Collected all values (JavaScript BFS): ${allValuesBFSJS}`); // 预期输出: ['A', 'B', 'C', 'D', 'E', 'F', 'G']

// 示例：定制化BFS - 查找特定值的节点
function findNodeByValueBfs(root, targetValue) {
    if (!root) {
        return null;
    }

    const queue = [];
    queue.push(root);

    while (queue.length > 0) {
        const currentNode = queue.shift();
        if (currentNode.value === targetValue) {
            return currentNode;
        }

        for (const child of currentNode.children) {
            queue.push(child);
        }
    }
    return null;
}

const targetNodeBFSJS = findNodeByValueBfs(root, 'F');
console.log(`Found node with value 'F' (JavaScript BFS): ${targetNodeBFSJS}`); // 预期输出: TreeNode(F)

Java BFS 示例

import java.util.LinkedList;
import java.util.Queue; // for Queue interface
import java.util.function.Consumer;

// ... (TreeNode 类定义) ...

public class BFSTraversal {

    public static void customBfs(TreeNode rootNode, Consumer<TreeNode> visitorFunc) {
        /**
         * 广度优先搜索。
         * @param rootNode - 树的根节点。
         * @param visitorFunc - 一个函数，用于处理当前访问的节点。
         */
        if (rootNode == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>(); // 使用 LinkedList 作为 Queue
        queue.offer(rootNode); // offer() 相当于 add()，但失败时返回 false 而不是抛异常

        while (!queue.isEmpty()) {
            TreeNode currentNode = queue.poll(); // 从队列头部取出节点 (poll() 相当于 remove())
            visitorFunc.accept(currentNode); // 访问当前节点

            // 将所有子节点（从左到右）添加到队列尾部
            for (TreeNode child : currentNode.children) {
                queue.offer(child);
            }
        }
    }

    // 示例：定制化BFS - 查找特定值的节点
    public static TreeNode findNodeByValueBfs(TreeNode root, Object targetValue) {
        if (root == null) {
            return null;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode currentNode = queue.poll();
            if (currentNode.getValue().equals(targetValue)) {
                return currentNode;
            }

            for (TreeNode child : currentNode.getChildren()) {
                queue.offer(child);
            }
        }
        return null;
    }

    public static void main(String[] args) {
        // ... (构建树代码) ...

        System.out.println("Java BFS (Level-order):");
        customBfs(root, node -> System.out.print(node.getValue() + " ")); // 预期输出: A B C D E F G
        System.out.println("n");

        // 示例：定制化BFS - 收集所有节点的值
        List<Object> allValuesBFSJava = new ArrayList<>();
        customBfs(root, node -> allValuesBFSJava.add(node.getValue()));
        System.out.println("Collected all values (Java BFS): " + allValuesBFSJava); // 预期输出: ['A', 'B', 'C', 'D', 'E', 'F', 'G']

        TreeNode targetNodeBFSJava = findNodeByValueBfs(root, "F");
        System.out.println("Found node with value 'F' (Java BFS): " + targetNodeBFSJava); // 预期输出: TreeNode(F)
    }
}

BFS的优缺点：

  • 优点： 总是能找到从起始节点到目标节点的最短路径（在无权图中，以边数衡量）。适用于层级遍历，例如查找同一层级的所有节点。不会发生栈溢出。
  • 缺点： 队列可能会存储大量节点，尤其是在宽而浅的树中，可能导致内存消耗过大。

4. DFS 与 BFS 的比较

DFS和BFS是解决树和图遍历问题的两种基本方法，它们各有优势和适用场景。理解它们的异同对于选择合适的算法至关重要。

特性 深度优先搜索 (DFS) 广度优先搜索 (BFS)
数据结构 栈 (Stack) – 递归使用调用栈，迭代使用显式栈 队列 (Queue)
遍历顺序 尽可能深地探索分支，然后回溯。先访问子孙节点，再访问兄弟节点。 逐层访问，先访问所有兄弟节点，再访问子节点。
访问路径 沿着一条路径直到尽头。 从起点向外辐射，一层一层扩展。
最短路径 找到的路径不一定是起点到目标的最短路径。 在无权图中，总是能找到起点到目标的最短路径。
内存消耗 主要取决于树的深度 (height)。栈的最大深度与树的深度成正比。深而窄的树内存效率高。 主要取决于树的宽度 (width)。队列的最大大小与树的最大宽度成正比。浅而宽的树内存消耗大。
时间复杂度 O(V + E)，对于树来说是 O(N)，其中 V 是节点数，E 是边数，N 是节点总数。 O(V + E)，对于树来说是 O(N)。
适用场景 – 查找路径、检测环路 (在图中) – 查找最短路径 (无权图/树)
– 拓扑排序 – 查找所有在 K 步之内的节点
– 序列化/反序列化树 – 社交网络中查找最近的朋友
– 递归问题通常更适合DFS实现 – Web爬虫 (按层级发现链接)
实现方式 递归 (简洁，易于理解) 或 迭代 (避免栈溢出) 通常是迭代 (使用队列)

5. 高级定制化与应用考量

我们已经实现了基本的DFS和BFS，并通过visitor_func参数实现了初步的定制。在实际应用中，我们可能需要更复杂的定制能力：

  1. 带返回值的遍历： 有时遍历不仅仅是“访问”，还需要根据访问结果进行累积或决策。例如，计算子树的大小，或者查找满足特定条件的第一个节点。

    • 在递归DFS中，可以修改函数签名，让其返回结果。
    • 在迭代DFS/BFS中，可以在visitor_func内部修改外部变量，或者修改循环条件以在找到目标后立即返回。

  2. 停止条件： 在某些情况下，一旦找到目标或满足特定条件，我们希望立即停止遍历以提高效率。

    • 在递归DFS中，可以在visitor_func或递归调用前添加条件判断，并使用return来中断当前分支的探索，或抛出异常来完全停止。
    • 在迭代DFS/BFS中，可以在while循环内部添加条件判断，一旦满足就break退出循环。

  3. 路径记录： 对于路径查找问题，我们需要在遍历时记录从根节点到当前节点的路径。

    • 在递归DFS中，可以将当前路径作为参数传递给递归函数，并在回溯时移除当前节点。
    • 在迭代DFS/BFS中，可以在队列/栈中存储(节点, 父节点)对，或者(节点, 路径)对。

  4. 处理图而非树 (防循环)： 尽管本文主题是树，但在许多实际场景中，我们处理的可能是更通用的“图”，其中可能包含循环。在这种情况下，DFS和BFS都需要一个visited（已访问）集合来跟踪已经访问过的节点，以防止无限循环。对于严格意义上的树，由于没有循环，通常不需要visited集合。但如果你的“树形对象结构”可能存在父节点指向子节点之外的引用，或者结构是动态变化的，那么visited集合就必不可少。

示例：带停止条件的DFS (Python)

def find_first_node_dfs(root_node, predicate_func):
    """
    DFS查找满足特定条件的第一个节点，找到后立即停止。
    :param root_node: 树的根节点。
    :param predicate_func: 一个函数，接受一个节点，返回True表示满足条件，False表示不满足。
    :return: 满足条件的第一个节点，如果未找到则返回None。
    """
    if root_node is None:
        return None

    stack = deque()
    stack.append(root_node)

    while stack:
        current_node = stack.pop()
        if predicate_func(current_node):
            return current_node # 找到后立即停止并返回

        for child in reversed(current_node.children):
            stack.append(child)
    return None

# 查找第一个值大于'F'的节点
first_gt_F = find_first_node_dfs(root, lambda node: node.value > 'F')
print(f"First node with value > 'F' (DFS): {first_gt_F}") # 预期输出: TreeNode(G)

示例：BFS查找最短路径 (记录路径) (Python)

def find_path_bfs(root_node, target_value):
    """
    BFS查找从根节点到目标值的最短路径。
    :param root_node: 树的根节点。
    :param target_value: 目标节点的值。
    :return: 路径节点列表，如果未找到则返回None。
    """
    if root_node is None:
        return None

    queue = deque()
    # 队列中存储 (节点, 当前路径) 对
    queue.append((root_node, [root_node.value]))

    while queue:
        current_node, path = queue.popleft()

        if current_node.value == target_value:
            return path # 找到目标，返回路径

        for child in current_node.children:
            new_path = list(path) # 创建新路径副本
            new_path.append(child.value)
            queue.append((child, new_path))
    return None

path_to_g = find_path_bfs(root, 'G')
print(f"Shortest path to 'G' (BFS): {path_to_g}") # 预期输出: ['A', 'D', 'G']

path_to_e = find_path_bfs(root, 'E')
print(f"Shortest path to 'E' (BFS): {path_to_e}") # 预期输出: ['A', 'B', 'E']

DFS和BFS是理解和操作树形结构的基础。通过递归和迭代两种实现方式，我们能够灵活应对不同的场景。DFS因其“一头扎到底”的特性，常用于需要探索所有可能路径或处理深层结构的问题，而BFS则以其“逐层探索”的特性，成为查找最短路径或进行层级处理的首选。掌握这两种算法及其定制化方法，是成为一名优秀编程专家的必备技能。无论是文件系统导航、网页爬取、游戏AI路径规划还是编译器设计，DFS和BFS都扮演着不可或缺的角色。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注