18、【常见算法】二叉树的遍历

二叉树的遍历

二叉树的遍历大致可分为先序遍历、中序遍历、后序遍历和层次遍历四种。

1、二叉树的结构体

1 typedef struct BinTreeNode 
2 { 
3     int data; // 默认结点中存储整型数据 
4     struct BinTreeNode* lchild; 
5     struct BinTreeNode* rchild; 
6 };

2、前序遍历

递归方法：

 1 //前序遍历-递归方法
 2 void preOrder(BinTreeNode *root)
 3 {
 4     if(root != NULL)
 5     {
 6         cout << root->data << " ";
 7         preOrder(root->lchild);
 8         preOrder(root->rchild);
 9     }
10 }

非递归方法：

 1 //前序遍历-非递归方法
 2 void preOrder(BinTreeNode *root)
 3 {
 4     stack<BinTreeNode *> s;
 5     BinTreeNode *p = root;
 6     while(p != NULL || !s.empty())
 7     {
 8 
 9         while( p!= NULL)
10         {
11             cout << p->data << " ";
12             s.push(p);
13             p = p->lchild;
14         }
15         if(!s.empty())
16         {
17             p = s.top();
18             s.pop();
19             p = p->rchild;
20         }
21     }
22 }

3、中序遍历

递归方法：

 1 //中序遍历 - 递归
 2 void inOrder(BinTreeNode *root)
 3 {
 4     if(root != NULL)
 5     {
 6         inOrder(root->lchild);
 7         cout << root->data << " ";
 8         inOrder(root->rchild);
 9     }
10 }

非递归方法：

 1 //中序遍历 - 非递归
 2 void inOrder(BinTreeNode *root)
 3 {
 4     stack<BinTreeNode *> s;
 5     BinTreeNode *p;
 6     while(p != NULL || s.empty())
 7     {
 8         while(p != NULL)
 9         {
10             s.push(p);
11             p = p->lchild;
12         }
13         if(!s.empty())
14         {
15             p = s.top();
16             cout << p->data << " ";
17             s.pop();
18             p = p->rchild;
19         }
20     }
21 }

4、后序遍历

递归方法

 1 //后序遍历 - 递归
 2 void postOrder(BinTreeNode *root)
 3 {
 4     if(root != NULL)
 5     {
 6         postOrder(root->lchild);
 7         postOrder(root->rchild);
 8         cout << root->data << " ";
 9     }
10 }

非递归方法

 1 //后序遍历 - 非递归
 2 void postOrder(BinTreeNode *root)
 3 {
 4     stack<BinTreeNode *> s;
 5     BinTreeNode *p = root, *r = NULL;
 6     while(p != NULL || !s.empty())
 7     {
 8         if(p)//走到最左边
 9         {
10             s.push(p);
11             p = p->lchild;
12         }
13         else//向右
14         {
15             p = s.top();
16             if(p->rchild && p->rchild != r)//右子数存在且未被访问
17             {
18                 p = p->rchild;
19                 s.push(p);
20                 p = p->lchild;
21             }
22             else//否则，弹出节点并访问
23             {
24                 p = s.top();
25                 s.pop();
26                 cout << p->data << " ";
27                 r = p;
28                 p = NULL;
29             }
30         }
31     }
32 }

5、层次遍历

非递归方法

 1 //层次遍历 - 非递归
 2 void levelOrder(BinTreeNode *root)
 3 {
 4     queue<BinTreeNode *> q;
 5     BinTreeNode *p = root;
 6     q.push(p);
 7     while(!q.empty())
 8     {
 9         p = q.front();
10         cout << p->data << " ";
11         q.pop();
12         
13         if(p->lchild != NULL)
14         {
15             q.push(p->lchild);
16         }
17         
18         if(p->rchild != NULL)
19         {
20             q.push(p->rchild);
21         }
22     }
23 }