Высота бинарного дерева

[Лена91]

Доброе время суток!

Посчитать высоту бинарного дерева не сложно, много информации. Но запуталась как программно реализовать классы Tree и Node (кажется они необходимы), перед подсчетом. Не скажите, где можно найти исходник...или может сбросите? Спасибо.

[Лена91]

Сделала так, но не верно считает. Не подскажите где ошибка?

Код: (C#)

//Узел
    public class Node<T>
    {
        // Private member-variables
        private T data;
        private NodeList<T> neighbors = null;

        public Node() {}
        public Node(T data) : this(data, null) {}

        public Node(T data, NodeList<T> neighbors)
        {
            this.data = data;
            this.neighbors = neighbors;
        }

        public T Value
        {
            get
            {
                return data;
            }
            set
            {
                data = value;
            }
        }

        protected NodeList<T> Neighbors
        {
            get
            {
                return neighbors;
            }
            set
            {
                neighbors = value;
            }
        }
    }


    //Список узлов
    public class NodeList<T> : Collection<Node<T>>
    {
        public NodeList() : base() { }

        public NodeList(int initialSize)
        {
            // Add the specified number of items
            for (int i = 0; i < initialSize; i++)
            {
                base.Items.Add(default(Node<T>));
            }
        }

        public Node<T> FindByValue(T value)
        {
            // search the list for the value
            foreach (Node<T> node in Items)
            {
                if (node.Value.Equals(value))
                {
                    return node;
                }
            }

            // if we reached here, we didn't find a matching node
            return null;
        }
    }


    //Узел бинарного дерева
    public class BinaryTreeNode<T> : Node<T>
    {
        public BinaryTreeNode() : base() { }
        public BinaryTreeNode(T data) : base(data, null) { }

        public BinaryTreeNode(T data, BinaryTreeNode<T> left, BinaryTreeNode<T> right)
        {
            base.Value = data;

            NodeList<T> children = new NodeList<T>(2);
            children[0] = left;
            children[1] = right;

            base.Neighbors = children;
        }

        public BinaryTreeNode<T> Left
        {
            get
            {
                if (base.Neighbors == null)
                {
                    return null;
                }
                else
                {
                    return (BinaryTreeNode<T>) base.Neighbors[0];
                }
            }
            set
            {
                if (base.Neighbors == null)
                {
                    base.Neighbors = new NodeList<T>(2);
                }

                base.Neighbors[0] = value;
            }
        }

        public BinaryTreeNode<T> Right
        {
            get
            {
                if (base.Neighbors == null)
                {
                    return null;
                }
                else
                {
                    return (BinaryTreeNode<T>) base.Neighbors[1];
                }
            }
            set
            {
                if (base.Neighbors == null)
                {
                    base.Neighbors = new NodeList<T>(2);
                }

                base.Neighbors[1] = value;
            }
        }
    }


    //Бинарное дерево
    public class BinaryTree<T>
    {
        private BinaryTreeNode<T> root;

        public BinaryTree()
        {
            root = null;
        }

        public virtual void Clear()
        {
            root = null;
        }

        public BinaryTreeNode<T> Root
        {
            get
            {
                return root;
            }
            set
            {
                root = value;
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            BinaryTree<int> btree = new BinaryTree<int>();

            btree.Root = new BinaryTreeNode<int>(1);

            btree.Root.Left = new BinaryTreeNode<int>(2);
            btree.Root.Right = new BinaryTreeNode<int>(3);

            btree.Root.Left.Left = new BinaryTreeNode<int>(4);
            btree.Root.Right.Right = new BinaryTreeNode<int>(7);

            btree.Root.Left.Right = new BinaryTreeNode<int>(5);
            btree.Root.Right.Left = new BinaryTreeNode<int>(6);

            btree.Root.Right.Right.Right = new BinaryTreeNode<int>(8);

            int res = findHeight(btree.Root);

            Console.Write(res);
            Console.ReadKey();
        }


        static int findHeight(BinaryTreeNode<int> node)
        {
            if (node == null)
            {
                return -1;
            }

            int lefth = findHeight(node.Left);
            int righth = findHeight(node.Right);

            if (lefth > righth)
            {
                return lefth + 1;
            }
            else
            {
                return righth + 1;
            }
        }
    }
}

[Джон]

Что значит "не верно"?

[Лена91]

Выдает ответ: 3. А это ведь не высота дерева, она должна быть: 19. Я что-то не поняла?

[Джон]

Ок. Я думаю, что таки последнее.

Обращаемся к теории. Что такое высота бинарного дерева (дальше просто "дерева")? Чему равна высота дерева, у которого есть только корень?

зы приведённый выше код Ваш?

[Лена91]

Нет, из инета. Классы из одного места, сам подсчет (функция findHeight(BinaryTreeNode<int> node)) из другого. Соединила видимо не правильно, возможно код перегружен классами.

[Джон]

Ок, насчёт кода - понятно.
Классы самого дерева не очень интересны для задания. Я думаю раз из инета, то рабочие.
Алгоритм поиска высоты в методе findHeight, в принципе, стандарт.

Ещё раз вопрос: что такое высота бинарного дерева?

Исходя из (я несколько изменил порядок инициализации дерева, для лучшей наглядности)

Код: (C#)

            btree.Root = new BinaryTreeNode<int>(1);

            btree.Root.Left = new BinaryTreeNode<int>(2);
            btree.Root.Right = new BinaryTreeNode<int>(3);

            btree.Root.Left.Left = new BinaryTreeNode<int>(4);
            btree.Root.Left.Right = new BinaryTreeNode<int>(5);

            btree.Root.Right.Left = new BinaryTreeNode<int>(6);
            btree.Root.Right.Right = new BinaryTreeNode<int>(7);

            btree.Root.Right.Right.Right = new BinaryTreeNode<int>(8);

в Вашем случае дерево выглядит так:

                    1
         2                    3
    4       5           6       7
                                        8

Так чему равна его высота (без всякого кода и C#-компилятора), чисто аналитически, ЧЕМУ?

[Лена91]

Высота равна 4.

[Джон]

Я вобще-то имел ввиду определение, т.е. что называется высотой дерева? Ну, или как Вы это понимаете/представляете.

Ок, попробуем по-другому.

Вы можете показать (рассказать), как у Вас получается:
 1. 4
 2. 19 (в силу)

Выдает ответ: 3. А это ведь не высота дерева, она должна быть: 19.

зы Да, и ещё один "намёк" . Чему равна высота дерева, у которого есть только корень?

[Лена91]

Высота дерева 3.
Высота дерева, у которого есть только корень 1.

[Джон]

Высота дерева 3.

Это определение высоты дерева? Т.е. ЛЮБОЕ бинарное дерево имеет высоту 3? Я Вас правильно понял?

Высота дерева, у которого есть только корень 1.

Это следует из какой формулы?

Вы, за время всего "эксперимента", озвучили 3 результата:
 * 19
 *  4
 * и 3, как "неправильный" результат работы программы

3 - понятно, программа выдала такой результат.

Но как Вы получили 19? А как потом 4? Вы как-то считали? Угадывали? Задавали вопросы на других форумах?
Как?

[Лена91]

19 получено из вершин (1+3+7+8 = 19), глупость.
4 получено сложением max кол-ва вершин в ветке (тех же), тоже ошибка.
3 это кол-во вершин в той же ветке, только не считая конечную вершину 8, т.к. она является "листом".

[Джон]

Извиняюсь за может бестактный вопрос: вы где-то учитесь/работаете/источник задания/цель решения?

Почему? Потому, что на лицо явная нехватка теории (матчасти). От этого зависит, стоит ли углубляться в объяснения, или же просто сдать работающий правильно код и забыть.

Хоть теория не так уж и сложна - что такое бинарное дерево? - да просто у каждого узла не более двух потомков. А точнее ВСЕГДА два потомка, только один из них или оба могут быть пустыми.

На этом и построен рекурсивыный алгоритм поиска высоты.

Но вот стоит ли его разбирать? Это зависит от цели. Другими словами: а оно Вам надо?

Ну как-то так.

[Лена91]

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

[Джон]

Нууу тут всё просто. Представьте, что каждый узел - это есть дерево (отличие корня - у него нет предков). Высота "одного" дерева равна 1. Соответственно, высота некоего узла будет равана высоте предка этого узла + 1. Ну, или другими словами, сумме высот деревьев-предков этого узла.

Это даёт нам возможность создания рекурсии, когда в ф-ю передаётся каждый раз дерево, просто начиная с узлов корня, это будут "поддеревья".

Поскольку дерево бинарное (помним! максимум 2 узла), то для конкретного узла "спрашиваем" высоту левого и правого потомка, и выбираем из них максимальную. "Листья", или ещё их назвают внешние узлы, являются
условием прекращения рекурсии.

Итак:

Код: (C#)

        static int findHeight(BinaryTreeNode<int> node)
        {
            if (node == null) // (под-)узел равен нулю - достигли "низа"
            {
                return -1; // прекращаем рекурсию, тут небольшой трюк, см. ниже
            }

            // иначе, пытаемся получить высоты правого и левого поддеревьев
            int lefth = findHeight(node.Left); // запускаем рекурсию для левого поддерева
            int righth = findHeight(node.Right);  // запускаем рекурсию для правого поддерева

            // возвращаем бОльшую из двух высот + 1 -> собственную высоту
            if (lefth > righth)
            {
                return lefth + 1;
            }
            else
            {
                return righth + 1; // здесь автор кода скрыл небольшой трюк, который явно не видно
                // для внешнего узла ("листика", потомков нет => node.Left и node.Right = null) оба значения lefth и righth = -1
                // следовательно if-проверка будет ложной, и выполнится блок else{}
                // но -1 + 1 = 0, поэтому ф-я вернёт высоту = 0
            }
        }

Вот собственно и всё. Вопросы?

[Лена91]

Спасибо.