问题描述
我有一个二进制树和内部节点组成'和'或'异'。叶节点也纷纷和数据成员。我需要用栈（非递归）来打印所有可能的路径。我已经寻找遍历树堆，但它的算法并不抱在我的情况下，由于后序，preorder或序不能应用。我想不出任何算法，因此你能向我提供一些线索或某些环节，来源等？
I have a binary tree and its internal nodes consist of 'AND' or 'XOR'. Leaf nodes have also and data members. I need to print all possible paths by using stack(non-recursive). I have searched for traversing tree with stack, but its algorithm doesn't hold in my case since postorder,preorder or inorder cannot be applied. I just cannot think of any algorithm, so can you provide me some hints or some links, source etc ?
例树：
输出示例：奶酪（10），黄油（20），费罗糕点（3），鸡蛋（1） - 总成本= 34
Example output: Cheese(10), Butter(20), Filo Pastry(3), Egg(1) - Total Cost = 34
推荐答案
这是有帮助的想在树形结构和递归的条款，并认识到pre-顺序，按顺序和后序遍历的在树上递归的三个实例。由于这是一门功课，海事组织你应该问的真正问题你怎么会用栈模拟递归？让我尝试用一棵树的例证回答这个问题。说，树是这个样子
It is helpful to think in terms of the tree structure and recursion, and recognise that pre-order, in-order and post-order traversals are three instances of a recursion on a tree. Since this is a homework, IMO the real question you should be asking "How can you simulate recursion with a stack?" Let me try to answer this with an illustration on a tree. Say the tree looks like this
1
/ \
2 3
和可以说，我们有一个函数递归它的工作原理是这样的：
And lets say we have a function recurse which works this way:
DEF递归节点： 递归（子）对所有节点的孩子 DoSomething的（节点）
def recurse node: recurse(child) over all of node's children doSomething(node)
可以说，我们称之为递归 1.流量将是这样的：
Lets say we call recurse on 1. The flow will be this:
recurse 1
recurse 2
doSomething 2
recurse 3
doSomething 3
doSomething 1
让我们试着反复，现在写这篇文章。
Lets try to write this iteratively now.
def iterate root:
//Let "stack" be the stack of nodes to process
stack.push(root)
while stack is not empty:
curr_node = stack.top()
if curr_node has a child that hasn't been processed:
stack.push(child)
else
doSomething(curr_node)
stack.pop()
和让检查的行为迭代1 ：
iterate 1
stack 1
stack 2 1
doSomething 2
stack 1
stack 3 1
doSomething 3
stack 1
doSomething 1
正如你所看到的，在 DoSomething的被称为节点上的顺序是两个递归和迭代的解决方案是相同的。
As you can see, the order in which doSomething was called on the nodes is identical in both the recursive and iterative solutions.
这篇关于算法一XOR树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！