这段析构函数错在哪里?

赵云30 发布于 2017/01/18 13:36
阅读 115
收藏 0
template <class T, class U>
BST<T, U>::~BST()
{
    DeleteNode(root);
}

如果将上述代码片段中的DeleteNode(root);注释掉程序正确,否则不能编译不能通过,程序提示不能链接到DeleteNode函数,我这段代码的用途是递归回收对象,防止内存泄露。

请问哪错了,怎么改?整个程序如下:


#include <iostream>

using namespace std;

template <class T, class U>
struct  Node{
    T   key;
    U   value;
    struct Node * left;
    struct Node * right;
};

template <class T, class U>
class BST {
    private:
        class Node<T, U> * root;
        // node前面的&不能少,否则程序错误。
        void InsertNode(class Node<T, U> *&node, T t, U u);
        class Node<T, U> * FindKey(class Node<T, U> *node, T t);
        void TraverTree(class Node<T, U> *node);
        void DeleteNode(class Node<T, U> *node);
        // node前面的&不能少,否则程序错误。
        void DeleteNode(class Node<T, U> *&node, T t);
    public:
        BST():root(NULL){}        
        ~BST();
        void Insert(T t, U u);
        void Find(T t);
        void Traver();
        void Delete(T t);
};

template <class T, class U>
void DeleteNode(class Node<T, U> *node)
{
    if (node->left) {
        DeleteNode(node->left);
    }
    if (node->right) {
        DeleteNode(node->right);
    }
    if (node) {
        delete node;
    }
}

template <class T, class U>
BST<T, U>::~BST()
{
    DeleteNode(root);
}

template <class T, class U>
void BST<T, U>::InsertNode(class Node<T, U> *&node, T t, U u)
{
    if (node == NULL) {
        //父节点指向新建子节点
        node = new Node<T, U>();
        node->key = t;
        node->value = u;
        return;
    }

    if (node->key > t) {
        InsertNode(node->left, t, u);
    }

    if (node->key < t) {
        InsertNode(node->right, t, u);
    }

    if (node->key == t) {
        node->value = u;
        cout << "key " << t << " modified to " << u << '\n';
    }
}

template <class T, class U>
void BST<T, U>::Insert(T t, U u) {
    InsertNode(root, t, u);
}

template <class T, class U>
class Node<T, U> * BST<T, U>::FindKey(class Node<T, U> *node, T t)
{
    if (node == NULL) {
        return NULL;
    }

    if (t < node->key) {
        cout << t << " < " << node->key <<'\n';
        FindKey(node->left, t);
    } else if (t > node->key) {
        cout << t << " > " << node->key <<'\n';
        FindKey(node->right, t);
    } else if (t == node->key) {
        cout << t << " == " << node->key <<'\n';
        cout << node << '\n';
        return node;
    }
}

template <class T, class U>
void BST<T, U>::Find(T t)
{
    class Node<T, U> *temp;
    temp = FindKey(root, t);
    if (temp) {
        cout << "Find key " << t << " value is" << temp->value << '\n';
    } else {
        cout << "Not find key "  << t << '\n';
    }
}

template <class T, class U>
void BST<T, U>::TraverTree(class Node<T, U> *node)
{
    if (node == NULL) {
        return;
    }
    TraverTree(node->left);
    cout << "key is" << node->key << " value is" << node->value << '\n';
    TraverTree(node->right);
}

template <class T, class U>
void BST<T, U>::Traver()
{
    TraverTree(root);
}

template <class T, class U>
void BST<T, U>::DeleteNode(class Node<T, U> *&node, T t)
{
    if (node == NULL) {
        return;
    }

    if (node->key > t) {
        DeleteNode(node->left, t);
    }

    if (node->key < t ) {
        DeleteNode(node->right, t);
    }

    if (node->key == t) {
        if (node->left && node->right) {
            class Node<T, U> * temp = node->right;
            while (temp->left != NULL) {
                temp = temp->left;
            }
            node->key = temp->key;
            node->value = temp->value;
            DeleteNode(node->right, temp->key);
        } else {
            class Node<T, U> * temp = node;
            if (node->left == NULL) {
                node = node->right;
            } else if (node->right == NULL) {
                node = node->left;
            }
            delete(temp);
        }
    }
}

template <class T, class U>
void BST<T, U>::Delete(T t)
{
    DeleteNode(root, t);
}

int main(int argc, char *argv[])
{
    class BST<int, int> bst;

    bst.Insert(13, 132);
    bst.Insert(16, 152);
    bst.Insert(12, 122);
    bst.Insert(14, 192);
    bst.Insert(16, 133);
    bst.Insert(15, 125);

    bst.Find(12);
    bst.Find(123);

    bst.Traver();
    bst.Delete(16);
    cout << "Hello World!" << endl;
    bst.Traver();

    return 0;
}



加载中
1
vaptu
vaptu

改正后的代码,已经编译链接运行成功。

具体原因看注释的代码:

https://www.bytelang.com/o/s/c/GZ2Xwj_5^8g=


运行结果:

key 16 modified to 133
12 < 13
12 == 12
0x11d2050
Find key 12 value is122
123 > 13
123 > 16
Not find key 123
key is12 value is122
key is13 value is132
key is14 value is192
key is15 value is125
key is16 value is133
Hello World!
key is12 value is122
key is13 value is132
key is14 value is192
key is15 value is125

返回顶部
顶部