C# 使用 List 栈模拟实现二叉树非递归先序遍历

原理概述

二叉树的先序遍历顺序为“根-左-右”。在递归实现中，系统调用栈自动保存了访问状态；而在非递归实现中，我们需要显式地使用一个容器（如 List<Node>）来充当栈，手动管理节点的入栈和出栈操作，以记录当前路径和回溯点。

第1步：定义二叉树节点类

首先需要定义一个基本的二叉树节点结构，包含存储数据的属性以及指向左右子节点的引用。

class Node
{
    public string Data { get; set; }
    public Node leftSon { get; set; }
    public Node rightSon { get; set; }
    public Node(string data)
    {
        Data = data;
    }
}

第2步：构建测试二叉树

为了验证遍历算法，创建一个包含多个节点的示例树。该树结构如下：

• 根节点 A，左子 B，右子 C
• B 的左 D、右 E
• C 的左 F、右 G
• D 的左 H、右 I

对应的创建代码如下：

private static Node CreateTree()
{
    Node a = new Node("A");
    a.leftSon = new Node("B");
    a.rightSon = new Node("C");
    a.leftSon.leftSon = new Node("D");
    a.leftSon.rightSon = new Node("E");
    a.rightSon.leftSon = new Node("F");
    a.rightSon.rightSon = new Node("G");
    a.leftSon.leftSon.leftSon = new Node("H");
    a.leftSon.leftSon.rightSon = new Node("I");
    return a;
}

第3步：实现非递归遍历逻辑

核心方法是 scanTree。其逻辑依赖于 List 作为栈，始终将栈顶元素（list[list.Count - 1]）视为当前处理的父节点（treeRoot），并通过 point 变量记录刚刚访问过的节点，用于判断是否需要回溯到父节点。

private static void scanTree(Node treeRoot)
{
    if (treeRoot == null) return;

    List<Node> list = new List<Node>();
    list.Add(treeRoot);
    Node point = treeRoot;
    Write(treeRoot);

    while (true)
    {
        // 检查当前栈顶节点是否就是上一轮刚访问过的节点
        if (!list.Contains(point))
        {
            // 说明上一轮执行了移除操作，或者是从子节点回溯上来
            if (treeRoot.leftSon == point)
            {
                // 如果上一个被移除的是左子节点
                if (treeRoot.rightSon != null)
                {
                    // 转向右子节点
                    treeRoot = treeRoot.rightSon;
                    list.Add(treeRoot);
                    Write(treeRoot);
                    point = treeRoot;
                    continue;
                }
                // 无右子节点，弹出当前栈顶（父节点）
                list.Remove(treeRoot);
                if (list.Count == 0) break;
                point = treeRoot;
                treeRoot = list[list.Count - 1];
            }
            else
            {
                // 如果上一个被移除的是右子节点
                list.Remove(treeRoot);
                if (list.Count == 0) break;
                point = treeRoot;
                treeRoot = list[list.Count - 1];
            }
            continue;
        }

        // 如果还没处理左子节点，且有左子节点
        if (treeRoot.leftSon != null)
        {
            treeRoot = treeRoot.leftSon;
            Write(treeRoot);
            list.Add(treeRoot);
            point = treeRoot;
            continue;
        }

        // 如果没有左子节点，但有右子节点
        if (treeRoot.rightSon != null)
        {
            treeRoot = treeRoot.rightSon;
            Write(treeRoot);
            point = treeRoot;
            list.Add(treeRoot);
            continue;
        }

        // 左右子节点都为空（叶子节点），且未进入上面的移除逻辑
        // 此时需弹出叶子节点，回溯到父节点
        list.Remove(treeRoot);
        if (list.Count == 0) break;
        point = treeRoot;
        treeRoot = list[list.Count - 1];
    }
}

public static void Write(Node node)
{
    Console.WriteLine(node.Data);
}

代码关键点解析

1. 栈的状态维护：
List<Node> list 始终保存从根节点到当前正在探索节点的祖先路径。treeRoot 变量实际上总是指向 list.Last() 的元素，即当前的“活跃”父节点。

2. 回溯的判断机制：
引入 point 变量非常关键。因为 list.Contains(point) 为 false 意味着 point 已经被从列表中移除了。通过判断 treeRoot.leftSon == point 还是 rightSon == point，程序可以知道刚才访问完的是左子树还是右子树，从而决定下一步是访问兄弟子树还是向上返回。

3. 循环终止条件：
当栈为空时（list.Count == 0），表示所有节点均已处理完毕，循环结束。

注意事项

• 性能考量：示例中使用 list.Remove(item) 基于值查找，对于大型链表效率较低。在生产环境中，建议使用标准的 Stack<T> 类并配合辅助映射表来替代 List.Contains 和 Remove 操作，以获得更优的时间复杂度。
• 空指针检查：确保传入的根节点不为 null，否则应直接返回或抛出异常。

以上就是使用C# List模拟栈进行二叉树非递归先序遍历的详细内容，更多关于C#二叉树算法的资料请关注本站其它相关文章！