Создание бинарного дерева из массива - 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); }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д