二叉树遍历的算法

1、递归算法：

 1 void preOrder(BTNode *b)  //先序遍历递归算法
 2 {
 3     if (b!=NULL)
 4     {
 5         visit(b);
 6         preOrder(b->lchild);
 7         preOrder(b->rchild);
 8     }
 9 }
10 void InOrder(BTNode *b)   //中序遍历递归算法
11 {
12     if(b!=NULL)
13     {
14         InOrder(b->lchild);
15         visit(b);
16         InOrder(b->rchild);
17     }
18 }
19 void PostOrder(BTNode *b)   //后序遍历递归算法
20 {
21     if(b!=NULL){
22         PostOrder(b->lchild);
23         PostOrder(b->rchild);
24         visit(b);
25     }
26 }

2、非递归

 1 void PreOrder(BTNode *b)//先序遍历
 2 {
 3     Stack s;
 4     while(b!=NULL||!s.empty())
 5     {
 6         if(b!=NULL){
 7             visit(b);
 8             s.push(b);
 9             b=b->left;
10         }
11         else{
12             b=s.pop();
13             b=b->right;
14         }
15     }
16 }
17 
18 //中序遍历
19 void InOrder(BTNode *b){
20     Stack s;
21     while(b!=NULL||!s.empty()){
22         if (b!=NULL)
23         {
24             s.push(b);
25             s=s->left
26         }
27         if(!s.empty()){
28             b=s.pop();
29             visit(b);
30             b=b->right;
31         }
32     }
33 }
34 
35 //后序遍历
36 void PostOrder(BTNode *b){
37     Stack s;
38     while(b!=NULL){
39         s.push(b);
40     }
41     while(!s.empty()){
42         BTNode* node=s.pop();
43         if(node->bPushed){
44             visit(node);
45         }
46         else{
47             s.push(node);
48             if(node->right!=NULL){
49                 node->right->bPushed=false;
50                 s.push(node->right);
51             }
52             if(node->left!=NULL){
53                 node->left->bpushed=false;
54                 s.push(node->left);
55             }
56         node->bPushed=true;  //如果标识位为true,则表示入栈
57         }        
58     }
59 }