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

问题描述

我有一个二叉树，其内部节点由'AND'或'XOR'组成。叶节点也有和数据成员。我需要使用堆栈（非递归）打印所有可能的路径。我已经搜索了遍历树与堆栈，但其算法不适用于我的情况，因为postorder，preorder或inorder不能应用。我只是不能想到任何算法，所以你能提供一些提示或一些链接，源等吗？

示例树：

>

示例输出：Cheese（10），Butter（20），Filo Pastry（3），Egg（1） - Total Cost = 34

解决方案

在树结构和递归方面考虑是有帮助的，并且认识到预先序，有序和后序遍历是树上的递归的三个实例。由于这是一个作业，IMO真正的问题你应该问你怎么能模拟递归与堆栈？让我试着用树上的插图回答这个问题。

  1 
 / \ 
 2 3 
  

假设我们有一个函数 recurse / p>



def recurse节点：$ b​​ $ b对所有节点的子节点进行递归（子节点）
doSomething（node）

$ b b

假设我们在1上调用 recurse 。流程如下：

  recurse 1 
 recurse 2 
 doSomething 2 
 recurse 3 
 doSomething 3 
 doSomething 1 
  

现在尝试重复写入。

  def iterate root：
 //让stack为要处理的节点的堆栈
 stack.push（root）
 stack不为空时：
 curr_node = stack.top 
如果curr_node有一个尚未处理的子节点：$ b​​ $ b stack.push（child）
 else 
 doSomething（curr_node）
 stack.pop $ b  

并且检查 iterate 1的行为：

  iterate 1 
 stack 1 
 stack 2 1 
 doSomething 2 
 stack 1 
 stack 3 1 
 doSomething 3 
 stack 1 
 doSomething 1 
  

$ b b

如你所见，在节点上调用 doSomething 的顺序在递归和迭代解决方案中是相同的。

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 ?

Example tree:

Example output: Cheese(10), Butter(20), Filo Pastry(3), Egg(1) - Total Cost = 34

解决方案

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 recurse node: recurse(child) over all of node's children doSomething(node)

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()

And lets examine the behaviour of iterate 1:

iterate 1
  stack 1
  stack 2 1
  doSomething 2
  stack 1
  stack 3 1
  doSomething 3
  stack 1
  doSomething 1

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屋！