Добрейший вечерочек форумчанам.
На повестке дня вот такая задачка:
1) С файла считывать последовательность координат (x, y, z) пространственных точек, упорядоченных по дальности нахождения от точки начала координат (разработать отдельную функцию для вычисления расстояния и сохранять это значение в структуре данных);
2) Для обхода использовать нижний вариант справа налево;
3) Извлечь из дерева все узлы, координата z которых попадает в заданный диапазон zmin ..zmax(я решил взять от 7 до 14) и указать их количество;
4) Для полного стирания дерева использовать прямой (от корня) вариант обхода слева направо;
5) Напечатать всё дерево с помощью не рекурсивной функции.
Прошу помощи с 3 пунктом. Никак не могу реализовать алгоритм:
Код:
1. делаю условие, если элемент, который передаётся буде NULL, то стоп функцию ретёрном
2. делаем рекурсию функции на правые и левые элементы( то есть вызываем эту же функцию сначала для левого, а потом для правого поддеревьев)
3. делаем условие, если координата z попадает в диапазон, то удаляем узел.
Заранее спасибо всем кто откликнется
КОД на СИ:
Код:
#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 DeleteSomeNodes(void);
int DeleteNode(TREE* pnew_adr);
TREE* root;
int main(){
system("chcp 1251");
if (CreateTreeFromFile() == 0)
return 0;
puts("\n Сформированное дерево: ");
PrintTreeNIZ(root);
OutputTreeStructure("сформированного дерева");
OutputTreeStructure("нового дерева");
EraseTree(root);
root = NULL;
puts("\n Дерево стерто из ДП\n\n");
return 0;
}
int Distance(FILE* ftxt, int *vid, int* z_cord) {
TREE* pel = (TREE*)malloc(sizeof(TREE));
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 DeleteSomeNodes(void)
{
printf("\n\t Deleting needing nods:\n");
TREE* pfind = root;
do {
if (pfind->z >= 7 && pfind->z <= 14) {
DeleteNode(root);
printf(" Number %d was deleted from tree\n", root);
}
} while (1);
puts("\n\n");
}
#define NoSubTree 0
#define LeftSubTree -1
#define RightSubTree 1
#define TwoSubTrees 2
int DeleteNode(TREE* pnew_adr)
{
TREE* proot = root;
int subtr;
if (proot == NULL) return 0;
if (pnew_adr->viddal < proot->viddal)
return DeleteNode(proot->left);
if (pnew_adr->viddal > proot->viddal)
return DeleteNode(proot->right);
if (proot->left == NULL && proot->right == NULL)
subtr = NoSubTree;
else if (proot->left == NULL)
subtr = RightSubTree;
else if (proot->right == NULL)
subtr = LeftSubTree;
else
subtr = TwoSubTrees;
switch (subtr) {
case NoSubTree:
root = NULL; break;
case LeftSubTree:
root = proot->left; break;
case RightSubTree:
root = proot->right; break;
case TwoSubTrees:
TREE* pnew_root = proot->right, * pnew_prnt = proot;
while (pnew_root->left != NULL) {
pnew_prnt = pnew_root;
pnew_root = pnew_root->left;
}
pnew_root->left = proot->left;
if (pnew_root != proot->right) {
pnew_prnt->left = pnew_root->right;
pnew_root->right = proot->right;
}
root = pnew_root;
}
free(proot);
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