使用恒定空间和O（n）运行时间编写二叉search树的非recursion遍历
这不是作业，这是面试的问题。
这里的问题是algorithm应该是恒定的空间。 对于如何在没有堆栈的情况下这样做，我是非常无能的，我会发布我使用堆栈写的东西，但是无论如何它都不相关。
以下是我所尝试的：我试图做一个前序遍历，并且到达了最左边的节点，但是我被困在那里。 我不知道如何在没有堆栈/父指针的情况下进行“recursion”备份。
任何帮助，将不胜感激。
（我把它标记为Java，因为这是我很舒服使用，但它是很明显的语言不可知论）。
我并没有完全想到，但是我认为只要你愿意在这个过程中搞砸你的树，
每个节点有2个指针，所以它可以用来表示一个双向链表。 假设你从根前进到Root.Left = Current。 现在Root.Left指针是无用的，因此将其指定为Current.Right并继续到Current.Left。 当你到达最左边的孩子的时候，你会有一个链表，树上挂着一些节点。 现在重复这个过程，为你遇到的每一棵树重复这个过程
编辑：认为它通过。 以下是按顺序打印的algorithm：
void traverse (Node root) { traverse (root.left, root); } void traverse (Node current, Node parent) { while (current != null) { if (parent != null) { parent.left = current.right; current.right = parent; } if (current.left != null) { parent = current; current = current.left; } else { print(current); current = current.right; parent = null; } } } Morris Inorder树遍历怎么样？ 它基于线程树的概念，它修改树，但是当它完成时将其还原。
Linkie： http ://geeksforgeeks.org/?p=6358
不使用任何额外的空间。
如果您使用的是基于树的向下指针，并且没有父指针或其他内存，则不可能在常量空间中遍历。
如果你的二叉树是在一个数组中，而不是基于指针的对象结构。 但是，你可以直接访问任何节点。 这是一种作弊;-)
这是iluxa 最初的答案 。 它以完全相同的顺序运行完全相同的节点操作和打印步骤 – 但以简化的方式[1]：
void traverse (Node n) { while (n) { Node next = n.left; if (next) { n.left = next.right; next.right = n; n = next; } else { print(n); n = n.right; } } }
[1]另外，它甚至在树根节点没有离开孩子的时候工作。
这是一个search树，所以你总是可以得到下一个键/条目
你需要像（我没有testing代码，但它是如此简单）
java.util.NavigableMap<K, V> map=... for (Entry<K, V> e = map.firstEntry(); e!=null; e = map.higherEntry(e.getKey())) { process(e) }
为了清楚起见，这是higherEntry ，所以它不是recursion的。 你有它 ：）
final Entry<K,V> getHigherEntry(K key) { Entry<K,V> p = root; while (p != null) { int cmp = compare(key, p.key); if (cmp < 0) { if (p.left != null) p = p.left; else return p; } else { if (p.right != null) { p = p.right; } else { Entry<K,V> parent = p.parent; Entry<K,V> ch = p; while (parent != null && ch == parent.right) { ch = parent; parent = parent.parent; } return parent; } } } return null; }
问题的标题没有提到节点中缺less“父”指针。 尽pipeBST并不一定需要，但许多二叉树实现都有父指针。 class Node {Node * left; 节点*权利; 节点*父节点; DATA数据; };
在这种情况下，在纸上绘制树图，然后用铅笔在树的周围绘制，从边缘的两侧上下移动（当向下时，您将被留在边缘，上去的时候，你会在右边）。 基本上有4个州：
- 西南：你在左边，从父母的左边孩子
- 东北：从一个左小孩，回到其父母
- 东南亚：从父母到正确的孩子
- 西北：从一个正确的孩子，回到其父母
Traverse( Node* node ) { enum DIRECTION {SW, NE, SE, NW}; DIRECTION direction=SW; while( node ) { // first, output the node data, if I'm on my way down: if( direction==SE or direction==SW ) { out_stream << node->data; } switch( direction ) { case SW: if( node->left ) { // if we have a left child, keep going down left node = node->left; } else if( node->right ) { // we don't have a left child, go right node = node->right; DIRECTION = SE; } else { // no children, go up. DIRECTION = NE; } break; case SE: if( node->left ) { DIRECTION = SW; node = node->left; } else if( node->right ) { node = node->right; } else { DIRECTION = NW; } break; case NE: if( node->right ) { // take a u-turn back to the right node node = node->right; DIRECTION = SE; } else { node = node->parent; } break; case NW: node = node->parent; break; } } }
接受的答案需要进行以下更改，否则将不打印BST只有一个节点的树
if (current == NULL && root != NULL) print(root);
上面的iluxa的答案小小的特例
if(current== null) { current = root; parent = current.Right; if(parent != null) { current.Right = parent.Left; parent.Left = current; } }
这是一个二叉search树，所以每个节点都可以通过一系列的右/左判断来达到。 描述该系列为0/1，最不重要的位至最重要的位。 所以函数f（0）的意思是“通过取右手分支find的节点，直到find一个叶子; f（1）意味着采取一个左边，其余的权利; f（2） – 即二元010 – – 意味着取右边，然后左边，然后维权，直到find一片叶子，从n = 0开始迭代f（n），直到你击中了每一片叶子，效率不高（因为你必须从树顶开始时间），但不断的记忆和线性时间。
我们可以在不修改树本身的情况下遍历二叉树（提供的节点具有父指针）。 它可以在恒定的空间内完成。 我发现这个有用的链接相同http://tech.technoflirt.com/2011/03/04/non-recursive-tree-traversal-in-on-using-constant-space/
