树

一.二叉树的遍历
  1 #include<iostream>
  2 #include<stack>
  3 #include<queue>
  4 using namespace std;
  5 
  6 typedef struct Node
  7 {
  8     int elem;
  9     struct Node *right;
 10     struct Node *left;
 11 }*TreeNode;
 12 
 13 void InitTree(TreeNode &root)
 14 {
 15     int x;
 16     cin >> x;
 17     if(x < 0)
 18     {
 19         root = NULL;
 20         return;
 21     }
 22     root = new Node;
 23 
 24     root->elem = x;
 25     InitTree(root->left);
 26     InitTree(root->right);
 27 }
 28 
 29 void PreOrder(TreeNode root)
 30 {
 31     if (root != NULL)
 32     {
 33         cout << root->elem << " ";
 34         PreOrder(root->left);
 35         PreOrder(root->right);
 36     }
 37 }
 38 
 39 void InOrder(TreeNode root)
 40 {
 41     if (root != NULL)
 42     {
 43         InOrder(root->left);
 44         cout << root->elem << " ";
 45         InOrder(root->right);
 46     }
 47 }
 48 
 49 void PostOrder(TreeNode root)
 50 {
 51     if (root != NULL)
 52     {
 53         PostOrder(root->left);
 54         PostOrder(root->right);
 55         cout << root->elem << " ";
 56     }
 57 }
 58 
 59 void LevelOrder(TreeNode root)
 60 {
 61     if (root != NULL)
 62     {
 63         queue<TreeNode> q;
 64         q.push(root);
 65         while (! q.empty())
 66         {
 67             cout << q.front()->elem << " ";
 68             if (q.front()->left != NULL)
 69                 q.push(q.front()->left);
 70             if (q.front()->right != NULL)
 71                 q.push(q.front()->right);
 72             q.pop();
 73         }
 74     }
 75 }
 76 
 77 /*
 78 从根节点开始，向左遍历节点并输出元素，把每一个节点的右孩子push到栈里
 79 遍历到NULL后，出栈一个节点p
 80 继续上述步骤
 81 直到栈为空
 82 */
 83 void NoRecursivePreOrder(TreeNode root)
 84 {
 85     if (root == NULL)
 86     {
 87         return;
 88     }
 89     stack<TreeNode> s;
 90     s.push(root);
 91     while (! s.empty())
 92     {
 93         TreeNode p = s.top();
 94         s.pop();
 95         while (p != NULL)
 96         {
 97             cout << p->elem << " ";
 98             if (p->right != NULL)
 99             {
100                 s.push(p->right);
101             }
102             p = p->left;
103         }
104     }
105 }
106 
107 /*
108 把p节点的所有左孩子都入栈
109 遍历到NULL后，出栈一个节点p并输出元素,p=p->right
110 继续上述步骤
111 直到栈为空
112 */
113 void NoRecursiveInOrder(TreeNode root)
114 {
115     if (root == NULL)
116     {
117         return;
118     }
119     stack<TreeNode> s;
120     TreeNode p = root;
121     while (!s.empty() || p != NULL)
122     {
123         while (p != NULL)
124         {
125             s.push(p);
126             p = p->left;
127         }
128         if (!s.empty())
129         {
130             p = s.top();  
131             s.pop();  
132             cout<< p->elem << " ";  
133             p = p->right;
134         }
135     }
136 }
137 
138 /*
139 把p节点的所有左孩子都入栈
140 遍历到NULL后
141 若p->right=NULL或者p的右孩子遍历过了则出栈并输出 否则p=p->right重复操作
142 直到栈为空
143 */
144 void NoRecursivePostOrder(TreeNode root)
145 {
146     if (root == NULL)
147     {
148         return;
149     }
150 
151     stack<TreeNode> s;
152     TreeNode p = root;
153     TreeNode visited = NULL;
154 
155     while (p != NULL || ! s.empty())
156     {
157         while (p != NULL)
158         {
159             s.push(p);
160             p = p->left;
161         }
162         p = s.top();    
163         if(p->right == NULL || p->right == visited)      
164         {      
165             cout<< p->elem << " ";      
166             visited = p;      
167             s.pop();      
168             p = NULL;      
169         }      
170         else    
171             p = p->right;      // 否则访问右孩子    
172     }
173 }
174 
175 
176 int main()
177 {
178     TreeNode root;
179     InitTree(root);
180 
181     PreOrder(root);
182     cout << endl;
183     NoRecursivePreOrder(root);
184     cout << endl;
185 
186     InOrder(root);
187     cout << endl;
188     NoRecursiveInOrder(root);
189     cout << endl;
190 
191     PostOrder(root);
192     cout << endl;
193     NoRecursivePostOrder(root);
194     cout << endl;
195 
196     LevelOrder(root);
197     cout << endl;
198 
199     return 0;
200 }