C # Binary Tree's - Inorder / Preorder и PostOrder (Справка по рекурсии)

Question

Мне нужна помощь с рекурсией.Я пытаюсь сделать бинарное дерево в C #, мне интересно, можно ли продемонстрировать все обходы Inorder / PostOrder и PreOrder с помощью рекурсивной функции.

Я завершил его для PreOrder, а затем попытался InOrder, однако вызвал исключение StackOverflow, мое понимание двоичного дерева в лучшем случае ненадежно, поэтому любая помощь с этим будет очень признательна, даже если это кажется глупым вопросом.

Следующий код - это то, что я использую для PreOrder Traversal;

     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("");
    }

Заранее спасибо, это определенно то, что у меня возникают проблемы, и ядаже не уверен, возможно ли это.

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);
    }
}

Разница в предзаказе в том, что вы сначала пересекаетелевое поддерево, затем обработать текущий узел и, наконец, пройти по правому поддереву.

Answer 2

Вики-страница для обхода дерева сообщает:

Двоичное дерево

Чтобы пройти непустое двоичное дерево в предзаказ , рекурсивно выполните следующие операции на каждом узле, начиная с корневого узла:

1. Посетите корень.
2. Пройдите по левому поддереву.
3. Пройдите правое поддерево.

Чтобы обойти непустое двоичное дерево в порядке (симметрично), выполнить следующие операции рекурсивно на каждом узле:

1. Обойти левуюподдерево.
2. Посетите корень.
3. Пройдите по правому поддереву.

Чтобы пройти непустое двоичное дерево в postorder , выполните следующие операции рекурсивно на каждом узле:

1. Обойдите левое поддерево.
2. Пройдите по правому поддереву.
3. Посетите корень.

[Кстати, это был первый хит поиска.]

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
                }
        }