Копирование и объединение бинарных деревьев
Всем здравствуйте, в университете на лабораторной работе дали задачу объединить 2 бинарных дерева. Алгоритм их объединения выполняется следующим образом: Сначала создаем оба дерева, затем делаем копию первого и вставляем в него узлы второго дерева. Я смог написать копирование и объединение, но они работают некорректно. В прикрепленном скриншоте видно что копия выводится с артефактами, а объединения не происходит. Просьба знающих людей помочь с решением проблемы. Всем добра и легкой компиляции)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
#include using namespace std; struct Node //Звено дерева { int x; //То, что записываем в дерево Node *l,*r; //Это указатели на новые звенья }; void show(Node *&Tree) //Функция обхода { if (Tree != NULL) //Пока не встретится пустое звено { show(Tree->l); //Рекурсивная функция для вывода левого поддерева cout Tree->x '\t'; //Отображаем корень дерева show(Tree->r); //Рекурсивная функци для вывода правого поддерева } } /*Добавили очистку памяти*/ void del(Node *&Tree){ if (Tree != NULL) //Пока не встретится пустое звено { del(Tree->l); //Рекурсивная функция прохода по левому поддереву del(Tree->r); //Рекурсивная функци для прохода по правому поддереву delete Tree; //Убиваем конечный элемент дерева Tree = NULL; //Может и не обязательно, но плохого не будет } } void add_node(int x,Node *&MyTree) //Фукция добавления звена в дерево { if (NULL == MyTree) //То, о чем я в самом начале писал. Если дерева нет, то ложим семечко { MyTree = new Node; //Выделяем память под звено дерева MyTree->x = x; //Записываем данные в звено MyTree->l = MyTree->r = NULL; //Подзвенья инициализируем пустотой во избежание ошибок } if (x MyTree->x) //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево { if (MyTree->l != NULL) add_node(x, MyTree->l); //При помощи рекурсии заталкиваем элемент на свободный участок else //Если элемент получил свой участок, то { MyTree->l = new Node; //Выделяем память левому подзвену. Именно подзвену, а не просто звену MyTree->l->l = MyTree->l->r = NULL; //У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой MyTree->l->x = x; //Записываем в левое подзвено записываемый элемент } } if (x > MyTree->x) //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо { if (MyTree->r != NULL) add_node(x, MyTree->r); //При помощи рекурсии заталкиваем элемент на свободный участок else //Если элемент получил свой участок, то { MyTree->r = new Node; //Выделяем память правому подзвену. Именно подзвену, а не просто звену MyTree->r->l = MyTree->r->r = NULL; //У правого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой MyTree->r->x = x; //Записываем в правое подзвено записываемый элемент } } } Node *unite(Node *copy, Node *root2)// Объединение деревьев { if (copy==0) { printf("первое ноль \n"); show(root2);//Если первое дерево пустое, то выводим второе return root2; exit(1);//Выход } if (root2==0) { printf("второе ноль\n"); show(copy);//Если второе дерево пустое, то выводим первое return copy; exit(1);//Выход } if (copy!=NULL)//Если первое не пустое, то { root2=unite(copy->r, root2);//Объединяем со вторым copy->r=root2; show(copy); return copy; } else { copy=unite(copy, root2->l);//Иначе объединяем с первым root2->l=copy; show(root2); return root2; } } Node *CopyTree(Node *Tree) { if (Tree==0) return 0 ; Node *copy = new Node; copy->x=Tree->x; copy->l=CopyTree(Tree->l); copy->r=CopyTree(Tree->r); show(copy); return copy; } int main() { /*Node *Tree = NULL; //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой for (int i=5; i>0; i--) add_node(i,Tree); //Это я забивал 5-4-3-2-1, а вывод сами увидите show(Tree); //Вывод на экран дерева. или просто обход дерева cout del(Tree); //Чистка памяти! Распилили дерево for (int i=20; i>5; i--) add_node(i,Tree); //На месте спиленного дерева можно растить новое show(Tree); //Смотрим, что выросло del(Tree); //Когда дерево уже не нужно, зачищаем память */ FILE *input1; //Бинарный файл в котором задано первое дерево FILE *input2; //Бинарный файл в котором задано второе дерево Node *root1=0 ;//Первое дерево Node *root2=0;//Второе дерево Node *copy=0; int n=4,m=3; int s[5]; int a[4]; input1=fopen("input1.bin", "r");//открытие и считывание информации с бинарного файла for (int i=0; in; i++) { fscanf(input1, "%d ", &s[i]);//получение информации о звеньях первого дерева } fclose(input1); printf("Дерево номер 1 \n"); for (int i = 0; s[i]; i++) { add_node(s[i], root1);//Заполняем первое дерево значениями } show(root1);//Вывод первого дерева printf(" \n "); printf(" копия \n "); CopyTree(root1); // del(root1); show(copy); // input2=fopen("input2.bin", "r");//открытие и считывание информации с бинарного файла for (int j=0; jm; j++) { fscanf(input2, "%d ", &a[j]);//получение информации о звеньях второго дерева } fclose(input2); printf("\n"); printf("Дерево номер 2 \n"); for (int j = 0;jm; j++) { add_node(a[j], root2);//Заполняем второе дерево значениями } show(root2); printf(" \n "); printf(" копия \n "); // CopyTree(root2); del(root2); printf(" \n "); unite(copy, root2);//Объединяем деревья return 0; } Источник