Обход InOrder идет только к первому левому узлу, а затем к ошибке?

Я пытаюсь выполнить простой неупорядоченный обход BST, и BST строится правильно, но когда я пытаюсь распечатать BST в порядке, он переходит к первому левому узлу, а затем не переходит ни к каким другим узлам после этого и создает переполнение.

Я пытался сделать разные обходы в порядке с помощью getLeft и getRight, но он все еще делает то же самое.

class Program
    {
        static void Main(string[] args)
        {
            Tree tree = new Tree();

            List<int> rands = new List<int>();

            Random random = new Random();

            int between = random.Next(20, 30);

            for (int i = 0; i < between; i++)
            {
                rands.Add(random.Next(100));
            }

            for (int x = 0; x < rands.Count; x++)
            {
                tree.constructTree(rands[x]);
            }

            tree.Inorder(tree.returnRoot());

        }
    class Node
    {
        private int number;
        public Node left;
        public Node right;

        public Node()
        {
        }

        public Node getLeft()
        {
            return this.left;
        }

        public Node getRight()
        {
            return this.right;
        }

        public int GetSetNumber
        {
            get
            {
                return this.number;
            }
            set
            {
                this.number = value;
            }
        }

        public Node GetSetLeft
        {
            get
            {
                return this.left;
            }
            set
            {
                this.left = value;
            }
        }

        public Node GetSetRight
        {
            get
            {
                return this.right;
            }
            set
            {
                this.right = value;
            }
        }
    }



    class Tree
    {
        public Node root;

        public Node returnRoot()
        {
            return this.root;
        }

        public void constructTree(int num)
        {
            Node t = new Node();
            t.GetSetNumber = num;

            if (root == null)
            {
                root = t;
            }
            else
            {
                Node cur = root;
                Node top;

                while (true)
                {
                    top = cur;
                    if (num < top.GetSetNumber)
                    {
                        cur = cur.GetSetLeft;
                        if (cur == null)
                        {
                            top.GetSetLeft = t;
                            return;
                        }
                    }
                    else
                    {
                        cur = cur.GetSetRight;
                        if (cur == null)
                        {
                            top.GetSetRight = t;
                            return;
                        }
                    }
                }

            }
        }

        public void Inorder(Node Root)
        {
            if (root == null)
            {
                return;
            }
            Inorder(root.left);
            Console.WriteLine(root.GetSetNumber + " ");
            Inorder(root.right);
        }

    }

c# binary-search-tree inorder
person TCripe4    schedule 02.05.2019    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы ссылаетесь на root в Inorder, а не на Root. root (нижний регистр r) — это переменная класса, содержащая корень всего дерева, а не параметр Node, который вы передали. Ваш код зацикливается бесконечно, потому что вы всегда вызываете Inorder на одном и том же узле.

Если вы будете использовать заглавные буквы в своих ссылках на root в Inorder (или использовать другое имя переменной в методе, чтобы избежать путаницы, например current), вы сможете добиться некоторого прогресса.

    public void Inorder(Node Root)
    {
        if (Root == null)
        {
            return;
        }
        Inorder(Root.left);
        Console.WriteLine(Root.GetSetNumber + " ");
        Inorder(Root.right);
    }
person nlawalker    schedule 02.05.2019