Удаление элемента из бинарного дерева - C (СИ)
Формулировка задачи:
в программе выполняется пару ф-й, не работает удаление элемента (в меню пункт 1), должен удалить узел где длина кода более 5, при попытке удалить крайней листок не имеющий потомков выдает, а ежели удалять элементы имеющие потомков, то когда печатает дерево выдает ту же ошибку, даю файл с деревом и ВЕСЬ код программы.
т.е. не работают: void DeleteNode (Tree ** root_adr);
код сбалансированного дерева " balanced[1]":
h 001 d 002 l 003 b 004 f 005 j 006 n 007 a 008 c 009 e 010 g 011 i 0121212 k 013 m 014 o 015
код не сбалансированного дерева "not balanced[2]" :
d 01 b 02 j 03 a 04 c 05 g 06 m 007 f 080808 h 09 l 10 n 11 e 12 o 13
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct key_combinations { char *key; char *combination; } KEY_COMBINATION; typedef struct tree { KEY_COMBINATION kc; struct tree *left,*right; }Tree; Tree *root; Tree ** stack; void AddNode (Tree * proot, Tree * pnew) ; void GetData (); void PrintTree(); void ShowTree(Tree *rooot, int lvl); void PutTree(Tree *rooot); void ifMore(Tree *rooot); void DeleteNode (Tree ** root_adr); void FreeNode (Tree * node) ; int TreeHeight(Tree * proot); void DigitNumber(Tree * proot); void RightToTop(Tree **root_adr); void DeleteTree(Tree *rooot) ; int main() { GetData (); PrintTree(); int menu=1,len=0; while(menu>0) { printf("\n\n delete where len>5 [1]\n right ot top [2] \n iteretion funk [3] \n free && exit [0] \n "); scanf("%d",&menu); switch(menu) { case 1: ifMore(root); PrintTree(); break; case 2: len=TreeHeight(root); printf("\n Tree height = %d with root : %s",len,root->kc.key); RightToTop(&root); len=TreeHeight(root); printf("\n Tree height = %d with root : %s",len,root->kc.key); break; case 3: stack=(Tree **)calloc(TreeHeight(root), sizeof(Tree *)); DigitNumber(root); break; case 0: DeleteTree(root); break; } } return 0; } void GetData () { Tree * pel; KEY_COMBINATION * pkc; char bufk[3],bufc[25]; FILE* f; pkc = (KEY_COMBINATION *)malloc(sizeof(KEY_COMBINATION)); int choise; printf("choose file balanced[1] not balanced[2] : "); scanf("%d",&choise); if(choise==2) f = fopen("TreeNB","r"); else f = fopen("TreeB","r"); while(fscanf(f,"%s%s",bufk,bufc)!=EOF) { //printf("\n %s %s",bufk,bufc); pkc->key = (char * ) malloc(strlen(bufk)+1); strcpy(pkc->key, bufk); pkc->combination =(char * ) malloc(strlen(bufc)+1); strcpy(pkc->combination, bufc); pel = (Tree *)malloc(sizeof(Tree)); pel->kc = * pkc; pel->left = NULL; pel->right = NULL; AddNode(root,pel); } } void AddNode (Tree * proot, Tree * pnew) { if (root == NULL) root = pnew; else if (strcmp(proot->kc.key, pnew->kc.key)>0) if (proot->left == NULL) proot->left = pnew; else AddNode(proot->left, pnew); else if (proot->right == NULL) proot->right = pnew; else AddNode(proot->right, pnew); } void PrintTree() { puts("\n==============================="); PutTree(root); puts("\n===============================\n"); ShowTree(root,1); puts("==============================="); } void ShowTree(Tree *rooot, int lvl) { if(rooot==NULL) return; ShowTree(rooot->right,lvl+1); printf("%*c%s\n", lvl*3,' ', rooot->kc.key); ShowTree(rooot->left,lvl+1); } void PutTree(Tree *rooot) { if(rooot==NULL) return; printf("\n\t%s -\t%s", rooot->kc.key, rooot->kc.combination); PutTree(rooot->left); PutTree(rooot->right); } void ifMore(Tree *rooot) { if(rooot==NULL) return; if(strlen(rooot->kc.combination)>5) { printf("found %s",rooot->kc.key); printf("\n %s-%s", rooot->kc.key, rooot->kc.combination); DeleteNode(&rooot); ifMore(rooot); } ifMore(rooot->left); ifMore(rooot->right); } void FreeNode (Tree * node) { free(node->kc.key); free(node->kc.combination); free(node); } 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 DigitNumber(Tree * proot) { int i=0; Tree * pdel = root, * pnext; while (pdel!= NULL) { if (pdel->left!= NULL) { pnext = pdel->left; if (pdel->right!= NULL) stack[++i] = pdel->right; } else if (pdel->right!= NULL) pnext = pdel->right; else pnext = stack[i--]; int n = strlen(pdel->kc.combination); printf("%s -%s - digit number = %d\n ",pdel->kc.key,pdel->kc.combination,n); pdel = pnext; } } void RightToTop(Tree **root_adr) { Tree *proot = *root_adr,*pright = *root_adr,*prev; while(pright->right!=NULL) { prev=pright; pright=pright->right; } prev->right=NULL; pright->left=proot; *root_adr=pright; } void DeleteNode (Tree ** root_adr) { Tree * proot = *root_adr, * pright, * padd; int cmp, subtr; if (proot == NULL) return; if (proot->left == NULL && proot->right == NULL) subtr = 0; else if (proot->left == NULL) subtr = 1; else if (proot->right == NULL) subtr = -1; else subtr = 2; switch (subtr) { case 0: *root_adr = NULL; break; case -1: *root_adr = proot->left; break; case 1: *root_adr = proot->right; break; case 2: *root_adr = proot->left; pright = proot->left->right; padd = proot->left->right=proot->right ; proot->right=NULL; while (padd->left!= NULL) padd = padd->left; padd->left = pright; break; } FreeNode(proot); printf(" free.."); } void DeleteTree(Tree *rooot) { if(rooot==NULL) return; DeleteTree(rooot->left); DeleteTree(rooot->right); free(rooot); }
Решение задачи: «Удаление элемента из бинарного дерева»
textual
Листинг программы
void Del(ELT *q) { if(q!=NULL) { Del(q->left); Del(q->reght); free(q); } }
Объяснение кода листинга программы
- В функции
Del
аргументом является указатель на узелq
. - Если
q
не равенNULL
, то выполняется рекурсивный вызов функцииDel
для левого поддереваq->left
. - После этого выполняется рекурсивный вызов функции
Del
для правого поддереваq->right
. - Затем освобождается память, выделенная под узел
q
, с помощью функцииfree
. - Если
q
равенNULL
, то ничего не происходит.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д