谁能给我一个解决方案,在不递归和不使用堆栈的情况下按顺序遍历二叉树?
问问题
2503 次
6 回答
4
第二次编辑:我认为这是正确的。除了通常的 node.left_child 和 node.right_child 之外,还需要 node.isRoot、node.isLeftChild 和 node.parent。
state = "from_parent"
current_node = root
while (!done)
switch (state)
case "from_parent":
if current_node.left_child.exists
current_node = current_node.left_child
state = "from_parent"
else
state = "return_from_left_child"
case "return_from_left_child"
if current_node.right_child.exists
current_node = current_node.right_child
state = "from_parent"
else
state = "return_from_right_child"
case "return_from_right_child"
if current_node.isRoot
done = true
else
if current_node.isLeftChild
state = "return_from_left_child"
else
state = "return_from_right_child"
current_node = current_node.parent
于 2010-04-07T19:01:36.030 回答
1
1.双线程树
如果你的树节点有父引用/指针,那么在遍历期间跟踪你来自哪个节点,这样你就可以决定下一步去哪里。
在 Python 中:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
self.parent = None
if self.left:
self.left.parent = self
if self.right:
self.right.parent = self
def inorder(self):
cur = self
pre = None
nex = None
while cur:
if cur.right and pre == cur.right:
nex = cur.parent
elif not cur.left or pre == cur.left:
yield cur.value # visit!
nex = cur.right or cur.parent
else:
nex = cur.left
pre = cur
cur = nex
root = Node(1,
Node(2, Node(4), Node(5)),
Node(3)
)
print([value for value in root.inorder()]) # [4, 2, 5, 1, 3]
2.单线程树
如果您的树节点没有父引用/指针,那么您可以执行所谓的 Morris 遍历,它会暂时改变树,使right
没有右子节点的属性 - 临时指向它的中序继任者节点:
在 Python 中:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder(self):
cur = self
while cur:
if cur.left:
pre = cur.left
while pre.right:
if pre.right is cur:
# We detect our mutation. So we finished
# the left subtree traversal.
pre.right = None
break
pre = pre.right
else: # prev.right is None
# Mutate this node, so it links to curr
pre.right = cur
cur = cur.left
continue
yield cur.value
cur = cur.right
root = Node(1,
Node(2, Node(4), Node(5)),
Node(3)
)
print([value for value in root.inorder()])
于 2021-04-05T16:19:42.557 回答
0
是的你可以。为了做到这一点,你需要一个父指针来提升树。
于 2010-10-28T22:43:14.367 回答
0
从 tree_first() 开始,继续 tree_next() 直到获得 NULL。完整代码:https ://github.com/virtan/tree_closest
struct node {
int value;
node *left;
node *right;
node *parent;
};
node *tree_first(node *root) {
while(root && root->left)
root = root->left;
return root;
}
node *tree_next(node *p) {
if(p->right)
return tree_first(p->right);
while(p->parent) {
if(!p->parent->right || p->parent->right != p)
return p->parent;
else p = p->parent;
}
return 0;
}
于 2014-01-24T22:40:05.360 回答
-1
正如这里有人已经说过的那样,这是可能的,但不是没有父指针。如果需要,父指针基本上允许您遍历“路径”,因此可以打印出节点。但是为什么递归在没有父指针的情况下工作?好吧,如果您了解递归,它会像这样(想象一下递归堆栈):
recursion //going into
recursion
recursion
recursion
recursion //going back up
recursion
recursion
recursion
因此,当递归结束时,您以相反的顺序打印了二叉树的选定侧。
于 2012-06-25T13:06:43.900 回答