@Retr0Hacker

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

Задача:

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
  • Вопрос задан
  • 96 просмотров
Пригласить эксперта
Ответы на вопрос 1
OCTAGRAM
@OCTAGRAM
В бинарном дереве поиска, чтобы удалить узел с детьми, его нужно сначала обменять с соседним более нижним, а потом удалить на новом месте. Под соседом понимается не связанный узел, а ближайший по значению. Алгоритмически это правейший потомок непосредственно левого сына или левейший потомок непосредственно правого сына. Так как он левейший или правейший, одного узла у него не будет, вы точно сможете его там удалить.

Пример дерева:

.
   4
 2   6
1 3 5 7


Если выстроить дерево поиска в ряд, то получится 1-2-3-4-5-6-7. Чтобы удалить 4, надо, например, обменять 4 и 5, временно нарушив порядок в дереве, а потом удалить 4 в новой позиции. В дереве не стало 4, а порядок снова восстановлен.

1-2-3-4-5-6-7
1-2-3-5-4-6-7
1-2-3-5-6-7


.
   5
 2   6
1 3 4 7


.
   5
 2   6
1 3   7
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы