剑指offer之先序非递归打印二叉树

1 问题

先序非递归打印二叉树

比如二叉树如下

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

先序原则：中左右打印节点，如果左边有节点继续要打做节点，打印会是如下结果

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

2 分析

我们可以用stack,先进后出，我们先push头结点，然后再push它的右节点和左节点，依次类推

3 代码实现

      #include <iostream>
      #include <stack>
      using namespace std;
      typedef struct Node
      {
      int value;
      struct Node* left;
      struct Node* right;
      } Node;
      void start_print(Node *head)
      {
     	if (head == NULL)
      	{
     		std::cout << "head is NULL" << std::endl;
     		return;
      	}
     	std::stack<Node *> stack;
     	stack.push(head);
     	while (stack.size())
      	{
      		Node *node = stack.top();
     		std::cout << node->value << std::endl;
     		//do not remember pop node
      stack.pop();
     		if (node->right)
      		{
     			stack.push(node->right);
      		}
     		if (node->left)
      		{
     			stack.push(node->left);
      		}
      	}
      }
      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;
       start_print(&head1);
      return 0;
      }
  
 

4 运行结果

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

5 总结

      void start_print(Node *head)
      {
     	if (head == NULL)
      	{
     		std::cout << "head is NULL" << std::endl;
     		return;
      	}
     	std::stack<Node *> stack;
     	stack.push(head);
     	while (stack.size())
      	{
      		Node *node = stack.top();
     		std::cout << node->value << std::endl;
     		if (node->right)
      		{
     			stack.push(node->right);
      		}
     		if (node->left)
      		{
     			stack.push(node->left);
      		}
     		//do not remember pop node
      stack.pop();
      	}
      }
  
 

一开始我出现了2个问题

问题1：没有调用stack.pop()函数，导致死循环。

问题2：我把那个stack.pop()写出上面的那个位置，很明显这里是栈，如果node->right或者node->left加到栈里面去了，这个时候再弹出来肯定不是我想要的效果，受之前使用queue的影响，因为pop()函数放哪里都行，想下如果是queue的话，因为是先进先出，所以如果node->right或者node->left加到队列里面去了，再pop()依然是弹出的最顶上的位置，所以不受位置限制。

小结：要记得使用pop()函数弹出来，然后stack调用pop()函数有位置限制，但是queue没有限制。

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

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