Algorithm for a XOR tree traverse [closed]

问题:

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

回答1:

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.

回答2:

A recursive approach would be to use normal traversal (in,pre or post order) by modifying them a little, i.e. print a node only when it has no left child and right child. As for total cost, just declare a global or static variable and add value to it each time you hit a leaf node.

I'll leave the non-recursive part for you to imagine.