不使用递归，帮我理解中序遍历

Question

我能够理解使用非递归方式进行前序遍历，但我对中序遍历感到困难。我似乎无法理解它，也许是因为我还没有理解递归的内部工作原理。

目前我尝试过以下方法：

def traverseInorder(node):
    lifo = Lifo()
    lifo.push(node)
    while True:
        if node is None:
            break
        if node.left is not None:
            lifo.push(node.left)
            node = node.left
            continue
        prev = node
        while True:
            if node is None:
                break
            print node.value
            prev = node
            node = lifo.pop()
        node = prev
        if node.right is not None:
            lifo.push(node.right)
            node = node.right
        else:
            break

内部while循环感觉不太对。此外，一些元素被打印了两次；也许我可以通过检查该节点是否已经被打印来解决这个问题，但这需要另一个变量，这再次让人感觉不对。我哪里出错了？我还没有尝试后序遍历，但我猜它很相似，我在那里也会遇到同样的概念障碍。谢谢你的时间！P.S.：Lifo和Node的定义：

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class Lifo:
    def __init__(self):
        self.lifo = ()
    def push(self, data):
        self.lifo = (data, self.lifo)
    def pop(self):
        if len(self.lifo) == 0:
            return None
        ret, self.lifo = self.lifo
        return ret

- Srikanth

Answer 1

从递归算法开始（伪代码）：

traverse(node):
  if node != None do:
    traverse(node.left)
    print node.value
    traverse(node.right)
  endif

这是尾递归的一个典型案例，因此你可以轻松将其转换为while循环。

traverse(node):
  while node != None do:
    traverse(node.left)
    print node.value
    node = node.right
  endwhile

你最后得到的是一个递归调用。递归调用的作用是将一个新的上下文推入堆栈，从头开始运行代码，然后检索上下文并继续执行它正在执行的操作。因此，您需要创建一个用于存储的堆栈和一个循环来确定在每次迭代中，我们是处于“第一次运行”情况（非空节点）还是处于“返回”情况（空节点，非空堆栈），并运行相应的代码：

traverse(node):
  stack = []
  while !empty(stack) || node != None do:
    if node != None do: // this is a normal call, recurse
      push(stack,node)
      node = node.left
    else // we are now returning: pop and print the current node
      node = pop(stack)
      print node.value
      node = node.right
    endif
  endwhile

难以理解的是"return"部分：在循环中，您必须确定正在运行的代码是处于"进入函数"情况还是"从调用返回"情况，并且您将有一个if/else链，其中包含与您的代码中非终端递归一样多的情况。

在这种特定情况下，我们使用节点来保留有关情况的信息。另一种方法是将其存储在堆栈本身中（就像计算机对递归所做的那样）。使用该技术，代码不太优化，但更易于跟踪。

traverse(node):
  // entry:
  if node == NULL do return
  traverse(node.left)
  // after-left-traversal:
  print node.value
  traverse(node.right)

traverse(node):
   stack = [node,'entry']
   while !empty(stack) do:
     [node,state] = pop(stack)
     switch state: 
       case 'entry': 
         if node == None do: break; // return
         push(stack,[node,'after-left-traversal']) // store return address
         push(stack,[node.left,'entry']) // recursive call
         break;
       case 'after-left-traversal': 
         print node.value;
         // tail call : no return address
         push(stack,[node.right,'entry']) // recursive call
      end
    endwhile 

- Victor Nicollet

---

@Victor：谢谢！你提醒我考虑哪些代码部分需要在“进入函数”和“从调用返回”情况下运行的提示，让我直观地理解了。此外，感谢你展示了尾递归展开的中间步骤；我曾听说过这个概念，但亲眼见到它的实现帮助了我很多！ - Srikanth

这是一个很好的解释... 我以前也曾经用一种困难的方式理解过它... 但是上面逐步分解的方法使得它变得更加简单易懂了。 - Harish

我不认为traverse(node): if node != None do: traverse(node.left) print node.value traverse(node.right) endif是尾递归的。 - Jackson Tale

我同意@JacksonTale的观点。这绝对不是尾递归的典型案例。尾递归需要一个递归调用。递归树遍历实际上是非尾递归的典型示例。 - bluenote10

嗨，@Victor，这是关于这个主题最好的文章。 你可以详细介绍pre_order_traversal和post_order_traversal吗？ ^_^ - Charlie 木匠

Answer 2

这里是一个简单的非递归 C++ 中序遍历代码：

void inorder (node *n)
{
    stack s;

    while(n){
        s.push(n);
        n=n->left;
    }

    while(!s.empty()){
        node *t=s.pop();
        cout<<t->data;
        t=t->right;

        while(t){
            s.push(t);
            t = t->left;
        }
    }
}

- Emadpres

Answer 3

def print_tree_in(root):
    stack = []
    current = root
    while True:
        while current is not None:
            stack.append(current)
            current = current.getLeft();
        if not stack:
            return
        current = stack.pop()
        print current.getValue()
        while current.getRight is None and stack:
            current = stack.pop()
            print current.getValue()
        current = current.getRight();

- Ashish

Answer 4

不使用递归的简单迭代中序遍历

'''iterative inorder traversal, O(n) time & O(n) space '''

class Node:
    def __init__(self, value, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right

def inorder_iter(root):

    stack = [root]
    current = root

    while len(stack) > 0:
        if current:
            while current.left:
                stack.append(current.left)
                current = current.left
        popped_node = stack.pop()
        current = None
        if popped_node:
            print popped_node.value
            current = popped_node.right
            stack.append(current)

a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')

b.right = d
a.left = b
a.right = c

inorder_iter(a)

- yask

Answer 5

def traverseInorder(node):
   lifo = Lifo()

  while node is not None:
    if node.left is not None:
       lifo.push(node)
       node = node.left
       continue

   print node.value

   if node.right is not None:
      node = node.right
      continue

   node = lifo.Pop()
   if node is not None :
      print node.value
      node = node.right

顺便说一下：我不懂Python，所以可能会有一些语法问题。

- H H

Answer 6

以下是使用堆栈进行C# (.net)中序遍历的示例:

(如果您需要迭代后序遍历，请参考: 二叉树的非递归后序遍历)

public string InOrderIterative()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                var iterativeNode = this._root;
                while(iterativeNode != null)
                {
                    stack.Push(iterativeNode);
                    iterativeNode = iterativeNode.Left;
                }
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    nodes.Add(iterativeNode.Element);
                    if(iterativeNode.Right != null)
                    {
                        stack.Push(iterativeNode.Right);
                        iterativeNode = iterativeNode.Right.Left;
                        while(iterativeNode != null)
                        {
                            stack.Push(iterativeNode);
                            iterativeNode = iterativeNode.Left;
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

这是一个带有已访问标志的示例：

public string InorderIterative_VisitedFlag()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                BinaryTreeNode iterativeNode = null;
                stack.Push(this._root);
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    if(iterativeNode.visted)
                    {
                        iterativeNode.visted = false;
                        nodes.Add(iterativeNode.Element);
                    }
                    else
                    {
                        iterativeNode.visted = true;
                        if(iterativeNode.Right != null)
                        {
                            stack.Push(iterativeNode.Right);
                        }
                        stack.Push(iterativeNode);
                        if (iterativeNode.Left != null)
                        {
                            stack.Push(iterativeNode.Left);
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

二叉树节点和listtostring实用程序的定义：

string ListToString(List<int> list)
        {
            string s = string.Join(", ", list);
            return s;
        }


class BinaryTreeNode
    {
        public int Element;
        public BinaryTreeNode Left;
        public BinaryTreeNode Right;        
    }

- Dreamer

Answer 7

Here's an iterative C++ solution as an alternative to what @Emadpres posted:

void inOrderTraversal(Node *n)
{
    stack<Node *> s;
    s.push(n);
    while (!s.empty()) {
        if (n) {
            n = n->left;
        } else {
            n = s.top(); s.pop();
            cout << n->data << " ";
            n = n->right;
        }
        if (n) s.push(n);
    }
}

- jpswain

Answer 8

@Victor，我对你尝试将状态推入堆栈的实现有一些建议。我认为这并不必要，因为从堆栈中取出的每个元素都已经被遍历过了。所以，我们只需要一个标志来指示下一个要处理的节点是否来自该堆栈即可，而不是将信息存储到堆栈中。以下是我的实现，它可以正常工作：

def intraverse(node):
    stack = []
    leftChecked = False
    while node != None:
        if not leftChecked and node.left != None:
            stack.append(node)
            node = node.left
        else:
            print node.data
            if node.right != None:
                node = node.right
                leftChecked = False
            elif len(stack)>0:
                node = stack.pop()
                leftChecked = True
            else:
                node = None

- Leonmax

Answer 9

这可能会有帮助（Java 实现）

public void inorderDisplay(Node root) {
    Node current = root;
    LinkedList<Node> stack = new LinkedList<>();
    while (true) {
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else if (!stack.isEmpty()) {
            current = stack.poll();
            System.out.print(current.data + " ");
            current = current.right;
        } else {
            break;
        }
    }
}

- Stuck in Java

Answer 10

class Tree:

    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value

    def insert(self,root,node):
        if root is None:
            root = node
        else:
            if root.value < node.value:
                if root.right is None:
                    root.right = node
                else:
                    self.insert(root.right, node)
            else:
                if root.left is None:
                    root.left = node
                else:
                    self.insert(root.left, node)       

    def inorder(self,tree):
        if tree.left != None:
            self.inorder(tree.left)
        print "value:",tree.value

        if tree.right !=None:
            self.inorder(tree.right)

    def inorderwithoutRecursion(self,tree):
        holdRoot=tree
        temp=holdRoot
        stack=[]
        while temp!=None:
            if temp.left!=None:
                stack.append(temp)
                temp=temp.left
                print "node:left",temp.value

            else:
                if len(stack)>0:
                    temp=stack.pop();
                    temp=temp.right
                    print "node:right",temp.value

- Siddhartha

---

欢迎来到SO。请记得在您的代码中添加4个空格缩进，以便正确显示。此外，我建议您添加一些注释。OP也要求一些解释，因此注释在这里有些必要。 - YakovL