修改深度首先遍历树 [英] modified depth first traversal of tree

问题描述

我在接受亚马逊采访时就得到了这个问题。
我被要求执行树的深度优先遍历，而不使用递归或堆栈。我可以使用每个节点的父指针作为结构的一部分，但除此之外没有别的（因为访问变量或任何东西）
请给我一个算法。 p>

解决方案

父指针实际上是你需要的，诀窍在于遍历它时消耗树。

Ugly伪代码：

  cur = treeroot; 
 while（1）{/ /获取到底部的
 if（cur.hasLeft）{
 cur = left; 
} else if（cur.hasRight）{
 cur = right; 
 } else {
 break; 
} 
 
 // cur现在是底层节点
 
 while（1）{
 doStuff（cur ）; //输出cur，执行操作，任何
 if（！cur.hasParent）{//完成遍历
 break; 
} 
 prev = cur; / /所以我们可以知道我们来到父母的方式
 cur = cur.parent; 
 if（cur.hasLeft&& cur.left == prev）{//删除左孩子完成
 cur.hasLeft = false; 
} else if（cur.hasRight&& cur.right == prev）{//删除右边的小孩;它已经完成
 //注意：else不可取，如果一个节点不应该有两个相同的孩子
 cur.hasRight = false; 
} 
 if（cur.hasLeft）{//一直到左边的孩子的底部
 cur = cur.left; 
 while（1）{
 if（cur.hasLeft）{
 cur = cur.left; 
} else if（cur.hasRight）{
 cur = cur.right; 
} else {
 break; 
} 
} 
} else if（cur.hasRight）{//一直到右边的孩子的底部
 cur = cur.right; 
 while（1）{
 if（cur.hasLeft）{
 cur = cur.left; 
} else if（cur.hasRight）{
 cur = cur.right; 
} else {
 break; 
} 
} 
} 
} 
  

I got this question in an interview with amazon. I was asked to perform a depth first traversal of a tree, without using recursion or stack. I could use a parent pointer for each node, as a part of the structure, but nothing else other than that.(for ex, a "visited" variable" or anything). Please suggest me an algorithm.

解决方案

The parent pointer is actually all you need. The trick is to consume the tree as you traverse it.

Ugly pseudocode:

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

这篇关于修改深度首先遍历树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！