33

我能够在不使用递归的情况下理解前序遍历，但是我很难进行中序遍历。我只是似乎不明白，也许是因为我不了解递归的内部工作。

这是我迄今为止尝试过的：

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循环感觉不对。此外，一些元素被打印两次；可能我可以通过检查该节点之前是否已打印来解决此问题，但这需要另一个变量，这再次感觉不对。我哪里错了？

我没有尝试过后序遍历，但我想它是相似的，我也会在那里面临同样的概念障碍。

谢谢你的时间！

PS：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
4

15 回答 15

89

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

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

最难掌握的是“返回”部分：您必须在循环中确定您正在运行的代码是处于“进入函数”的情况还是“从调用中返回”的情况，并且您将有一个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
于 2010-01-22T11:05:51.757 回答
17

这是一个简单的有序非递归 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;
        }
    }
}
于 2011-02-06T19:55:31.000 回答
3 
def print_tree_in（根）：
    堆栈 = []
    当前 = 根
    而真：
        虽然当前不是无：
            stack.append(当前)
            当前 = current.getLeft();
        如果不堆叠：
            返回
        当前 = stack.pop()
        打印 current.getValue()
        而 current.getRight 是 None 和堆栈：
            当前 = stack.pop()
            打印 current.getValue()
        当前 = current.getRight();
于 2012-01-02T18:44:54.767 回答
1 
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

PS：我不懂 Python，所以可能会有一些语法问题。

于 2010-01-22T11:06:20.063 回答
1

这是在 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);
        }

binarytreenode、listtostring 实用程序的定义：

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


class BinaryTreeNode
    {
        public int Element;
        public BinaryTreeNode Left;
        public BinaryTreeNode Right;        
    }
于 2014-07-13T05:02:54.740 回答
1

没有递归的简单迭代中序遍历

'''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)
于 2016-10-08T14:06:34.420 回答
0

可以隐式记住状态，

traverse(node) {
   if(!node) return;
   push(stack, node);
   while (!empty(stack)) {
     /*Remember the left nodes in stack*/
     while (node->left) {
        push(stack, node->left);
        node = node->left;
      }

      /*Process the node*/
      printf("%d", node->data);

      /*Do the tail recursion*/
      if(node->right) {
         node = node->right
      } else {
         node = pop(stack); /*New Node will be from previous*/
      }
    }
 }
于 2010-03-01T03:40:21.937 回答
0

@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
于 2011-07-31T02:25:41.153 回答
0

@Emadpres 对答案的一点优化

def in_order_search(node):
    stack = Stack()
    current = node

    while True:
        while current is not None:
            stack.push(current)
            current = current.l_child

        if stack.size() == 0:
            break

        current = stack.pop()
        print(current.data)
        current = current.r_child
于 2015-09-11T03:37:17.047 回答
0

这可能会有所帮助（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;
        }
    }
}
于 2015-11-23T23:14:53.490 回答
0 
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
于 2016-10-16T21:15:30.770 回答
0

这是一个迭代 C++ 解决方案，作为@Emadpres 发布的替代方案： 

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);
    }
}

于 2017-12-13T21:30:11.383 回答
0

这是用于中序遍历的迭代 Python 代码::

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

def inOrder(root):
    current = root
    s = []
    done = 0

    while(not done):
        if current is not None :
            s.append(current)
            current = current.left
        else :
            if (len(s)>0):
                current = s.pop()
                print current.data
                current = current.right
            else :
                done =1

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

inOrder(root)
于 2018-01-12T14:51:37.877 回答
0

为了编写这些递归方法的迭代等价物，我们可以首先了解递归方法本身是如何在程序的堆栈上执行的。假设节点没有父指针，我们需要为迭代变体管理我们自己的“堆栈”。

开始的一种方法是查看递归方法并标记调用将“恢复”的位置（新的初始调用，或递归调用返回之后）。下面这些标记为“RP 0”、“RP 1”等（“恢复点”）。以中序遍历为例。（我将使用 C 语言进行介绍，但同样的方法适用于任何通用语言）：

void in(node *x)  
{  
  /* RP 0 */  
  if(x->lc) in(x->lc);  
  /* RP 1 */  
  process(x);  
  if(x->rc) in(x->rc);  
  /* RP 2 */  
}

它的迭代变体：

void in_i(node *root)  
{  
  node *stack[1000];  
  int top;  
  char pushed;  
 
  stack[0] = root;  
  top = 0;  
  pushed = 1;  
 
  while(top >= 0)  
  {  
    node *curr = stack[top];  
 
    if(pushed)  
    {  
      /* type (x: 0) */  
      if(curr->lc)  
      {  
        stack[++top] = curr->lc;  
        continue;  
      }  
    }  
 
    /* type (x: 1) */  
    pushed = 0;  
    process(curr);  
    top--;  
 
    if(curr->rc)  
    {  
      stack[++top] = curr->rc;  
      pushed = 1;  
    }  
  }  
}

代码注释与(x: 0)递归(x: 1)方法中的“RP 0”和“RP 1”恢复点相对应。该pushed标志帮助我们推断出这两个恢复点之一。我们不需要在其“RP 2”阶段处理节点，因此我们不会将此类节点保留在堆栈中。

于 2021-01-13T16:41:36.360 回答
-2

我认为问题的一部分是“prev”变量的使用。您不必存储上一个节点，您应该能够在堆栈（Lifo）本身上维护状态。

从Wikipedia，您的目标算法是：

  1. 访问根。
  2. 遍历左子树
  3. 遍历右子树

在伪代码中（免责声明，我不了解 Python，因此为下面的 Python/C++ 样式代码道歉！）您的算法将类似于：

lifo = Lifo();
lifo.push(rootNode);

while(!lifo.empty())
{
    node = lifo.pop();
    if(node is not None)
    {
        print node.value;
        if(node.right is not None)
        {
            lifo.push(node.right);
        }
        if(node.left is not None)
        {
            lifo.push(node.left);
        }
    }
}

对于后序遍历，您只需交换将左右子树推入堆栈的顺序。

于 2010-01-22T11:07:05.503 回答