算法一XOR树遍历 [英] Algorithm for a XOR tree traverse

问题描述

我有一个二进制树和内部节点组成'和'或'异'。叶节点也纷纷和数据成员。我需要用栈（非递归）来打印所有可能的路径。我已经寻找遍历树堆，但它的算法并不抱在我的情况下，由于后序，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树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！