알고리즘 문제 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 PrintTreeInPostOrder1(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())
30         {
31             break;
32         }
33 
34         node=s_parents.top();
35         if (map_tag[node]==2)
36         {
37             cout<<node->value<<endl;
38             s_parents.pop();
39         }else
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 }