C#非递归先序遍历二叉树实例

本文将介绍如何用C#实现非递归的先序遍历二叉树，并给出两个具体的实例说明。

前置知识

在阅读本文前，需要先了解二叉树的相关定义和先序遍历的实现方式，以及C#的基本语法。

非递归先序遍历

对于一颗二叉树，其先序遍历的过程就是先遍历根节点，然后递归地遍历左子树和右子树。而非递归的先序遍历，可以通过使用栈来实现。

具体实现过程如下：
1. 创建一个栈，将根节点入栈。
2. 循环进行以下操作：
1. 从栈顶弹出一个节点，并访问该节点。
2. 将该节点的右子节点（如果有）入栈。
3. 将该节点的左子节点（如果有）入栈。
4. 当栈为空时，终止循环。

示例说明

示例 1

假如现在有一颗二叉树，其结构如下：

        1
       / \
      2   3
     /   / \
    4   5   6
           / \
          7   8

通过非递归先序遍历，输出该二叉树的节点值，输出结果应该为：1 2 4 3 5 6 7 8。

下面是实现该功能的C#代码：

using System;
using System.Collections.Generic;

class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int val) {
        this.value = val;
    }
}

class Program {
    static void Main(string[] args) {
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);

        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node3.left = node5;
        node3.right = node6;
        node6.left = node7;
        node6.right = node8;

        PreOrderTraversal(root);
    }

    static void PreOrderTraversal(Node root) {
        Stack<Node> stack = new Stack<Node>();
        stack.Push(root);

        while (stack.Count != 0) {
            Node node = stack.Pop();
            Console.Write(node.value + " ");

            if (node.right != null) {
                stack.Push(node.right);
            }
            if (node.left != null) {
                stack.Push(node.left);
            }
        }
    }
}

示例 2

现在我们来考虑一个稍微复杂一些的例子。假设有一个二叉搜索树，其结构如下：

        4
       / \
      2   6
     / \ / \
    1  3 5  7

在该二叉树中查找指定的值3，并输出其所在的节点。

下面是实现该功能的C#代码：

using System;
using System.Collections.Generic;

class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int val) {
        this.value = val;
    }
}

class Program {
    static void Main(string[] args) {
        Node root = new Node(4);
        Node node2 = new Node(2);
        Node node3 = new Node(6);
        Node node1 = new Node(1);
        Node node4 = new Node(3);
        Node node5 = new Node(5);
        Node node6 = new Node(7);

        root.left = node2;
        root.right = node3;
        node2.left = node1;
        node2.right = node4;
        node3.left = node5;
        node3.right = node6;

        int searchValue = 3;
        Node node = Search(root, searchValue);
        if (node != null) {
            Console.WriteLine($"The node with value {searchValue} is found.");
        }
        else {
            Console.WriteLine($"The node with value {searchValue} is not found.");
        }
    }

    static Node Search(Node root, int value) {
        Stack<Node> stack = new Stack<Node>();
        stack.Push(root);

        while (stack.Count != 0) {
            Node node = stack.Pop();

            if (node.value == value) {
                return node;
            }

            if (node.right != null && node.value < value) {
                stack.Push(node.right);
            }
            if (node.left != null && node.value > value) {
                stack.Push(node.left);
            }
        }

        return null;
    }
}

以上两个示例展示了非递归先序遍历的应用场景，同时也说明了该方法的高效性和灵活性。