Удаление элементов из бинарного дерева (не дерево поиска)

Задание заключается в создании бинарного дерева, из букв введенной строки, обходе дерева и удалении согласных букв из дерева.

проблема заключается в последнем задании. при удалении элемента все разделяется на 3 случая, как я понял нет потомков, 1 потомок, 2 потомка. поскольку у меня простое бинарное дерево, балансировать, вертеть его мне не требуется.

так вот ближе к сути, в моей реализации отсутствует указатель на предка, в результате чего удаление затруднено.

хотел реализовать рекурсивный алгоритм с обратным обходом для удаления элементов(чтоб указатели не потерять) но вываливается ошибка. по видимому изза NULL ов , точнее их отсутствия. попробовал прикрутить указатель на предка, но что то тоже не выходит.

подскажите алгоритм удаления по условию без использования указателя на предка или подскажите как при создании дополнить правильно это поле?

Добавлено через 1 минуту

заголовочный файл

C++Выделить код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#pragma once
struct Node
{   char data;
    Node left, right, parent;
 
};
class Tree
{
public:
    Node CreateTree(int n, char, Node);
    void PrintTree(Node,int n);
    Node GetHead(){ return _head; }
    void PreOrderWalk(Node);
    void DelСonsonants(Node);
    Tree(int,char);
    ~Tree();
private:
    Node _head;
    int Nodes;
    int _CountofNodes;
};

файл ресурсов

C++Выделить код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#include "Tree.h"
#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;
 
 
 
Tree::Tree(int n, char s1)
{
    _head = CreateTree(n, s1, nullptr);
    _CountofNodes = n;
    Nodes = new int [n];
    for (int i = 0; i < n; i++)
    {
        Nodes[i] = new int[n];
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
    {
        Nodes[i][j] = 0;
    }
 
}
 
Node Tree::CreateTree(int n, char s1, Node parent)
{
    int nl, nr;
    Node head;
    if (n > 0 )
    {
        nl = n / 2;
        nr = n - nl - 1;
        head = new Node;
        head -> data = s1[rand()%20];
        head -> left = CreateTree(nl,s1,head);
        head->right = CreateTree(nr, s1,head);
        head->parent = parent;
    }
    else
    { 
        head = nullptr; 
    }
    return head;
}
 
void Tree::PrintTree(Node head, int n)
{
    if ( head != nullptr)
    {
        PrintTree(head->right, n + 2);
        for (int i = 1; i < n; i++)
        {
            cout << "  ";
        }
        cout << head->data << endl;
        PrintTree(head->left, n + 2);
    }
}
 
void Tree::PreOrderWalk(Node head)
{ 
    if (head == nullptr)    return;    //Если дерева нет, выходим
 
    cout << head->data << "  "; //Посетили узел
    PreOrderWalk(head->left); //Обошли левое поддерево    
    PreOrderWalk(head->right); //
}
 
void Tree::DelСonsonants(Node head)
{   
    char Сonsonants[42] = "bcdfghjklmnpqrstvwxyzBCDFGHJKLMNPQRSVWXYZ";
        if (head == nullptr)    return;    //Если дерева нет, выходим;
        //DelСonsonants(head->left); //Обошли левое поддерево 
        //DelСonsonants(head->right); //Обошли правое поддерево  
        head->left;
        cout << endl << head->parent->data << endl;
        /  for (int i = 0; i < 42; i++)
        {
            if (head->data == Сonsonants[i])
            {
            
            }
        }/
}
Tree::~Tree()
{
}

файл основной программы

C++Выделить код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include "Tree.h"
using namespace std;
void main()
{
    const int n = 20;
    char s1[50];
    cout << "vvedite s " << endl;
    cin.getline(s1, n);
    Tree n1(n,s1);
    Node head = n1.GetHead();
    n1.CreateTree(n,s1,nullptr);
    n1.PrintTree(head,n);
    system("pause");
    n1.PreOrderWalk(head);
    system("pause");
    n1.DelСonsonants(head);
    n1.PrintTree(head, n);
    system("pause");
 
}