c++ - 层序遍历 : Deleting a Subtree

Question

#include <iostream>

using namespace std;

struct node {
    int item;
    node* l;
    node* r;
    node (int x) {
        item = x;
        l = 0;
        r = 0;
    }
    node(int x, node* l, node* r) {
        item = x;
        this->l = l;
        this->r = r;
    }
};

typedef node* link;

class QUEUE {
private:
    link* q;
    int N;
    int head;
    int tail;
public:
    QUEUE(int maxN) {
        q = new link[maxN + 1];
        N = maxN + 1;
        head = N;
        tail = 0;
    }
    int empty() const {
        return head % N == tail;
    }
    void put(link item) {
        q[tail++] = item;
        tail = tail % N;
    }

    link get() {
        head = head % N;
        return q[head++];
    }
};

link head = 0; // Initial head of the tree

link find(int x) {
    if (head == 0) {
        cout << "\nEmpty Tree\n";
        return 0;
    }
    link temp = head;
    // To find the node with the value x and return its link
    QUEUE q(100);
    q.put(temp);
    while (!q.empty()) {
        temp = q.get();
        if (temp->item == x) {
            return temp;
        }
        if (temp->l != 0) q.put(temp->l);
        if (temp->r != 0) q.put(temp->r);
    }
    return 0;
}

void print(link temp) {
    QUEUE q(100);
    q.put(temp);
    while (!q.empty()) {
        temp = q.get();
        cout << temp->item << ", ";
        if (temp->l != 0) q.put(temp->l);
        if (temp->r != 0) q.put(temp->r);
    }
}

void deleteAll(link h) {
    // This deletes the entire binary tree
    QUEUE q(100);
    q.put(h);
    while (!q.empty()) {
        h = q.get();
        if (h->l != 0) q.put(h->l);
        if (h->r != 0) q.put(h->r);
        delete h;
    }
}

int main() {
    link temp = 0;
    char c;
    int n1, n2;
    cout << "\n\nPlease enter the input instructions (X to exit program) : \n\n";
    do {
        cin >> c;
        switch (c) {
            case 'C':   cin >> n1;
                        if (head == 0) {
                            head = new node(n1);
                            cout << "\nRoot node with item " << n1 << " has been created\n\n";
                        } else {
                            cout << "\nError: Tree is not empty\n\n";
                        }
                        break;

            case 'L':   cin >> n1 >> n2;
                        temp = find(n1);
                        if (temp != 0) {
                            if (temp->l == 0) {
                                temp->l = new node(n2);
                                cout << "\nNode with item " << n2 << " has been added\n\n";
                            }
                            else {
                                cout << "\nError: The specified node already has a left child\n\n";
                            }
                        }
                        else {
                            cout << "\nError: The specified node doesn't exist\n\n";
                        }
                        break;

            case 'R':   cin >> n1 >> n2;
                        temp = find(n1);
                        if (temp != 0) {
                            if (temp->r == 0) {
                                temp->r = new node(n2);
                                cout << "\nNode with item " << n2 << " has been added\n\n";
                            }
                            else {
                                cout << "\nError: The specified node already has a right child\n\n";
                            }
                        }
                        else {
                            cout << "\nError: The specified node doesn't exist\n\n";
                        }
                        break;

            case 'P':   cin >> n1;
                        temp = find(n1);
                        if (head != 0) {
                            cout << "\nLevel-order traversal of the entire tree: ";
                            print(temp);
                        }
                        else {
                            cout << "\nError: No elements to print\n\n";
                        }
                        break;

            case 'D':   cin >> n1;
                        temp = find(n1); 
                        deleteAll(temp);
                        temp = 0;
                        break;

            case 'X':   cout << "\nExiting Program\n\n";
                        break;

            default:    cout << "\nInvalid input entered. Try again.\n\n";

        }
    } while (c != 'X');
    system("pause");
    return 0;
}

示例输入:

C 9
L 9 8
R 9 6
L 8 3
R 8 5
R 6 2
L 3 4
L 4 10
L 5 1
R 5 11
L 1 12
R 1 7

一切正常，直到我删除一个子树并在崩溃前打印垃圾值时打印。请帮助我找出错误，因为我已经尝试了几个小时但没有成功。

一切正常，直到我删除一个子树并在崩溃前打印垃圾值时打印。请帮助我找出错误，因为我已经尝试了几个小时但没有成功。

Answer 1

尝试递归函数:

void Delete(link h)
{
  if(h)
  {
    if(h->l) Delete(h->l);
    if(h->r) Delete(h->r);
    delete(h);
  }
}