修改深度第一次遍历树

Question

我在接受亚马逊采访时得到了这个问题.我被要求执行树的深度优先遍历,而不使用递归或堆栈.我可以为每个节点使用父指针,作为结构的一部分,但除此之外别无其他.(例如,"访问"变量"或任何东西).请建议我一个算法.

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