C#二叉树-中序/前序和后序(递归帮助)

Question

我需要一些关于递归的帮助。我正在尝试在C#中创建一个二叉树，想知道是否可能使用递归函数演示所有的中序/后序和前序遍历。

我已经完成了前序遍历，并尝试进行中序遍历，但导致堆栈溢出异常，我的二叉树理解力最多只能算得上薄弱，所以任何帮助都将不胜感激，即使它看起来像是一个愚蠢的问题。

以下是我用于前序遍历的代码：

     public void recursivePreorder(BinaryTreeNode root)
    {
        Console.Write(root.Data.ToString());
        if (root.Left != null)
        {
            recursivePreorder(root.Left);
        }
        if (root.Right != null)
        {
            recursivePreorder(root.Right);
            }
    }

     public void preorderTraversal()
    {
        if (Root != null)
        {
            recursivePreorder(Root);
        }
        else
        {
            Console.WriteLine("There is no tree to process");
        }

    static void Main(string[] args)
    {

        // Build the tree
        Test.Add(5);
        Test.Add(2);
        Test.Add(1);
        Test.Add(3);
        Test.Add(3); // Duplicates are OK
        Test.Add(4);
        Test.Add(6);
        Test.Add(10);
        Test.Add(7);
        Test.Add(8);
        Test.Add(9);
        // Test if we can find values in the tree

        for (int Lp = 1; Lp <= 10; Lp++)
            Console.WriteLine("Find Student ID ({0}) = {1}", Lp, Test.Find(Lp));

        // Test if we can find a non-existing value
        Console.WriteLine("Find Student ID (999) = {0}", Test.Find(999));

        // Iterate over all members in the tree -- values are returned in sorted order
        foreach (int value in Test)
        {
            Console.WriteLine("Value: {0}", value);
        }

        Console.WriteLine("Preorder Traversal");
        Console.WriteLine("");
        Test.preorderTraversal();
        Console.WriteLine("");
    }

非常感谢您的帮助，这绝对是我难以理解的事情之一，甚至我不确定它是否可能实现。

- Steffan Caine

Answer 1

Inorder（中序遍历）与您已经拥有的非常相似，只需在处理当前节点的位置上稍微调整一下代码：

public void recursiveInorder(BinaryTreeNode root)
{
    if (root.Left != null)
    {
        recursiveInorder(root.Left);
    }
    Console.Write(root.Data.ToString());
    if (root.Right != null)
    {
        recursiveInorder(root.Right);
    }
}

与前序遍历的区别在于，您首先遍历左子树，然后处理当前节点，最后遍历右子树。

- BrokenGlass

---

非常感谢您的快速回复，有没有可能还能向我展示一下后序遍历呢？另外，您可以帮忙解释一下它的工作原理吗？因为虽然您的答案非常清晰，但我似乎仍然无法理解与这个主题相关的任何内容，无论是二叉树如何工作还是递归如何工作。 - Steffan Caine

@SteffanCaine：想一想：post顺序只是将当前节点的处理移动到最后 - 那么你会在哪里放置你的Console.Write语句呢？还要查看下面@Mitch链接的维基百科文章。 - BrokenGlass

哈，我知道它会很简单，通过下面的文章链接和你的回复，它确实非常明显。非常感谢你，伙计，非常感激；) - Steffan Caine

我们可以在方法开始处添加验证以检查根节点是否为空。 - Pritam Karmakar

Answer 2

树的遍历 的维基页面说明：

二叉树

为了按 先序 遍历一个非空二叉树，在每个节点上递归执行以下操作，从根节点开始：

1. 访问根节点。
2. 遍历左子树。
3. 遍历右子树。

为了按 中序（对称）遍历一个非空二叉树，在每个节点上递归执行以下操作：

1. 遍历左子树。
2. 访问根节点。
3. 遍历右子树。

为了按 后序 遍历一个非空二叉树，在每个节点上递归执行以下操作：

1. 遍历左子树。
2. 遍历右子树。
3. 访问根节点。

[顺便说一下，这是第一个搜索结果。]

- Mitch Wheat

---

我已经有一份试图解释这个问题的文档，但是我没有理解，所以想要一个更人性化的答案。不过你提供的链接非常有帮助，非常感谢 :) - Steffan Caine

Answer 3

  class BstNode
    {
        public int data;
        public BstNode(int data)
        {
            this.data = data;
        }
        public BstNode left;
        public BstNode right;
    }
class Program
            {
                public static void PreOrderTraversal(BstNode root)
                {
                    if (root == null) return;

                    Console.WriteLine("PreOrderTraversal at node {0}", root.data); // process the root
                    PreOrderTraversal(root.left);// process the left
                    PreOrderTraversal(root.right);// process the right
                }

                public static void InOrderTraversal(BstNode root)
                {
                    if (root == null) return;

                    InOrderTraversal(root.left);// process the left
                    Console.WriteLine("InOrderTraversal at node {0}", root.data); // process the root
                    InOrderTraversal(root.right);// process the right
                }

                public static void PostOrderTraversal(BstNode root)
                {
                    if (root == null) return;

                    PostOrderTraversal(root.left);// process the left            
                    PostOrderTraversal(root.right);// process the right
                    Console.WriteLine("PostOrderTraversal at node {0}", root.data); // process the root
                }
        }

- user1997925