Узлы дерева ссылок на каждом уровне - PullRequest
Новая
       14

Узлы дерева ссылок на каждом уровне

4 голосов
/ 02 февраля 2010

Учитывая бинарное дерево, как бы вы соединяли узлы на каждом уровне, слева направо. Скажем, на третьем уровне 5 узлов, свяжите их все слева направо.

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

Спасибо

Ответы [ 9 ]

5 голосов
/ 14 октября 2012

Идея есть:
1. Траверс по дереву с BFS.
2. Когда вы выполняете обход, вы связываете узлы на следующем уровне - если узел имеет левый и правый узлы, вы будете связывать слева направо. Если узел имеет следующий узел, то вы связываете самый правый дочерний элемент текущего узла с крайним левым дочерним элементом следующего узла. 

    public void BreadthFirstSearch(Action<Node> currentNodeAction)
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);

        while (q.Count != 0)
        {
            Node current = q.Dequeue();

            if (currentNodeAction != null)
                currentNodeAction(current);

            if (current.left != null) q.Enqueue(current.left);
            if (current.right != null) q.Enqueue(current.right);
        }
    }

    private void Linker(Node node)
    {
        Link(node.left, node.right);

        if (node.next != null)
            Link(node.right ?? node.left, node.next.left ?? node.next.right);
    }

    private void Link(Node node1, Node node2)
    {
        if (node1 != null && node2 != null)
            node1.next = node2;
    }

    public void LinkSameLevel()
    {
        BreadthFirstSearch(Linker);
    }
4 голосов
/ 02 февраля 2010

Создать вектор связанных списков. Выполните DFS, отслеживая свой уровень, и для каждого найденного узла добавьте его в связанный список уровня. Это будет работать в O (n), что является оптимальным.

Это то, что вы хотите сделать?

2 голосов
/ 02 февраля 2010

Это не прямой ответ на вопрос и может не применяться в зависимости от вашей ситуации.Но если у вас есть контроль над созданием и обслуживанием бинарного дерева, вероятно, было бы более эффективно поддерживать ссылки при построении / обновлении дерева.

Если бы вы держали и левый, и правый указатели на каждом уровне, то было бы «просто» (всегда легко сказать это слово, когда кто-то другой выполняет работу), чтобы поддерживать их.При вставке нового узла на заданном уровне вы знаете его непосредственных братьев и сестер из информации родительского узла.Вы можете настроить левый и правый указатели для трех задействованных узлов (если предположить, что они не на краю дерева).Аналогично, при удалении узла просто обновите левый и правый указатели родственных элементов удаляемого узла.Поменяйте их так, чтобы они указывали друг на друга.

1 голос
/ 02 февраля 2010

Я согласен с ответом Томаса Але, если вы хотите составить все списки строк одновременно. Похоже, вы заинтересованы в создании списка только для одной конкретной строки.

Допустим, у вас есть гигантское дерево, но вы хотите связать только 5-й ряд. Очевидно, что нет никакого смысла в доступе к любому узлу ниже 5-го ряда. Так что просто сделайте DFS с досрочным прекращением. К сожалению, вам все еще нужно пройти через всех предков каждого узла в списке.

Но вот хорошие новости. Если у вас есть идеальное двоичное дерево (где каждый отдельный узел разветвляется ровно дважды, кроме последней строки), то в первой строке будет 1 один, второй 2, третий 4, четвертый 8 и пятый 16. Таким образом, есть еще узлов в последнем ряду (16), чем все предыдущие вместе взятые (1 + 2 + 4 + 8 = 15), поэтому поиск по всем предкам по-прежнему просто O (n), где n - количество узлов в строки.

С другой стороны, в худшем случае пятая строка состоит из одного узла с полным двоичным деревом над ним. Тогда вам все равно придется поискать всех 15 предков, чтобы поместить этот один узел в список.

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

0 голосов
/ 07 октября 2018

Сохранять массив глубин при поиске в ширину. 

    vector<forward_list<index_t>> level_link(MAX_NODES);
    index_t fringe_depth = 0;
    static index_t depth[MAX_NODES];
    memset(depth,0,sizeof(depth));
    depth[0] = 0;

Теперь, когда глубина изменяется во время удаления из очереди, вы получаете все связи! 

    explored[0] = true;
    static deque<index_t> fringe;
    fringe.clear();
    fringe.push_back(0); // start bfs from node 0
    while(!fringe.empty()) {
        index_t xindex = fringe.front();
        fringe.pop_front();
        if(fringe_depth < depth[xindex]) {
            // play with prev-level-data
            fringe_depth = depth[xindex];
        }

Теперь у нас есть глубина края, поэтому мы можем связать уровни. 

        level_link[fringe_depth].push_front(xindex);

        for(auto yindex : nodes[xindex].connected) {
            if(explored[yindex])
                continue;
            explored[yindex] = true;
            depth[yindex] = depth[xindex] + 1;
            fringe.push_back(yindex);
        }
    }
0 голосов
/ 10 февраля 2016 
    private class Node
    {
        public readonly Node Left;
        public readonly Node Right;
        public Node Link { get; private set; }

        public void Run()
        {
            LinkNext = null;
        }

        private Node LinkNext
        {
            get
            {
                return Link == null ? null : (Link.Left ?? Link.Right ?? Link.LinkNext);
            }
            set
            {
                Link = value;
                if (Right != null)
                    Right.LinkNext = LinkNext;
                if (Left != null)
                    Left.LinkNext = Right ?? LinkNext;
            }
        }
    }
0 голосов
/ 29 марта 2015

Для решения этой проблемы могут использоваться разные подходы. Вот некоторые из них, которые приходят на ум: -

1) Использование обхода порядка уровней или BFS.
Мы можем изменить записи очереди, чтобы они содержали уровень узлов. Таким образом, узел очереди будет содержать указатель на узел дерева и целочисленный уровень. Когда мы снимаем узел с узла, мы можем проверить уровень удаленного узла, если он один и тот же, мы можем установить правильный указатель, указывающий на него.
Временная сложность для этого метода будет O (n).

2) Если у нас есть полное бинарное дерево, мы можем расширить обход Pre-Order. В этом методе мы установим правый указатель родителя перед потомками.
Временная сложность для этого метода будет O (n).

3) В случае неполного двоичного дерева мы можем изменить метод (2), пройдя сначала корень, затем правый указатель и затем левый, чтобы мы могли убедиться, что все узлы на уровне i имеют установленный правый указатель до уровня i + 1 узел. Временная сложность для этого метода будет O (n ^ 2).

0 голосов
/ 16 января 2013

Что я обычно делаю, чтобы решить эту проблему, так это то, что я делаю простой обход по порядку.

Я инициализирую свое дерево конструктором, который присваивает значение уровня или столбца каждому узлу. Следовательно, моя голова на уровне 0. 

public Node(int d)
{
head=this;
data=d;
left=null;
right=null;
level=0;
}

Теперь, если в обходе я беру налево или направо, я просто делаю обход с помощью индикатора уровня. Для каждого идентификатора уровня я создаю связанный список, возможно, в векторе узлов.

0 голосов
/ 24 марта 2012 
#include <queue>

struct Node {
    Node *left;
    Node *right;
    Node *next;
};

/** Link all nodes of the same level in a binary tree. */
void link_level_nodes(Node *pRoot)
{
    queue<Node*> q;
    Node *prev;     // Pointer to the revious node of the current level
    Node *node;
    int cnt;        // Count of the nodes in the current level
    int cntnext;    // Count of the nodes in the next level

    if(NULL == pRoot)
        return;

    q.push(pRoot);
    cnt = 1;
    cntnext = 0;
    prev = NULL;

    while (!q.empty()) {
        node = q.front();
        q.pop();

        /* Add the left and the right nodes of the current node to the queue
           and increment the counter of nodes at the next level. 
        */
        if (node->left){
            q.push(node->left);
            cntnext++;
        }
        if (node->right){
            q.push(node->right);
            cntnext++;
        }

        /* Link the previous node of the current level to this node */
        if (prev)
            prev->next = node;

        /* Se the previous node to the current */
        prev = node;

        cnt--;
        if (0 == cnt) { // if this is the last node of the current level
            cnt = cntnext;
            cntnext = 0;
            prev = NULL;
        }
    }
}
...