关卡顺序遍历:删除子树

#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 Treen";
        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 << "nnPlease enter the input instructions (X to exit program) : nn";
    do {
        cin >> c;
        switch (c) {
            case 'C':   cin >> n1;
                        if (head == 0) {
                            head = new node(n1);
                            cout << "nRoot node with item " << n1 << " has been creatednn";
                        } else {
                            cout << "nError: Tree is not emptynn";
                        }
                        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 addednn";
                            }
                            else {
                                cout << "nError: The specified node already has a left childnn";
                            }
                        }
                        else {
                            cout << "nError: The specified node doesn't existnn";
                        }
                        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 addednn";
                            }
                            else {
                                cout << "nError: The specified node already has a right childnn";
                            }
                        }
                        else {
                            cout << "nError: The specified node doesn't existnn";
                        }
                        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 printnn";
                        }
                        break;
            case 'D':   cin >> n1;
                        temp = find(n1); 
                        deleteAll(temp);
                        temp = 0;
                        break;
            case 'X':   cout << "nExiting Programnn";
                        break;
            default:    cout << "nInvalid input entered. Try again.nn";
        }
    } while (c != 'X');
    system("pause");
    return 0;
}

示例输入：

一切都很好，直到我删除子树并在崩溃前打印垃圾值时打印。请帮我找出错误，因为我已经徒劳地尝试了几个小时。

尝试递归函数：

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

删除节点时，调用deleteAll(temp) 会删除temp，但它不会从temp父节点的l或r中删除指针值。

这会给您留下无效的指针，从而导致垃圾打印和崩溃。

不幸的是，您的查找当前的工作方式是，当您检查其值时，您不知道当前temp节点的父节点是什么。

修复它的一种方法是使用不同类型的find(称为类似 remove (，它在每次迭代时l和r查找值，并在返回指针之前将l或r设置为NULL。对于何时在根中找到值，您可能必须有一个特殊情况。

编辑(添加了示例代码(：

我假设您出于某种原因没有使用递归，所以我的代码使用您现有的基于队列的代码。我只做了足够的改变才能让它工作。

findAndUnlink找到具有给定值的节点并将其与树"取消链接"。它返回找到的节点，为您提供一个完全独立的树。注意：由调用方释放返回的树，否则您将泄漏内存。

这是对现有代码中find的替换，因为现有代码随后在返回的节点上调用deleteAll。

link findAndUnlink(int x) {
    if (head == 0) {
        cout << "nEmpty Treen";
        return 0;
    }
    link temp = head;
    if (temp->item == x) {
        // remove whole tree
        head = NULL;
        return temp;
    }
    // To find the node with the value x and remove it from the tree and return its link
    QUEUE q(100);
    q.put(temp);
    while (!q.empty()) {
        temp = q.get();
        if (temp->l != NULL) {
            if (temp->l->item == x) {
                link returnLink = temp->l;
                temp->l = NULL;
                return returnLink;
            }
            q.put(temp->l);
        }
        if (temp->r != NULL) {
            if (temp->r->item == x) {
                link returnLink = temp->r;
                temp->r = NULL;
                return returnLink;
            }
            q.put(temp->r);
        }
    }
    return 0;
}

相关内容

最新更新

热门标签：