измененная глубина первого обхода дерева

Question

Я получил этот вопрос в интервью с Amazon. Меня попросили выполнить первый обход дерева по глубине, без использования рекурсии или стека. Я мог бы использовать родительский указатель для каждого узла, как часть структуры, но ничего кроме этого (например, «посещаемая» переменная »или что-нибудь еще). Пожалуйста, предложите мне алгоритм.

Answer 1

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

Гадкий псевдокод:

cur = treeroot;
while (1) { // Get to bottom of tree
    if (cur.hasLeft) {
        cur = left;
    } else if (cur.hasRight) {
        cur = right;
    } else {
        break;
}

// cur is now the bottom node

while (1) {
    doStuff(cur); // output cur, perform op on it, whatever
    if (!cur.hasParent) { // Done with traversal
        break;
    }
    prev = cur; // So we can tell which way we came up to the parent.
    cur = cur.parent;
    if (cur.hasLeft && cur.left == prev) { // Delete left child; it's done
       cur.hasLeft = false;
    } else if (cur.hasRight && cur.right == prev) { // Delete right child; it's done
       // Note: "else" not desirable if a node should not be able to have the same child in two spots
       cur.hasRight = false;
    }
    if (cur.hasLeft) { // Go all the way to the bottom of the left child
        cur = cur.left;
        while (1) {
            if (cur.hasLeft) {
                cur = cur.left;
            } else if (cur.hasRight) {
                cur = cur.right;
            } else {
                break;
            }
        }
    } else if (cur.hasRight) { // Go all the way to the bottom of the right child
        cur = cur.right;
        while (1) {
            if (cur.hasLeft) {
                cur = cur.left;
            } else if (cur.hasRight) {
                cur = cur.right;
            } else {
                break;
            }
        }
    }
}

Answer 2

Вот мое предложение для двоичного дерева. Язык C #. Это частный метод класса binarTree, который содержит целые числа

private Node DFS(int value)
{
    Node current = this.root;
    if(current.data == value) return current;

    while(true)
    {
        //go down-left as far as possible
        while(current.leftChild != null)
        {
            current = current.leftChild;
            if(current.data == value) return current;
        }
        //leftChild is null, but maybe I can go right from here
        while(current.leftChild == null && current.rightChild != null)
        {
            current = current.rightChild;
            if(current.data == value) return current;
        }
        if(current.leftChild == null && current.rightChild == null)
        {
            // Ok, I got to a leaf. Now I have to get back to the last "crossroads"
            // I went down-left from, but there was also down-right option
            while(current.parent != null &&
                  (current == current.parent.rightChild ||
                   current.parent.rightChild == null))
            {
                current = current.parent;
            }
            if(current.parent == null) return null;

            // Ok If I'm here, that means I found the crossroads mentioned before
            // I'll go down-right once and then I should try down-left again
            current = current.parent.rightChild;
            if(current.data == value) return current;
        }
    }
}

Если это не двоичное дерево, то, конечно, все усложняется, но логика схожа. Спуститесь к листу, взяв первого возможного ребенка на каждом уровне. Как только вы достигнете листа, вы поднимаетесь. Каждый раз, когда вы смотрите на родителя, вы проверяете, был ли ребенок, от которого вы должны родиться, последним в списке родителей. Если нет, вы берете следующего ребенка и снова спускаетесь. Если да, вы идете и проверяете следующего родителя. Если вы вернетесь к корню, вы искали все дерево.

EDIT

Хорошо, поиск и обход - разные вещи, мой плохой. Вот некоторый модифицированный код для обходов

предзаказ:

public void preorderTraversal()
{
    Node current = this.root;
    Console.WriteLine(" item: {0} ", current.data);
    while(true)
    {
        while(current.leftChild != null)
        {
            current = current.leftChild;
            Console.WriteLine(" item: {0} ", current.data);
        }
        while(current.leftChild == null && current.rightChild != null)
        {
            current = current.rightChild;
            Console.WriteLine(" item: {0} ", current.data);
        }
        if(current.leftChild == null && current.rightChild == null)
        {
            while(current.parent != null &&
                  (current == current.parent.rightChild ||
                   current.parent.rightChild == null))
            {
                current = current.parent;
            }
            if(current.parent == null)
            {
                return;
            }
            else
            {
                current = current.parent.rightChild;
                Console.WriteLine(" item: {0} ", current.data);
            }
        }
    }
}

Симметричный:

public void inorderTraversal()
{
    Node current = this.root;
    while(true)
    {
        while(current.leftChild != null)
        {
            current = current.leftChild;
        }
        Console.WriteLine(" item: {0} ", current.data);
        while(current.leftChild == null && current.rightChild != null)
        {
            current = current.rightChild;
            Console.WriteLine(" item: {0} ", current.data);
        }
        if(current.leftChild == null && current.rightChild == null)
        {
            while(current.parent != null &&
                  (current == current.parent.rightChild ||
                   current.parent.rightChild == null))
            {
                    current = current.parent;
                    if(current.rightChild == null)
                    {
                        Console.WriteLine(" item: {0} ", current.data);
                    }
            }
            if(current.parent == null)
            {
                return;
            }
            else
            {
                Console.WriteLine(" item: {0} ", current.parent.data);
                current = current.parent.rightChild;
            }
        }
    }
}

postorder:

public void postorderTraversal()
{
    Node current = this.root;
    while(true)
    {
        while(true)
        {
            if(current.leftChild != null)
            {
                current = current.leftChild;
            }
            else if(current.rightChild != null)
            {
                current = current.rightChild;
            }
            else
            {
                break;
            }
        }
        while(current.parent != null &&
              (current == current.parent.rightChild ||
               current.parent.rightChild == null))
        {
            Console.WriteLine(" item: {0} ", current.data);
            current = current.parent;
        }
        Console.WriteLine(" item: {0} ", current.data);
        if(current.parent == null)
        {
            return;
        }
        else
        {
            current = current.parent.rightChild;
        }
    }
}

Answer 3

Для «хакерского» решения вы можете использовать тот факт, что указатели обычно выровнены на 4 байта (т. Е. Последние два бита равны 0) и использовать эти два бита в качестве вашего посещенного флага.

Answer 4

Это показывает, как я это сделаю в C. Он демонстрирует как обратный порядок, так и обратный порядок и обобщается для 0..N дочерних элементов каждого узла.

struct node {
    struct node *parent;
    struct node *child[NCHILD];
};

void dfs(struct node *head, void (*visit_preorder)(struct node *n), void (*visit_postorder)(struct node *n))
{
    struct node *current = head;
    struct node *prev = head;

    while (current)
    {
        int i;

        /* preorder traversal */
        if (prev == current->parent)
            visit_preorder(current);

        /* Find first child to visit */
        for (i = NCHILD; i > 0; i--)
        {
            if (prev == current->child[i - 1])
                break;
        }
        while (i < NCHILD && current->child[i] == NULL)
            i++;

        prev = current;

        if (i < NCHILD)
        {
            /* Descend to current->child[i] */
            current = current->child[i];
        }
        else
        {
            /* Postorder traversal */
            visit_postorder(current);

            /* Ascend back to parent */
            current = current->parent;
        }
    }
}

Answer 5

Если у вас есть родительский указатель, то вы можете раскрутить дерево без стека. Единственная другая проблема во время отдыха - "мне нужно навестить другого ребенка (детей)?" На это можно ответить, просто сравнив значения указателей, чтобы выяснить, вернулись ли вы только что от левого или правого потомка (или обобщить до N потомков).

EDIT

Псевдокод (не проверен):

p_last          = NULL;
p               = p_head;
descend         = true;

while (NULL != p)
{
    p_tmp = p;

    if (descend)
    {
        // ... Node processing here...

        if (0 == p->num_children)
        {
            // No children, so unwind
            p = p_parent;
            descend = false;
        }
        else
        {
            // Visit first child
            p = p->child[0];
        }
    }
    else
    {
        // Find the child we just visited
        for (i = 0; i < p->num_children; i++)
        {
            if (p_last == p->child[i])
            {
                break;
            }
        }
        if (i == num_children-1)
        {
            // Processed last child, so unwind
            p = p_parent;
        }
        else
        {
            // Visit next child
            p = p->p_child[i+1];
            descend = true;
        }
    }

    p_last = p_tmp;
}