剑指offer之中序打印二叉树（非递归实现）

1 问题

中序打印二叉树（非递归实现），比如二叉树如下

      /* 2
      * 3 5
      * 1 4 2 3
      * 3 2 1   5  1   4  2   3
  
 

中序：按左中右来打印二叉树，结果如下

      3
      1
      2
      3
      1
      4
      5
      2
      1
      2
      4
      5
      2
      3
      3
  
 

2 代码实现

      #include <iostream>
      #include <stack>
      using namespace std;
      typedef struct Node
      {
      int value;
      struct Node* left;
      struct Node* right;
      } Node;
      void center_print(Node *head)
      {
     	if (head == NULL)
      	{
     		std::cout << "head is NULL" << std::endl;
     		return;
      	}
     	std::stack<Node *> stack;
     	Node *p = head;
     	while (p != NULL || !stack.empty())
      	{
     		while (p != NULL)
       {
      stack.push(p);
      p = p->left;
       }
      if (!stack.empty())
       {
      p = stack.top();
      std::cout << p->value << std::endl;
      stack.pop();
      p = p->right;
       }
      	}
      }
      int main()
      {
      /* 2
      * 3 5
      * 1 4 2 3
      * 3 2 1   5  1   4  2   3
      */
      Node head1, node1, node2, node3, node4, node5, node6;
      Node node7, node8, node9, node10, node11, node12, node13, node14;
      head1.value = 2;
      node1.value = 3;
      node2.value = 5;
      node3.value = 1;
      node4.value = 4;
      node5.value = 2;
      node6.value = 3;
      node7.value = 3;
      node8.value = 2;
      node9.value = 1;
      node10.value = 5;
      node11.value = 1;
      node12.value = 4;
      node13.value = 2;
      node14.value = 3;
      head1.left = &node1;
      head1.right = &node2;
      node1.left = &node3;
      node1.right = &node4;
      node2.left = &node5;
      node2.right = &node6;
      node3.left = &node7;
      node3.right = &node8;
      node4.left = &node9;
      node4.right = &node10;
      node5.left = &node11;
      node5.right = &node12;
      node6.left = &node13;
      node6.right = &node14;
      node7.left = NULL;
      node7.right = NULL;
      node8.left = NULL;
      node8.right =  NULL;
      node9.left = NULL;
      node9.right = NULL;
      node10.left = NULL;
      node10.right = NULL;
      node11.left = NULL;
      node11.right = NULL;
      node12.left = NULL;
      node12.right = NULL;
      node13.left = NULL;
      node13.right = NULL;
      node14.left = NULL;
      node14.right = NULL;
      center_print(&head1);
      return 0;
      }
  
 

3 运行结果

      2
      3
      1
      3
      2
      4
      1
      5
      5
      2
      1
      4
      3
      2
      3
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/90350060