Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Высота бинарного дерева  (Прочитано 14031 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Лена91
Интересующийся

ru
Offline Offline
Пол: Женский

« : 12-11-2019 14:08 » 

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

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

ru
Offline Offline
Пол: Женский

« Ответ #1 : 14-11-2019 13:56 » 

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

Код: (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;
            }
        }
    }
}
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #2 : 14-11-2019 21:45 » 

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

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Лена91
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #3 : 18-11-2019 12:59 » 

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

de
Offline Offline
Пол: Мужской

« Ответ #4 : 18-11-2019 21:23 » 

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

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

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

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Лена91
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #5 : 19-11-2019 06:37 » 

Нет, из инета. Классы из одного места, сам подсчет (функция findHeight(BinaryTreeNode<int> node)) из другого. Соединила видимо не правильно, возможно код перегружен классами.
« Последнее редактирование: 19-11-2019 06:42 от Лена91 » Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #6 : 20-11-2019 23:05 » new

Ок, насчёт кода - понятно.
Классы самого дерева не очень интересны для задания. Я думаю раз из инета, то рабочие.
Алгоритм поиска высоты в методе 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#-компилятора), чисто аналитически, ЧЕМУ?
« Последнее редактирование: 20-11-2019 23:09 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Лена91
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #7 : 25-11-2019 13:34 » 

Высота равна 4.
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #8 : 25-11-2019 17:09 » 

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

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

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

зы Да, и ещё один "намёк" Ага. Чему равна высота дерева, у которого есть только корень?
« Последнее редактирование: 25-11-2019 17:11 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Лена91
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #9 : 25-11-2019 17:35 » 

Высота дерева 3.
Высота дерева, у которого есть только корень 1.
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #10 : 25-11-2019 23:38 » 

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

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

Цитата
Высота дерева, у которого есть только корень 1.
Это следует из какой формулы?

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

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

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

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Лена91
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #11 : 26-11-2019 12:36 » 

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

de
Offline Offline
Пол: Мужской

« Ответ #12 : 26-11-2019 22:29 » 

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

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

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

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

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

Ну как-то так.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Лена91
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #13 : 27-11-2019 14:00 » 

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

de
Offline Offline
Пол: Мужской

« Ответ #14 : 27-11-2019 14:56 » 

Нууу тут всё просто. Представьте, что каждый узел - это есть дерево (отличие корня - у него нет предков). Высота "одного" дерева равна 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
            }
        }

Вот собственно и всё. Вопросы?
« Последнее редактирование: 27-11-2019 14:59 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Лена91
Интересующийся

ru
Offline Offline
Пол: Женский

« Ответ #15 : 28-11-2019 13:00 » 

Спасибо.
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines