The task is more than simple, but it put me in a stupor ... It is necessary to remove all the odd elements from the ordinary binary tree and display the same new tree on the screen. The user enters int n - the number of elements and the elements of the tree itself. Here is what I could write (somewhere myself, somewhere I took from the Internet)

#include <stdio.h> #include <stdlib.h> #include "bintree.h" void paste_node(Tree ** tr, int x) //процедура вставки нового узла { Tree *tree_bin; if ((*tr) == NULL) { //если дерево пусто, то tree_bin = (Tree *)malloc(sizeof(Tree)); //возвращаем указатель на первый байт, если памяти не хватает на нулевой, //с помощью функции malloc tree_bin->item = x; //inf = x tree_bin->lchild = tree_bin->rchild = NULL; //ссылки на левого и правого ребёнка NULL *tr = tree_bin; return; //выход из процедуры } if (x < (*tr)->item) { //если вводимое значение меньше текущего значения, то paste_node(&((*tr)->lchild), x); //вызываем рекурсивно функцию paste_node от левого ребёнка и x } else { //иначе paste_node(&((*tr)->rchild), x); //от правого ребёнка и х } } Tree * minimum(Tree *tr) { if (!tr->lchild->lchild) return tr; return minimum(tr->lchild); } void delete_node(Tree** tr, int num, Tree* parent) //процедура удаления элемента { if (!(*tr)) return; //если дерево пусто, выход из процедуры if (num < (*tr)->item) delete_node(&((*tr)->lchild), num, *tr); else if (num >(*tr)->item) delete_node(&((*tr)->rchild), num, *tr); else { if (!(*tr)->lchild && !(*tr)->rchild) {//Если детей у удаляемого узла нет, то перед нами самый простой случай - листовой узел. if (parent) {//Родителю данного узла надо сообщить о том, что потомка у него теперь нет if (parent->lchild) { if (parent->lchild->item == (*tr)->item) { //Если удаляется левый потомок parent->lchild = NULL; } } if (parent->rchild) { if (parent->rchild->item == (*tr)->item) { //Если удаляется правый потомок parent->rchild = NULL; } } } free(*tr); // Освобождаем память *tr = NULL; } else if (!(*tr)->lchild || !(*tr)->rchild) { // Если у удаляемой вершины есть хотя бы один потомок Tree* nodeToRemove = NULL; if ((*tr)->lchild) { //Находим того самого единственного потомка удаляемой вершины nodeToRemove = (*tr)->lchild; } else { nodeToRemove = (*tr)->rchild; } //Скопировать все данные из единственного потомка удаляемой вершины (*tr)->lchild = nodeToRemove->lchild; (*tr)->rchild = nodeToRemove->rchild; (*tr)->item = nodeToRemove->item; //Освободить память, выделенную ранее для данного потомка free(nodeToRemove); } else { //Если у удаляемой вершины есть оба потомка, то согласно алгоритму необходимо найти наименьший элемент в правом поддереве удаляемого элемента if (!(*tr)->rchild->lchild) { //Если у правого поддерева нет левых потомков, то это означает, что у всех потомков значение ключа больше, //а значит надо просто скопировать значения из правого потомка в удаляемый элемент (*tr)->item = (*tr)->rchild->item; // Скопировать значение из правого потомка Tree* rightRIghtChild = (*tr)->rchild->rchild; free((*tr)->rchild); // Освбодить память, выделенную для правого потомка (*tr)->rchild = rightRIghtChild; } else { Tree* minNodeParent = minimum((*tr)->rchild); //Поиск наименьшего элемента в правом поддереве (он обязательно найдётся, случай когда его нет был разобран выше) (*tr)->item = minNodeParent->lchild->item; //Скопировать значение из наименьшего жлемента в правом поддереве в удаляемый элемент free(minNodeParent->lchild); minNodeParent->lchild = NULL; } } } } void print_tree(Tree *tr, int depth) { if (tr != NULL) { print_tree(tr->lchild, depth + 1); for (int i = 0; i < depth; ++i) printf(" "); printf("%d<\n", tr->item); print_tree(tr->rchild, depth + 1); } } void delete_nechet(Tree *tr) { if (!tr) return; if (tr->item % 2 != 0) delete_node(*tr, tr->item, NULL); if (tr->lchild != NULL) delete_nechet(*tr->lchild); if (tr->rchild != NULL) delete_nechet(*tr->rchild); } int main() { int n; cin >> n; Tree tr; for (int i = 0; i < n; i++) { int x; cin >> x; paste_node(tr, x); } delete_nechet(*tr); print_tree(tr, 0); return 0; }

The very first mistake that comes out at the compilation stage is the absence of the bintree.h library, and further ...

How can this be fixed? What am I doing wrong? I will be glad to any help

  • It’s you, as if to explain ... in the situation of the robber who stole the safe, but left the key, and breaking it without the key doesn’t work out :) In this header file, all the necessary announcements - for example, what a Tree ... - Harry

1 answer 1

In "bintree.h" obviously, the structure of the node is defined (Tree). This can be done independently.

In order not to chop the branch on which you sit, it is better to do so - first we delete the odd ones in the subtrees, then check the root

 void delete_nechet(Tree *tr) { if (!tr) return; if (tr->lchild <> NULL) delete_nechet(*tr->lchild); if (tr->rchild <> NULL) delete_nechet(*tr->rchild); if (tr->item % 2 != 0) delete_node(*tr, tr->item, NULL); }
  • What kind of operator is so interesting "<>"?) - Mikhail Murugov
  • @ Mikhail Murugov is not equal to Pascal :) - MBo