## 这段析构函数错在哪里？

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

```#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

```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```