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

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

РЕДАКТИРОВАТЬ

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

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;
}

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

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

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;
        }
    }
}

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

РЕДАКТИРОВАТЬ

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

preorder:

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);
            }
        }
    }
}

inorder:

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;
        }
    }
}

Это показывает, как я бы сделал это в 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;
        }
    }
}