Jedes 2. Element aus einem Binärbaum löschen

  • Jedes 2. Element aus einem Binärbaum löschen

    Hallo,

    stehe vor folgendem Problem:
    Ich habe einen BBaum aufgebaut (nicht balanciert!!!) und stehe jetzt vor dem Problem jedes 2. Element aus diesem Baum zu löschen.

    Hab mir das so vorgestellt,
    das ich mir den Baum traversieren lasse und dann jedes 2. Element lösche (habe neben den Nutzdaten in jedem Element auch noch nen Zähler stehen der mir angibt wann das Element eingefügt wurde) und an dessen Stelle das kleinste Element des rechten Teilbaumes hinsetze.
    Soweit ist das ja nicht so schwierig,
    aber wie komme ich an den Vorgänger des jeweils 2. Elements???

    Ich muss ja den Zeiger des Vorgängers des jeweils 2. Elements umhängen, stehe aber vor dem Problem wie komme ich zum Vorgänger.

    Bin für jeden Tip (oder URL) dankbar :D


    P.S.: Wie schon gesagt ist der Baum nicht balanciert, und muss auch nach dem Löschen nicht balanciert sein.

  • baum.h

    Quellcode

    1. #ifndef _BAUM_
    2. #define _BAUM_
    4. #include <iostream>
    5. using namespace std;
    7. class Blatt
    8. {
    9. public:
    10. Blatt(const char*, const char*);
    11. ~Blatt();
    12. const char* getSchluessel(){return schluessel;}
    13. const char* getWert(){return wert;}
    14. void setZaehler(void);
    15. //bool operator<(Blatt &obj){return (strcmp(this->schluessel, obj.schluessel) < 0);}
    16. //bool operator==(Blatt &obj){return (strcmp(this->schluessel, obj.schluessel) == 0);}
    18. private:
    19. char schluessel[30];
    20. char *wert;
    21. int zaehler;
    22. int tiefe;
    23. Blatt *links, *rechts;
    24. friend class Baum;
    25. };
    27. class Baum
    28. {
    29. public:
    30. void add(Blatt *);
    31. void addRekursive(bool, Blatt *, Blatt *);
    32. void remove(Blatt *);
    33. const char * operator[](const char *);
    34. void maxTiefeErmittlung(Blatt *);
    35. void maxSuchweg(const char *, Blatt *);
    36. void inorder2(Blatt *);
    37. void jeden2tenLoeschen(Blatt *);
    38. };
    41. Blatt *anker = 0;
    42. static int maxTiefe = 0;
    43. char maxTiefeElement[30];
    45. #endif
    Alles anzeigen


    baum.cpp

    Quellcode

    1. #include "baum.h"
    2. #include <iostream>
    3. #include <assert.h>
    4. #include <crtdbg.h>
    5. using namespace std;
    9. int main()
    10. {
    11. Baum b;
    13. Blatt *keyValue1 = new Blatt("L", "01. Wert");
    14. Blatt *keyValue2 = new Blatt("J", "02. Wert");
    15. Blatt *keyValue3 = new Blatt("N", "03. Wert");
    16. Blatt *keyValue4 = new Blatt("D", "04. Wert");
    17. Blatt *keyValue5 = new Blatt("K", "05. Wert");
    18. Blatt *keyValue6 = new Blatt("M", "06. Wert");
    19. Blatt *keyValue7 = new Blatt("O", "07. Wert");
    20. Blatt *keyValue8 = new Blatt("C", "08. Wert");
    21. Blatt *keyValue9 = new Blatt("E", "09. Wert");
    22. Blatt *keyValue10 = new Blatt("P", "10. Wert");
    23. Blatt *keyValue11 = new Blatt("A", "11. Wert");
    24. Blatt *keyValue12 = new Blatt("B", "12. Wert");
    25. Blatt *keyValue13 = new Blatt("H", "13. Wert");
    26. Blatt *keyValue14 = new Blatt("Q", "14. Wert");
    27. Blatt *keyValue15 = new Blatt("G", "15. Wert");
    28. Blatt *keyValue16 = new Blatt("I", "16. Wert");
    29. Blatt *keyValue17 = new Blatt("F", "17. Wert");
    30. Blatt *keyValue18 = new Blatt("R", "18. Wert");
    31. Blatt *keyValue19 = new Blatt("S", "19. Wert");
    32. Blatt *keyValue20 = new Blatt("X", "20. Wert");
    35. b.add(keyValue1);
    36. b.add(keyValue2);
    37. b.add(keyValue3);
    38. b.add(keyValue4);
    39. b.add(keyValue5);
    40. b.add(keyValue6);
    41. b.add(keyValue7);
    42. b.add(keyValue8);
    43. b.add(keyValue9);
    44. b.add(keyValue10);
    45. b.add(keyValue11);
    46. b.add(keyValue12);
    47. b.add(keyValue13);
    48. b.add(keyValue14);
    49. b.add(keyValue15);
    50. b.add(keyValue16);
    51. b.add(keyValue17);
    52. b.add(keyValue18);
    53. b.add(keyValue19);
    54. b.add(keyValue20);
    57. delete keyValue1;
    58. delete keyValue2;
    59. delete keyValue3;
    60. delete keyValue4;
    61. delete keyValue5;
    62. delete keyValue6;
    63. delete keyValue7;
    64. delete keyValue8;
    65. delete keyValue9;
    66. delete keyValue10;
    67. delete keyValue11;
    68. delete keyValue12;
    69. delete keyValue13;
    70. delete keyValue14;
    71. delete keyValue15;
    72. delete keyValue16;
    73. delete keyValue17;
    74. delete keyValue18;
    75. delete keyValue19;
    76. delete keyValue20;
    78. _CrtDumpMemoryLeaks();
    79. }
    81. /////////////////////////////////////////////////////////
    82. /////////////////////////////////////////////////////////
    84. Blatt::Blatt(const char *key, const char *value)
    85. {
    86. size_t keyLen = strlen(key) + 1;
    87. strcpy_s(schluessel, keyLen, key);
    89. size_t valueLen = strlen(value) + 1;
    90. wert = new char[valueLen];
    91. assert(wert);
    92. strcpy_s(wert, valueLen, value);
    94. links = 0;
    95. rechts = 0;
    96. }
    98. Blatt::~Blatt()
    99. {
    100. if (anker)
    101. {
    102. delete[] wert;
    103. }
    104. }
    106. void Blatt::setZaehler()
    107. {
    108. static int counter = 1;
    109. zaehler = counter;
    110. counter++;
    111. }
    113. /////////////////////////////////////////////////////////
    114. /////////////////////////////////////////////////////////
    116. void Baum::add(Blatt *obj)
    117. {
    118. if (anker == 0)
    119. {
    120. obj->setZaehler();
    121. obj->tiefe = 0;
    122. maxTiefeErmittlung(obj);
    123. anker = obj;
    124. //cout << "eingefuegt :: " << obj->schluessel << " :: nr:" << obj->zaehler << endl;
    125. return;
    126. }
    127. else
    128. {
    129. if (strcmp(obj->schluessel, anker->schluessel) < 0)
    130. {
    131. //links
    132. //cout << "Linker Teilbaum:" << endl;
    133. addRekursive(1, anker, obj);
    134. return;
    135. }
    136. else
    137. {
    138. //rechts
    139. //cout << "Rechter Teilbaum:" << endl;
    140. addRekursive(0, anker, obj);
    141. return;
    142. }
    143. }
    144. }
    146. void Baum::addRekursive(bool left, Blatt *pos, Blatt *obj) //bool left = 1 -> links einfügen
    147. {
    148. Blatt *hilfszeiger = pos;
    149. static int tiefe = 1;
    151. //Blatt wird links eingefügt (bool left = 1)
    152. if (left)
    153. {
    154. //linke Position frei
    155. if (hilfszeiger->links == 0)
    156. {
    157. obj->setZaehler();
    158. obj->tiefe = tiefe;
    159. maxTiefeErmittlung(obj);
    160. hilfszeiger->links = obj;
    161. //cout << "Tiefe:" << tiefe << " :: links eingefuegt :: " << obj->schluessel << " :: nr:" << obj->zaehler << endl;
    162. tiefe = 1;
    163. return;
    164. }
    165. else
    166. {
    167. //linke Position besetzt, also erneut vergleichen
    168. if (strcmp(obj->schluessel, hilfszeiger->links->schluessel) < 0)
    169. {
    170. //cout << "Tiefe:" << tiefe << endl;
    171. tiefe++;
    172. addRekursive(1, hilfszeiger->links, obj);
    173. return;
    174. }
    175. else
    176. {
    177. //cout << "Tiefe:" << tiefe << endl;
    178. tiefe++;
    179. addRekursive(0, hilfszeiger->links, obj);
    180. return;
    181. }
    182. }
    183. }
    184. //Blatt wird rechts eingefügt (bool left = 0)
    185. else
    186. {
    187. if (hilfszeiger->rechts == 0)
    188. {
    189. obj->setZaehler();
    190. obj->tiefe = tiefe;
    191. maxTiefeErmittlung(obj);
    192. hilfszeiger->rechts = obj;
    193. //cout << "Tiefe:" << tiefe << " :: rechts eingefuegt :: " << obj->schluessel << " :: nr:" << obj->zaehler << endl;
    194. tiefe = 1;
    195. return;
    196. }
    197. else
    198. {
    199. if (strcmp(obj->schluessel, hilfszeiger->rechts->schluessel) < 0)
    200. {
    201. //cout << "Tiefe:" << tiefe << endl;
    202. tiefe++;
    203. addRekursive(1, hilfszeiger->rechts, obj);
    204. return;
    205. }
    206. else
    207. {
    208. //cout << "Tiefe:" << tiefe << endl;
    209. tiefe++;
    210. addRekursive(0, hilfszeiger->rechts, obj);
    211. return;
    212. }
    213. }
    214. }
    215. }
    217. const char * Baum::operator[](const char *key)
    218. {
    219. static Blatt *hilfszeiger;
    220. static bool rekursiverAufruf = false;
    221. static bool nichtInListe;
    222. if (!rekursiverAufruf)
    223. {
    224. hilfszeiger = anker;
    225. nichtInListe = false;
    226. }
    228. if (hilfszeiger)
    229. {
    230. if (strcmp(key, hilfszeiger->schluessel) == 0)
    231. {
    232. rekursiverAufruf = false;
    233. return hilfszeiger->wert;
    234. }
    235. else
    236. {
    237. if (strcmp(key, hilfszeiger->schluessel) < 0)
    238. {
    239. if (hilfszeiger->links != 0)
    240. {
    241. hilfszeiger = hilfszeiger->links;
    242. rekursiverAufruf = true;
    243. operator[](key);
    244. }
    245. else
    246. {
    247. nichtInListe = true;
    248. }
    249. }
    250. else
    251. {
    252. if (hilfszeiger->rechts != 0)
    253. {
    254. hilfszeiger = hilfszeiger->rechts;
    255. rekursiverAufruf = true;
    256. operator[](key);
    257. }
    258. else
    259. {
    260. nichtInListe = true;
    261. }
    262. }
    263. }
    264. }
    265. if (nichtInListe)
    266. {
    267. rekursiverAufruf = false;
    268. return "Nicht in Liste";
    269. }
    270. else
    271. {
    272. return hilfszeiger->wert;
    273. }
    274. }
    276. void Baum::maxTiefeErmittlung(Blatt *obj)
    277. {
    278. size_t keyLen = strlen(obj->schluessel) + 1;
    280. if (obj->tiefe > maxTiefe)
    281. {
    282. maxTiefe = obj->tiefe;
    283. strcpy_s(maxTiefeElement, keyLen, obj->schluessel);
    284. }
    285. }
    287. void Baum::maxSuchweg(const char *key, Blatt *obj)
    288. {
    289. static bool rekursiverAufruf = false;
    290. static Blatt *hilfszeiger;
    291. static int suchschritte;
    292. if (!rekursiverAufruf)
    293. {
    294. hilfszeiger = anker;
    295. suchschritte = 1;
    296. cout << "Maximalen Suchweg fuer Element " << maxTiefeElement << " ermitteln" << endl;
    297. }
    299. if (hilfszeiger)
    300. {
    301. if (strcmp(key, hilfszeiger->schluessel) == 0)
    302. {
    303. cout << "Gesuchtes Element(" << hilfszeiger->schluessel << " -> " << hilfszeiger->wert << ") gefunden!" << endl;
    304. cout << "Anzahl Suchschritte: " << suchschritte << endl;
    305. }
    306. else
    307. {
    308. if (strcmp(key, hilfszeiger->schluessel) < 0)
    309. {
    310. cout << hilfszeiger->schluessel << " -> " << hilfszeiger->wert << endl;
    311. hilfszeiger = hilfszeiger->links;
    312. rekursiverAufruf = true;
    313. suchschritte++;
    314. maxSuchweg(key, hilfszeiger);
    315. }
    316. else
    317. {
    318. cout << hilfszeiger->schluessel << " -> " << hilfszeiger->wert << endl;
    319. hilfszeiger = hilfszeiger->rechts;
    320. rekursiverAufruf = true;
    321. suchschritte++;
    322. maxSuchweg(key, hilfszeiger);
    323. }
    324. }
    325. }
    326. }
    328. void Baum::inorder2(Blatt *obj) //traversiert inorder und ruft die Methode 'jeden2tenLoeschen(Blatt *)' auf
    329. {
    330. Blatt *hilfszeiger = obj;
    332. if (hilfszeiger->links)
    333. {
    334. inorder2(hilfszeiger->links);
    335. }
    336. jeden2tenLoeschen(hilfszeiger);
    337. if (hilfszeiger->rechts)
    338. {
    339. inorder2(hilfszeiger->rechts);
    340. }
    341. }
    343. void Baum::jeden2tenLoeschen(Blatt *obj)
    344. {
    345. if (obj->zaehler % 2 == 0)
    346. {
    347. cout << obj->schluessel << " :: " << obj->zaehler << endl;
    348. }
    349. }
    Alles anzeigen


    Beispiel:
    Möchte die 6 löschen, dann setze ich die 7 an dessen Stelle.
    Aber dafür muss ich den rechten Zeiger der 3 umsetzen.
    Aber wie komme ich zur 3???
    Bilder

    • baum.JPG

      6,33 kB, 512×384, 278 mal angesehen

  • :D
    Habe über dem Problem die grundlegende Eigenschaft des Binärbaumes vergessen.

    Hab jetzt ne Möglichkeit gefunden, mein Problem zu lösen.
    Da ich aber noch etwas Zeit habe die Aufgabe zu lösen mach ich mich jetzt nicht an die Aufgabe.


    Trotzdem dank an alle die sich mit dem Problem beschäftigt haben :!:


    :) Ich wünsche Allen schöne Feiertage und nen guten Rutsch :)