这段代码哪里错了?

赵云30 发布于 2017/01/22 12:06
阅读 109
收藏 0

如下代码片段,将注释去掉出现一大堆编译错误,不知道怎么改。

    if (node->key > t) {
        InsertNode(node->left, t, u);
        if (node->left->height - node->right->height == 2) {
           if (t < node->left->key) {
               //RotateWithLeftChild(node);
           } else {
               //DoubleWithLeftChild(node);
           }
        }
    }

    if (node->key < t) {
        InsertNode(node->right, t, u);
        if (node->right->height - node->left->height == 2) {
           if (t > node->right->key) {
               //RotateWithRightChild(node);
           } else {
               //DoubleWithRightChild(node);
           }
        }
    }

 

整个程序如下,其中RotateWithLeftChild(node)等四个注释掉的函数暂时没有实现,先空在那里。:

#include <iostream>

using namespace std;

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

template <class T, class U>
struct  DNode{
    T   key;
    U   value;
    int left;
    int right;
    int height;
};

template <class T, class U>
class AVL {
    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);
        int TraverTree(class Node<T, U> *node);
        void DeleteNode(class Node<T, U> *node);
        // node前面的&不能少,否则程序错误。
        void DeleteNode(class Node<T, U> *&node, T t);
        int WriteNode(class Node<T, U> *node);
        void RotateWithLeftChild(class Node<T, U> * &k2);
        void RotateWithRightChild(class Node<T, U> * &k2);
        void DoubleWithLeftChild(class Node<T, U> * &k2);
        void DoubleWithRightChild(class Node<T, U> * &k2);
    public:
        AVL():root(NULL){}
        ~AVL();
        void Insert(T t, U u);
        void Find(T t);
        int Traver();
        void Delete(T t);
        void Write();
};

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>
AVL<T, U>::~AVL()
{
    //看这里!!!!!!! 这是同名覆盖原则, 使用域标志:: 。这种写法在MFC中尤其常见。
    //例如在mfc中调用库中没有封装的api就会这么写 ::SendMessage(...);
    ::DeleteNode(root);
}

template <class T, class U>
void AVL<T, U>::RotateWithLeftChild(class Node<T, U> *&k2)
{
     class Node<T, U> *k1 = k2->left;
     k2->left = k1->right;
     k1->right = k2;
     k2->height = max(k2->left->height, k2->right->height) + 1;
     k1->height = max(k1->left->height, k2->height ) + 1;
     k2 = k1;
}

template <class T, class U>
void AVL<T, U>::RotateWithRightChild(class Node<T, U> *&k2)
{
    return;
}

template <class T, class U>
void AVL<T, U>::DoubleWithLeftChild(class Node<T, U> *&k2)
{
    return;
}

template <class T, class U>
void AVL<T, U>::DoubleWithRightChild(class Node<T, U> *&k2)
{
    return;
}

template <class T, class U>
void AVL<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->left->height - node->right->height == 2) {
           if (t < node->left->key) {
               //RotateWithLeftChild(node);
           } else {
               //DoubleWithLeftChild(node);
           }
        }
    }

    if (node->key < t) {
        InsertNode(node->right, t, u);
        if (node->right->height - node->left->height == 2) {
           if (t > node->right->key) {
               //RotateWithRightChild(node);
           } else {
               //DoubleWithRightChild(node);
           }
        }
    }

    if (node->key == t) {
        node->value = u;
        cout << "key " << t << " modified to " << u << '\n';
    }
    node->height = max(node->left->height, node->right->height) + 1;
}

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

template <class T, class U>
class Node<T, U> * AVL<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 AVL<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>
int AVL<T, U>::TraverTree(class Node<T, U> *node)
{
    if (node == NULL) {
        return 0;
    }
    int m = TraverTree(node->left);
    cout << "key is " << node->key << " value is " << node->value << '\n';
    int n = TraverTree(node->right);
    return m + n + 1;
}

template <class T, class U>
int AVL<T, U>::Traver()
{
    return TraverTree(root);
}

template <class T, class U>
void AVL<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 AVL<T, U>::Delete(T t)
{
    DeleteNode(root, t);
}

/*
 * 返回值表示右子树有n个节点
 */
template <class T, class U>
int AVL<T, U>::WriteNode(class Node<T, U> *node)
{
    if (node == NULL)
        return 0;

    int m = WriteNode(node->left);

    class DNode<T, U> dnode;
    dnode.key = node->key;
    dnode.value = node->value;
    if (node->left == NULL)
        dnode.left = 0;
    else
        dnode.left = -m - 1;
    if (node->right ==NULL)
        dnode.right = 0;
    else
        dnode.right = TraverTree(node->right->left) + 1;

    cout << "key " << dnode.key << " value " << dnode.value << " left " << dnode.left << " right " << dnode.right << '\n';

    WriteNode(node->right);

    return TraverTree(node->right);
}

template <class T, class U>
void AVL<T, U>::Write()
{
    WriteNode(root);
}

int main(int argc, char *argv[])
{

    class AVL<int, int> avl;

    avl.Insert(20, 21);
    avl.Insert(13, 32);
    avl.Insert(16, 12);
    avl.Insert(12, 2);
    avl.Insert(14, 12);
    avl.Insert(16, 13);
    avl.Insert(15, 15);
    avl.Insert(11, 15);
    avl.Insert(9, 15);
    avl.Insert(10, 5);
    avl.Insert(17, 6);

    avl.Find(12);
    avl.Find(123);

    avl.Write();

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

    /*
    class AVL<string, int> AVL;
    AVL.Insert("hello", 12);
    AVL.Insert("zhangfei", 14);
    AVL.Insert("liubei", 14);
    AVL.Traver(); */

    return 0;
}

 

加载中
返回顶部
顶部