将一个二叉搜索树存到磁盘文件上

赵云30 发布于 2017/01/18 20:20
阅读 556
收藏 1
#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>
struct  DNode{
    T   key;
    U   value;
    int left;
    int 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);
        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);
    public:
        BST():root(NULL){}        
        ~BST();
        void Insert(T t, U u);
        void Find(T t);
        int Traver();
        void Delete(T t);
        void Write_To_Disk();
};

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

/*
 * 返回值表示Node节点对应的DNode离文件末尾有m个偏移量,也就是说右子树有m个节点。
 */
template <class T, class U>
int BST<T, U>::WriteNode(class Node<T, U> *node)()
{
    if (node == NULL)
        return 0;

    int m = WriteNode(node->left);

    class DNode 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 = 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 BST<T, U>::Write_To_Disk()
{
    WriteNode(root);
}

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();
*/
    /*
    class BST<string, int> bst;
    bst.Insert("hello", 12);
    bst.Insert("zhangfei", 14);
    bst.Insert("liubei", 14);
    bst.Traver(); */

    return 0;
}




加载中
1
梅开源
梅开源
第一反应是序列化反序列化
0
中山野鬼
中山野鬼
你说的方法没有问题。哈。其实没必要用地址方式存储链结构。而是(区域块的)基地址加偏移量的方式。这种方式占用内存少(64位系统),且容易成块的复制到磁盘上。
0
m
magiclogy

可以考虑二叉树中序遍历结果写入文件,这个时候文件里的每个数据是有序的;

读取的时候重建二叉排序树,尽量保证二叉树平衡即可。

不过这种方法重新得到的排序树和原来不一样。。。

0
赵云30
赵云30

能写到磁盘我是相信的,但是自己编程功力不够,实际写代码时不知道怎么写。注释掉的Write_ro_disk本来是准备用来写道磁盘的。

有没有高手写一个我瞻仰瞻仰。

0
bobdog1986
bobdog1986
试试序列化和反序列化行么?
0
赵云30
赵云30

引用来自“bobdog1986”的评论

试试序列化和反序列化行么?
什么是序列化和反序列化?
bobdog1986
bobdog1986
回复@长工 : 序列化就是把内存中数据格式化到硬盘,反序列化就是反过来。不同语言都有序列化的方法,google或stackoverflow搜一下C++ serialize,或者百度一下C++ 序列化,都有例子的。
返回顶部
顶部