这不是作业，这是一道面试题。
这里的问题是算法应该是常数空间。我对如何在没有堆栈的情况下执行此操作一无所知，我会发布我使用堆栈编写的内容，但无论如何它都不相关。
这是我尝试过的：我尝试进行预订遍历，然后到达了最左边的节点，但我被困在那里。我不知道如何在没有堆栈/父指针的情况下“递归”备份。
任何帮助，将不胜感激。
（我将其标记为 Java，因为这是我很喜欢使用的，但显然它与语言无关。）
问问题
41401 次
10 回答
30
我没有完全考虑清楚，但我认为只要你愿意在这个过程中搞砸你的树，这是可能的。
每个 Node 都有 2 个指针，所以它可以用来表示一个双向链表。假设您从 Root 前进到 Root.Left=Current。现在 Root.Left 指针没用了，因此将其分配为 Current.Right 并继续执行 Current.Left。当您到达最左边的孩子时，您将拥有一个链接列表，其中的树挂在一些节点上。现在迭代它，为你遇到的每一棵树重复这个过程
编辑：想通了。这是按顺序打印的算法：
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;
}
}
}
于 2011-03-31T07:31:26.640 回答
29
于 2011-03-31T15:41:47.873 回答
4
如果您使用的是基于向下指针的树并且没有父指针或其他内存，则不可能在常量空间中遍历。
如果您的二叉树位于数组中而不是基于指针的对象结构中，则这是可能的。但是您可以直接访问任何节点。这是一种作弊;-)
于 2011-03-31T07:28:31.810 回答
3
这是 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] 另外，它甚至可以在树根节点没有左子节点的情况下工作。
于 2014-11-30T12:57:34.440 回答
0
这是一个搜索树，所以你总是可以得到下一个键/条目
你需要类似的东西（我没有测试代码，但它很简单）
java.util.NavigableMap<K, V> map=...
for (Entry<K, V> e = map.firstEntry(); e!=null; e = map.higherEntry(e.getKey())) {
process(e)
}
为了清楚起见，这是higherEntry，所以它不是递归的。你有它 ：）
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;
}
于 2011-03-31T07:41:44.907 回答
0
问题的标题没有提到节点中缺少“父”指针。尽管 BST 不一定需要它，但许多二叉树实现确实具有父指针。类节点{节点*左；节点* 对；节点*父；数据数据；};
就是这种情况，在纸上画出树的图，然后用铅笔在树周围画，从边缘的两侧向上和向下（向下时，你会在边缘的左侧，并且上升时，您将在右侧）。基本上有4种状态：
- SouthWest：你在边缘的左侧，从父节点到左子节点
- NorthEast：从一个左孩子开始，回到它的父母
- 东南部：从父母到正确的孩子
- 西北：从一个正确的孩子，回到它的父母
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;
}
}
}
于 2011-03-31T08:58:07.700 回答
0
我们可以在不修改树本身的情况下遍历二叉树（假设节点具有父指针）。它可以在恒定空间中完成。我发现这个有用的链接用于相同的 http://tech.technoflirt.com/2011/03/04/non-recursive-tree-traversal-in-on-using-constant-space/
于 2011-09-23T21:33:22.240 回答
0
接受的答案需要进行以下更改，否则它将不会打印 BST 只有一个节点的树
if (current == NULL && root != NULL)
print(root);
于 2013-12-07T16:44:17.653 回答
0
上面 iluxa 答案的小特例
if(current== null)
{
current = root;
parent = current.Right;
if(parent != null)
{
current.Right = parent.Left;
parent.Left = current;
}
}
于 2016-02-27T01:21:38.463 回答
-1
它是一棵二叉搜索树，因此每个节点都可以通过一系列右/左决策到达。将该系列描述为 0/1，从最低有效位到最高有效位。所以函数f(0)的意思是“取右手分支找到的节点，直到找到叶子；f(1)意思是取一个左边，剩下的右边；f(2)——也就是二进制010—— - 表示向右，然后向左，然后向右，直到找到叶子。从 n = 0 开始迭代 f(n)，直到你击中每一个叶子。效率不高（因为你必须从每个树的顶部开始时间）但恒定的记忆和线性时间。
于 2011-03-31T07:27:41.897 回答