Как можно переписать рекурсивный поиск количества вершин в дереве?

16
23 сентября 2021, 07:40

> Максимальное число вершин дерева в цепочке, начинающейся в корне дерева, заканчивающейся в одном из его листьев, и не содержащей никакую вершину дважды. При использовании рекурсии вылетает stackoverflowexception.

 public class Node
    {
        public Node left, right;
        public double key;
        public Node(int key)
        {
            this.key = key;
        }
    }
    public class BinaryTree
    {
        public Node root;
        public void Insert(int key)
        {
            Node x = root, y = null;
            double cmp = 0;
            while (x != null)
            {
                cmp = x.key - key;
                if (cmp == 0)
                {
                    return;
                }
                else
                {
                    y = x;
                    if (cmp < 0)
                    {
                        x = x.right;
                    }
                    else
                    {
                        x = x.left;
                    }
                }
            }
            Node newNode = new Node(key);
            if (y == null)
            {
                root = newNode;
            }
            else
            {
                if (cmp > 0)
                {
                    y.left = newNode;
                }
                else
                {
                    y.right = newNode;
                }
            }
        }
        public static int Height(Node node)// рекурсивный поиск вершин
        {
            if (node == null) return 0;
            return 1 + Math.Max(Height(node.left), Height(node.right));
        }
    }
Answer 1

Проверьте своё дерево на цикличность

public static int Height(Node node, Dictionary<Node, int> memory)// рекурсивный поиск вершин
{       
    if (node == null) return 0;
    if (memory.ContainsKey(node)){
        // У вас цикл. Для дерева такого быть не должно
        // Если вы хотите бросить исключение в этом случае, то
        // throw new Exception("Tree has a cycle!");
        // если всё таки хотите с циклом посчитать, то
        // return memory[node];
    }
    var height = 1 + Math.Max(Height(node.left, memory), Height(node.right, memory));
    memory[node] = height;
    return height;
}
READ ALSO
Для каждого слова заданного текста указать долю согласных. Определить слово, в котором доля согласных максимальна

Для каждого слова заданного текста указать долю согласных. Определить слово, в котором доля согласных максимальна

Для каждого слова заданного текста указать долю согласныхОпределить слово, в котором доля согласных максимальна

31
Изменение надписи по нажатию на кнопкe

Изменение надписи по нажатию на кнопкe

Нужно сделать так, чтобы щелчок по второй кнопке удалял надпись привет, и отображал новую другого цвета, например "Пока !"

38
C# graphics рисование на picturebox

C# graphics рисование на picturebox

Как правильно организовать аналог requestAnimationFrame (из js) в c# win forms? Как использовать больше ресурсов, чтобы ускорить отрисовку? Хотелось бы услышать...

55
Зачем в LINQ нужна лишняя запись?

Зачем в LINQ нужна лишняя запись?

Есть два одинаковых LINQ-запросаНепонятно, зачем в первом запросе прописывать q => q

38