Как удалить необходимые узлы из бинарного дерева?

[Retr0Hacker]

Добрейший вечерочек форумчанам.

На повестке дня вот такая задачка:

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