算法题18 二叉树的前序、中序、后序、分层遍历

题目

　　用非递归的方法完成二叉树的前序、中序、后序、分层遍历

分析

　　1. 二叉树的前序遍历

　　　在遍历的过程中子树的根节点需要返回来再用到一次（查其右子树），需要将遍历的根节点暂时保存起来。可以用栈来实现根节点的暂存

 1 void PrintTreeInPreOrder1(TreeNode* root)
 2 {
 3     if (!root)
 4     {
 5         cout<<"the tree is empty!"<<endl;
 6         return;
 7     }
 8 
 9     stack<TreeNode*> s_parents;
10 
11     TreeNode* node=root;
12     while(node||!s_parents.empty())
13     {
14         while (node)
15         {
16             s_parents.push(node);
17             cout<<node->value<<endl;
18             node=node->pLeft;
19         }
20 
21         node=s_parents.top();
22         s_parents.pop();
23 
24         node=node->pRight;
25     }
26 
27 }

　　2. 二叉树的中序遍历

 1 void PrintTreeInMidorder(TreeNode* root)
 2 {
 3     if (!root)
 4     {
 5         cout<<"the tree is empty!"<<endl;
 6         return;
 7     }
 8 
 9     stack<TreeNode*> s_parents;
10 
11     TreeNode* node=root;
12     while(node||!s_parents.empty())
13     {
14         while (node)
15         {
16             s_parents.push(node);
17             node=node->pLeft;
18         }
19 
20         node=s_parents.top();
21         cout<<node->value<<endl;
22         s_parents.pop();
23 
24         node=node->pRight;
25     }
26 
27 }

　　3. 二叉树的后序遍历

　　　后序遍历比较麻烦，子树的根节点需要返回来用到两次(一次是遍历其右子树，一次是输出其值)，。因此我们需要记录根节点已经遍历的次数，以此来判断该遍历其左子树、右子树还是该输出节点值

 1 void PrintTreeInPostOrder(TreeNode* root)
 2 {
 3     if (!root)
 4     {
 5         cout<<"the tree is empty!"<<endl;
 6         return;
 7     }
 8 
 9     stack<TreeNode*> s_parents;
10     map<TreeNode*,int> map_tag; 
11 
12     TreeNode* node=root;
13     while(node||!s_parents.empty())
14     {
15         if (map_tag.find(node)==map_tag.end())   //节点没有遍历过，循环遍历至最左叶节点
16         {
17             while (node)
18             {
19                 s_parents.push(node);
20                 map_tag.insert(make_pair(node,1));
21                 node=node->pLeft;
22             }
23 
24             node=s_parents.top();
25             cout<<node->value<<endl;
26             s_parents.pop();
27         }
28 
29         if (s_parents.empty())                    //如果栈为空，节点均已打印&pop，遍历结束
30         {
31             break;
32         }
33 
34         node=s_parents.top();
35         if (map_tag[node]==2)                    //如果遍历标记=2，表示左右子孩子都遍历过了，POP返回父节点
36         {
37             cout<<node->value<<endl;
38             s_parents.pop();
39         }else                                   //如果遍历标记=1，表示左子孩子遍历过了，转至遍历右子树
40         {
41             map_tag[node]+=1;
42             node=node->pRight;
43         }
44     }
45 
46 }

　　4.二叉树的分层遍历

　　如果要一层一层的遍历二叉树，需要依次记录下同一层的所有子节点，可以用一个先进先出的队列记录，在遍历a层的同时push 第a+1层的左孩子和右孩子，直到队列为空。

 1 void PrintTreeInLevel(TreeNode* root)
 2 {
 3     list<TreeNode*> node_list;
 4     node_list.push_back(root);
 5     while (node_list.size()>0)
 6     {
 7         TreeNode* node=node_list.front();
 8         cout<<node->value<<endl;
 9 
10         if (node->pLeft!=NULL)
11         {
12             node_list.push_back(node->pLeft);
13         }
14 
15         if (node->pRight!=NULL)
16         {
17             node_list.push_back(node->pRight);
18         }
19 
20         node_list.pop_front();
21 
22     }
23 
24 }