Создайте дерево avl, где каждый узел указывает на другое дерево avl - PullRequest
Новая
       41

Создайте дерево avl, где каждый узел указывает на другое дерево avl

0 голосов
/ 19 мая 2018

У меня есть следующий входной текстовый файл 

   id    element
    0    1
    0    3
    1    0
    1    1
    1    3
    2    2
    2    4
    3    4
    4    1

Я хочу организовать данные в дерево AVL.Моей первой мыслью было создать дерево идентификаторов AVL, а затем каждый из узлов идентификаторов в первом дереве будет содержать указатель на другое дерево AVL, где будут храниться элементы.

Затем я подумал, что смогу сделать этопутем создания AVL-дерева указателей на узлы, с которыми связан этот идентификатор.Это означает, что мне нужно добавить еще один указатель на узел к каждому узлу моего дерева.Этот дополнительный указатель будет связан с деревом, которое содержит узлы, содержащие указатели на узлы моего основного дерева, содержащего требуемый связанный идентификатор.

Ниже приведены мои методы для дерева AVL, где они работают нормально.В структуре avl_node_id я думал, что я добавлю указатель на корень другого дерева AVL.Однако я не знаю, как на самом деле реализовать все это. 

class AVLTree
{
    public:
        AVLTree();
        void readFile();
        void printToScreen();

        struct avl_node
        {
            int data;
            struct avl_node *left;
            struct avl_node *right;
        }*root;

        struct avl_node_id
        {
            struct avl_node **root;
            int data;
            struct avl_node *left;
            struct avl_node *right;
        }*id_root;

        int height(avl_node *);
        int diff(avl_node *);
        avl_node *rr_rotation(avl_node *);
        avl_node *ll_rotation(avl_node *);
        avl_node *lr_rotation(avl_node *);
        avl_node *rl_rotation(avl_node *);
        avl_node* balance(avl_node *);
        avl_node* insert(avl_node *, int );
        void display(avl_node *, int);
        void inorder(avl_node *);
    private:
        int n,m;
};

А вот код для чтения файла и вставки идентификаторов в исходное дерево 

void AVLTree::readFile()
{
    ifstream read("input2.txt");
    while(read>>n>>m){
        id_root = insert(id_root, n);
    }
}

AVLTree::avl_node *AVLTree::insert(avl_node *root, int value)
{
    if (root == NULL)
    {
        root = new avl_node;
        root->data = value;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    else if (value < root->data)
    {
        root->left = insert(root->left, value);
        root = balance (root);
    }
    else if (value > root->data)
    {
        root->right = insert(root->right, value);
        root = balance (root);
    }
    return root;
}
...