二叉树的遍历

二叉树的存储结构：

1 struct BinaryTreeNode {
2         int     val;
3         BinaryTreeNode *left;
4         BinaryTreeNode *right;
5 
6         BinaryTreeNode(int v, BinaryTreeNode *l = NULL, BinaryTreeNode *r = NULL): 
7         val(v), left(l), right(r){}
8     };

前序遍历：

　　根节点->左子树->右子树

　　递归方法：

1 void PreOrder(BinaryTreeNode* root) {
2     if (root != NULL) {
3         std::cout<<root->val；
4         PreOrder(root->left);
5         PreOrder(root->right);
6     }
7 }

　　迭代方法：

 1 void PreOrder(BinaryTreeNode* root) {
 2     BinaryTreeNode* p = root;
 3     std::stack<BinaryTreeNode*> s;
 4 
 5     while (p!= NULL || !s.empty()) {
 6         if (p != NULL) {
 7             std::cout<<p->val;
 8             s.push(p);
 9             p = p->left;
10         } else {
11             p = s.top();
12             s.pop();
13             p = p->right;
14         }
15     }
16 }

中序遍历：

　　左子树->根节点->右子树

　　递归方法：

1 void InOrder(BinaryTreeNode *root) {
2     if (root != NULL) {
3         InOrder(root->left);
4         std::cout<<p->val;
5         InOrder(root->right);
6 
7     }
8 }

　　迭代方法：

 1 void Inorder(BinaryTreeNode* root) {
 2     BinaryTreeNode* p = root;
 3     std::stack<BinaryTreeNode*> s;
 4 
 5     while (p != NULL || !s.empty()) {
 6         if (p != NULL) {
 7             s.push(p);
 8             p = p->left;
 9         } else {
10             p = s.top();
11             std::cout<<p->val;
12             s.pop();
13             p=p->right;
14         }
15     }
16 }

后序遍历：

　　左子树->根节点->右子树

　　递归方法：

1 void Postorder(BinaryTreeNode* root) {
2     if (root != NULL) {
3         PostorderRecur(root->left);
4         PostorderRecur(root->right);
5         std::cout<<root->val;
6     }
7 }

　　迭代方法：

　　因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。当用栈来保存节点，必须分清返回根节点时，是从左子树返回的，还是从右子树返回的。所以，使用辅助指针r，其指向最近访问过的节点。

 1 void BinaryTree::Postorder() {
 2     BinaryTreeNode* p = root;
 3     BinaryTreeNode* r = NULL;
 4     std::stack<BinaryTreeNode*> s;
 5 
 6     while (p!= NULL && !s.empty()) {
 7         if (p != NULL) {
 8             s.push(p);
 9             p = p->left;
10         } else {
11             p = s.top();
12             if (p->right != NULL && p->right != r) {
13                 p = p->right;16             
　　　　　　　　　} else {
17                 s.pop();
18                 std::cout<<p->val<<" ";
19                 r = p;
20                 p = NULL;
21             }
22         }
23     }
24 }

层次遍历：

 1 void Levelorder() {
 2     BinaryTreeNode *p = root;
 3     std::queue<BinaryTreeNode*> q;
 4 
 5     if (p != NULL) {
 6         q.push(p);
 7     }
 8 
 9     while (!q.empty()) {
10         p = q.front();
11         q.pop();
12         std::cout<<p->val;
13 
14         if (p->left != NULL) {
15             q.push(p->left);
16         }
17         if (p->right != NULL) {
18             q.push(p->right);
19         }
20     }
21 }