Задача:
1) С файла считывать последовательность координат (x, y, z) пространственных точек, упорядоченных по дальности нахождения от точки начала координат (разработать отдельную функцию для вычисления расстояния и сохранять это значение в структуре данных);
2) Для обхода использовать нижний вариант справа налево;
3) Извлечь из дерева все узлы, координата z которых попадает в заданный диапазон zmin ..zmax(я решил взять от 7 до 14) и указать их количество;
4) Для полного стирания дерева использовать прямой (от корня) вариант обхода слева направо;
5) Напечатать всё дерево с помощью не рекурсивной функции.
Прошу помощи с 3 пунктом. Код я немного переписал и дополнил. Но все еще есть проблема:
"Кейс на случай если у узла 2 дочерних элемента не до конца написан, потому что я хз куда девать правый элемент, если левый имеет свои дочерние. В этой функции, которую я написал, на место удаленного узла, подтягивается левый дочерний элемент, и если у него нет дочернего элемента, то туда записывается правый узел, но в случае, если он будет с дочерними элементами, то произойдет утечка памяти".
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_LEN 8
#define STACK_INIT_SIZE 20
typedef struct Tree {
int z;
int viddal;
struct Tree* left, * right;
} TREE;
typedef struct Stack {
size_t size, limit;
TREE** data;
} STACK;
int Distance(FILE* ftxt, int* vid, int* z_cord);
int CreateTreeFromFile(void);
TREE* NewNode(FILE* f, int viddal, int z);
void AddNewNode(TREE* pnew);
void PrintTreeNIZ(TREE* proot);
void iterPostorder(TREE* root);
void OutputTreeStructure(const char* title);
void ShowTree(TREE* proot, int level);
void ShowLevels(void);
int TreeHeight(TREE* proot);
void EraseTree(TREE* proot);
void Search(TREE* tree);
int DeleteNode(TREE* pnew_adr);
TREE* root;
int main(){
system("chcp 1251");
if (CreateTreeFromFile() == 0)
return 0;
puts("\n Сформованное дерево: ");
PrintTreeNIZ(root);
OutputTreeStructure("сформованного дерева");
puts("\n Поиск и удаление объектов: ");
Search(root);
OutputTreeStructure("дерева после удаления объектов");
EraseTree(root);
root = NULL;
puts("\n Дерево стерто из ДП\n\n");
return 0;
}
//---------------------------------------------------------
int Distance(FILE* ftxt, int *vid, int* z_cord) {
TREE* pel;
if (feof(ftxt)) {;
return NULL;
}
else {
int x, y, z;
fscanf(ftxt, "%d%d%d", &x, &y, &z);
*z_cord = z;
*vid = sqrt(x * x + y * y + z * z);
}
}
int CreateTreeFromFile()
{
const char* fname = "Cords_1.txt";
FILE* fvoc = fopen(fname, "r");
if (fvoc == NULL) {
printf("\n\t\tНе удалось открыть файл %s...\n", fname);
return 0;
}
TREE* node;
int viddal, z;
Distance(fvoc, &viddal, &z);
while ((node = NewNode(fvoc, viddal, z)) != NULL) {
AddNewNode(node);
Distance(fvoc, &viddal, &z);
}
fclose(fvoc);
return 1;
}
TREE* NewNode(FILE* f, int viddal, int z)
{
TREE* pel;
pel = (TREE*)malloc(sizeof(TREE));
if (feof(f)) {
return NULL;
}
pel->viddal = viddal;
pel->z = z;
pel->left = pel->right = NULL;
return pel;
}
void AddNewNode(TREE* pnew) {
if (root == NULL) {
root = pnew;
return;
}
TREE* prnt = root;
do {
if (pnew->viddal == prnt->viddal) {
free(pnew);
return;
}
if (pnew->viddal < prnt->viddal) {
if (prnt->left == NULL) {
prnt->left = pnew;
return;
}
else
prnt = prnt->left;
}
else {
if (prnt->right == NULL) {
prnt->right = pnew;
return;
}
else
prnt = prnt->right;
}
} while (1);
}
//---------------------------------------------------------
void PrintTreeNIZ(TREE* proot)
{
if (proot == NULL)
return;
printf("\n Right Tree");
iterPostorder(proot->right);
printf("\n\n Left Tree");
iterPostorder(proot->left);
printf("\n\n Korin - %d", proot->viddal);
}
void OutputTreeStructure(const char* title)
{
printf("\n\n\n Структура %s:\n\n", title);
ShowLevels();
ShowTree(root, 0);
puts("\n");
}
#define TAB 7
void ShowTree(TREE* proot, int level)
{
if (proot == NULL) return;
ShowTree(proot->right, level + 1);
printf("\n%*c%d", level * TAB + 10, ' ', proot->viddal);
ShowTree(proot->left, level + 1);
}
void ShowLevels(void)
{
int lev;
printf(" Уровень: ");
for (lev = 1; lev <= TreeHeight(root); lev++)
printf(" %-*d", 6, lev);
printf("\n\n");
}
int TreeHeight(TREE* proot)
{
int lh, rh;
if (proot == NULL) return 0;
lh = TreeHeight(proot->left);
rh = TreeHeight(proot->right);
return lh > rh ? lh + 1 : rh + 1;
}
//---------------------------------------------------------
void EraseTree(TREE* proot)
{
if (proot == NULL)
return;
EraseTree(proot->left);
EraseTree(proot->right);
free(proot);
}
//---------------------------------------------------------
STACK* createStack() {
Stack* tmp = (Stack*)malloc(sizeof(Stack));
tmp->limit = STACK_INIT_SIZE;
tmp->size = 0;
tmp->data = (TREE**)malloc(tmp->limit * sizeof(TREE*));
return tmp;
}
void freeStack(Stack** s) {
free((*s)->data);
free(*s);
*s = NULL;
}
void push(Stack* s, TREE* item) {
if (s->size >= s->limit) {
s->limit *= 2;
s->data = (TREE**)realloc(s->data, s->limit * sizeof(TREE*));
}
s->data[s->size++] = item;
}
TREE* pop(Stack* s) {
if (s->size == 0) {
exit(7);
}
s->size--;
return s->data[s->size];
}
TREE* peek(Stack* s) {
return s->data[s->size - 1];
}
void iterPostorder(TREE* root) {
Stack* ps = createStack();
TREE* lnp = NULL;
TREE* peekn = NULL;
while (!ps->size == 0 || root != NULL) {
if (root) {
push(ps, root);
root = root->left;
}
else {
peekn = peek(ps);
if (peekn->right && lnp != peekn->right) {
root = peekn->right;
}
else {
pop(ps);
printf("\n\t Visited -> %d", peekn->viddal);
lnp = peekn;
}
}
}
freeStack(&ps);
}
//---------------------------------------------------------
void Search(TREE* tree) {
if (tree == NULL) return;
Search(tree->left);
Search(tree->right);
if (tree->z >= 7 && tree->z <= 14) {
DeleteNode(tree);
printf("\n Deleted element: %d", tree->viddal);
}
}
#define NoSubTree 0
#define LeftSubTree -1
#define RightSubTree 1
#define TwoSubTrees 2
int DeleteNode(TREE* pnew_adr)
{
int subtr;
if (pnew_adr == NULL) return 0;
DeleteNode(pnew_adr->left);
DeleteNode(pnew_adr->right);
if (pnew_adr->left == NULL && pnew_adr->right == NULL)
subtr = NoSubTree;
else if (pnew_adr->left == NULL)
subtr = RightSubTree;
else if (pnew_adr->right == NULL)
subtr = LeftSubTree;
else
subtr = TwoSubTrees;
switch (subtr) {
case NoSubTree:
pnew_adr = NULL; break;
case LeftSubTree:
pnew_adr = pnew_adr->left; break;
case RightSubTree:
pnew_adr = pnew_adr->right; break;
case TwoSubTrees:
*prnt_adr = proot->left;
if ((*prnt_adr)->left == NULL)
(*prnt_adr)->left = proot->right;
if ((*prnt_adr)->right == NULL)
(*prnt_adr)->right = proot->right;
}
free(pnew_adr);
return 1;
}
//---------------------------------------------------------
Координаты из тестового файла
13 14 15
13 14 15
16 14 18
16 14 18
10 11 12
10 11 12
4 5 6
4 5 6
16 17 18
14 13 21
17 13 14
12 12 14
13 13 14
11 13 12
10 12 4
4 5 2
5 6 7
17 14 15
22 13 21
