Есть ли способ пройти через связанный список, где вместо normall указатели будут уникальными? - PullRequest
Новая
       15

Есть ли способ пройти через связанный список, где вместо normall указатели будут уникальными?

0 голосов
/ 25 марта 2019

Я пытаюсь написать двоичное дерево на c ++, связанный список в виде поддеревьев и уникальные указатели в качестве связей между этими списками. Все дерево разделено на две части: правую и левую. Есть два указателя, которые ссылаются на голову слева и справа. Тогда каждый лист в поддереве является структурой, в которой хранится следующая информация: 

class Leaf{
private:
    int * leaf_value; 
    int occupancy;
    std::unique_ptr<Leaf> NextLeaf;

public:
    explicit Leaf(int);
    void AppendLeaf(int,std::unique_ptr<Leaf>);

};

Leaf::Leaf(int size) {
    leaf_value = new int (size);
    NextLeaf = nullptr;
    occupancy = 0;
}

Где leaf_value - указатель на память, в которой будут храниться все числа на этом уровне (поскольку это двоичное дерево, мы можем знать точный размер (2 ^ current_level), который должен быть выделен для объектов). Таким образом, мы будем заполнять это свободное пространство числами, пока заполненность не станет меньше 2 ^ current_level. И после этого мы добавим новый, более глубокий уровень для следующего ряда элементов. Структура будет выглядеть так: 

               1
            /        \
         [2]         [ 3 ]
        /              \
   [4 , 5 ,6 ,7]  [8 , 9 , 10 , 11 ]

Где элементы в квадратных скобках - это отдельные листья. , Я подумал, что это может быть хорошей идеей, связать их все с уникальными указателями, потому что каждый узел списка ссылается только на следующий, так что на самом деле все указатели уникальны. Вот упрощенный код того, что я пытаюсь сделать. 


int main(){
     Node head;
     head.next = nullptr;
     int value;
     cin << value;
     AddNode(value , head); 
     return 0;
}

/*TreeHead - is another leaf structure that stores pointers to left and right branches 
struct SmartTree{
    int level;
    std::unique_ptr<Leaf> LeftChild = std::make_unique<Leaf>(1);
    std::unique_ptr<Leaf> RightChild = std::make_unique<Leaf>(1);

}
*/
void AddNode(int val , std::unique_ptr<SmartTree> TreeHead){
/*problem with implemantation of this part */
     Node * currentLeaf  = TreeHead;
     Node * previousLeaf = TreeHead;
     while(current != nullptr){
        previousLeaf = currentLeaf;
        currentLeaf = currentLeaf -> next ;
     }
     currentLeaf = new Leaf;
     previous -> next = currentLeaf;
     currentLeaf -> value = val; 
}

Но проблема в том, что я не могу найти правильный путь, чтобы пройти все наименьшее к нижнему из-за уникальности уникальных указателей. Я не уверен, что могу сделать это с помощью функции move(pointer), потому что как я понял, что функции работают, это предоставляет право владения от TreeHead до CurrentLeafe, сохраненная в нем ценность может быть потеряна. Итак, вопрос: Есть ли способ пройти через уникальные указатели или я должен использовать разные виды указателей для выполнения этой задачи? Большое спасибо!

1 Ответ

0 голосов
/ 26 марта 2019

Я немного изменил свои методы, изменив лист массива [ 1 2 3 ] на обычный.Это означает, что теперь каждый лист является объектом, который содержит один элемент, поэтому дерево теперь выглядит не так: 

                1
            /        \
         [2]         [ 3 ]
        /              \
   [4 , 5 ,6 ,7]  [8 , 9 , 10 , 11 ]

, а как: 

               1
           /       \
          2           3
        /    \      /  \ 
       5      6    7     8

Новая структура дерева: 

struct SmartTree {
    int value;
    int childrens;
    bool is_root = false;
    std::unique_ptr<SmartTree> LeftChild;
    std::unique_ptr<SmartTree> RightChild;
};

Но я уверен, что и предыдущий метод будет работать так же хорошо. Так что я обнаружил, что не без помощи хорошим решением в этом случае является рекурсия, а теперь функция, которая проходит по дереву и добавляет элемент вend выглядит так: 

std::unique_ptr <SmartTree> InsertLeftChild(std::unique_ptr<SmartTree> tree, std::unique_ptr<SmartTree> left_subtree){
    // left_subtree - node to insert
    tree -> childrens += 1;
    if (tree -> is_root and  tree -> LeftChild == nullptr) tree -> LeftChild = std::move(left_subtree);
    else if (tree -> is_root) tree -> LeftChild = InsertLeftChild(std::move(tree -> LeftChild) , move(left_subtree));
    else if (tree -> LeftChild == nullptr)tree -> LeftChild = std::move(left_subtree);
    else if (tree -> RightChild == nullptr) tree -> RightChild = std::move(left_subtree);
    else if (tree -> LeftChild -> childrens <= tree -> RightChild -> childrens) tree->LeftChild = InsertLeftChild(std::move(tree -> LeftChild) , std::move(left_subtree));
    else if (tree -> LeftChild -> childrens > tree -> RightChild -> childrens)  tree->RightChild = InsertLeftChild(std::move(tree -> RightChild) , std::move(left_subtree));
    return move(tree);
};

Этот текст написан только для вставки левых детей.Таким образом, первая и вторая if проверяет, является ли это корнем, и является ли эта корневая инициализация.Если у него есть дочерние элементы, то вызовите функцию InsertLeftChilld.Передача aruments, функция с перемещением уничтожит предыдущий указатель, поэтому с левой стороны я возвращаю права владения LeftChild: 

tree -> LeftChild = std::move(left_subtree);

else if (tree -> LeftChild == nullptr) проверяет, является ли это концом, и если это так - вставляет новый лист

else if (tree -> LeftChild -> childrens <= tree -> RightChild -> childrens) проверяет, куда вы должны направить свой лист дальше, если вы не можете его вставить. Надеюсь, этот метод поможет кому-то в будущем. Спасибо всем за ответы!

...