修改深度第一次遍历树

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

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

对于’hacky’解决方案，您可以使用指针通常为4字节对齐（即最后两位为0）的事实，并将这两位用作访问标志。

Answer 3

这是我对二叉树的命题。 语言是C＃。 它是一个包含int的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; } } } 

如果它不是二叉树，那么事情当然会变得更复杂，但逻辑是相似的。 到每个级别的第一个可能的孩子的叶子。 一旦你到达一片叶子，你就会上去。 每当你抬头看看父母时，你都会检查你应该来自的孩子是否是父母列表中的最后一个。 如果没有，你带下一个孩子，再次下来。 如果是，您上去查看以下父母。 如果你回到root，你搜索了整棵树。

编辑

好的搜索和遍历是不同的事情，我的不好。 以下是一些经过修改的遍历代码

预购：

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

后序：

 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 4

如果您有父指针，那么您可以在没有堆栈的情况下展开树。 放松期间唯一的另一个问题是“我是否需要访问另一个孩子？” 如果您刚刚从左子项或右子项返回（或概括为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; } 

Answer 5

这显示了我是如何用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; } } }