Создание бинарного дерева из массива - C#

Узнай цену своей работы

Формулировка задачи:

Всем привет. Есть массив чисел, например 1 4 6 10 0 0 0 7 0 8 0 0 2 5 0 0 3 9 0 0 0, в котором записаны все узлы бинарного дерева если обходить его в прямом порядке. 0 означает отсутствие потомка. Никак не могу разобраться как из этого массива сделать бинарное дерево. Деревом у меня является массив объектов node с полями int value, node left, node right, node parent Подскажите пожалуйста как это реализовать.

Решение задачи: «Создание бинарного дерева из массива»

textual
Листинг программы
            int[] arr = new int[] { 1, 4, 6, 10, 0, 0, 0, 7, 0, 8, 0, 0, 2, 5, 0, 0, 3, 9, 0, 0, 0 };
 
            Node[] tree = new Node[arr.Length];
 
            Node parent = null;
 
            for (int i = 0; i < arr.Length; i++)
            {
                tree[i] = new Node();
                // сслыка для удобства, что бы не писать вечно tree[i]
                var node = tree[i];
                // присваиваем значение из массива
                node.value = arr[i];
                // присваем раннее запомненого родителя
                node.parent = parent;
                // запоминаем  текущий элемент как родителя
                parent = node.value == 0 ? node.parent : node;
 
                // Если есть родитель
                if (node.parent != null)
                {
                    bool flag = true;
 
                    while (flag)
                    {
                        // Сначала левый потомок, потом правый
                        // Если есть потомки, поднимаемся по дереву вверх
                        if (node.parent.left == null)
                        {
                            node.parent.left = node;
                            flag = false;
                        }
                        else if (node.parent.right == null)
                        {
                            node.parent.right = node;
                            flag = false;
                        }
                        else
                        {
                            node.parent = node.parent.parent;
                        }
                    }
                }
            }
 
            foreach (var item in tree)
            {
                Console.WriteLine("{0} left{1}, right {2} parent {3}", item.value, item.left, item.right, item.parent);
            }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 3.909 из 5
Похожие ответы