二叉树遍历

递归：
1 前序
struct node {
    int data;
    struct node* left;
    struct node* right;
};

void visit(int data)
{
    printf("%d ", data);
}

2 中序
void preOrder(struct node* root)
{
    if (root == NULL)
        return;
    visit(root->data);
    preOrder(root->left);
    preOrder(root->right);
}

3 后序
void postOrder(struct node* root)
{
    if (root == NULL)
        return;
    postOrder(root->left);
    postOrder(root->right);
    visit(root->data);
}

4, 层序（宽度优先）
void printLevel(struct node *p, int level)
 {
  if (!p) return;
  if (level == 1) {
    visit(p->data);
  } else {
    printLevel(p->left, level-1);
    printLevel(p->right, level-1);
  }
}
 
void printLevelOrder(struct node *root) 
{
  int height = maxHeight(root);  //maxHeight计算二叉树高度，如二叉树实例高度为3
  for (int level = 1; level <= height; level++) {
    printLevel(root, level);
    printf("\n");
  }
}

当二叉树高度为N时，此时递归层序遍历为最坏情况，时间复杂度为O（N^2）。当二叉树左右子树基本平衡时，时间复杂度为O（N），分析如下：

设访问第K层时间为T（k），则T（k）存在如下的递归公式：

T(k) = 2T(k-1) + c = 2k-1 T(1) + c = 2k-1 + c 

当二叉树平衡时，则高度为O（lgN），则总时间为：

T(1) + T(2) + ... + T(lg N)
= 1 + 2 + 22 + ... + 2lg N-1 + c
= O(N)

非递归版本 用栈（队列）实现回溯 （访问完左子树再访问右子树，用栈或者队列记录已经访问过的节点访问信息，方便后来回溯）
1 先序//与二叉树镜像的做法类似

1. void preOrder1(TNode* root)
2. {
3.     Stack S;
4.     while ((root != NULL) || !S.empty())
5.     {
6.         if (root != NULL)
7.         {
8.             Visit(root);
9.             S.push(root);       // 先序就体现在这里了，先访问，再入栈
10.             root = root->left;  // 依次访问左子树
11.         }
12.         else
13.         {
14.             root = S.pop();     // 回溯至父亲节点
15.             root = root->right;
16.         }
17.     }
18. }
19. 1. // 先序遍历伪代码：非递归版本，用栈实现，版本2
    2. void preOrder2(TNode* root)
    3. {
    4.     if ( root != NULL)
    5.     {
    6.         Stack S;
    7.         S.push(root);
    8.         while (!S.empty())
    9.         {
    10.             TNode* node = S.pop(); 
    12.             Visit(node);          // 先访问根节点，然后根节点就无需入栈了
    13.             S.push(node->right);  // 先push的是右节点，再是左节点
    14.             S.push(node->left);
    15.         }
    16.     }
    17. }

2 中序

1. 中序遍历伪代码：非递归版本，用栈实现，版本1
2. void InOrder1(TNode* root)
3. {
4.     Stack S;
5.     while ( root != NULL || !S.empty() )
6.     {
7.         while( root != NULL )   // 左子树入栈
8.         {
9.             S.push(root);
10.             root = root->left;
11.         }
12.         if ( !S.empty() )
13.         {
14.             root = S.pop();
15.             Visit(root->data);   // 访问根结点
16.             root = root->right;  // 通过下一次循环实现右子树遍历
17.         }
18.     }
19. }

3 后序
因为中序遍历节点序列有一点的连续性，而后续遍历则感觉有一定的跳跃性。先左，再右，最后才中间节点；访问左子树后，需要跳转到右子树，右子树访问完毕了再回溯至根节点并访问之。这种序列的不连续造成实现前面先序与中序类似的第1个与第3个版本比较困难。但是按照第2个思想，直接来模拟递归还是非常容易的。如下：

1. / 后序遍历伪代码：非递归版本，用栈实现
2. void PostOrder(TNode* root)
3. {
4.     Stack S;
5.     if( root != NULL )
6.     {
7.         S.push(root);
8.     }
9.     while ( !S.empty() )
10.     {
11.         TNode* node = S.pop(); 
12.         if ( node->bPushed )
13.         {   // 如果标识位为true,则表示其左右子树都已经入栈，那么现在就需要访问该节点了
14.             Visit(node);        
15.         }
16.         else
17.         {   // 左右子树尚未入栈，则依次将 右节点,左节点,根节点 入栈
18.             
    
19.             node-?bPushed=true;
20.             s.push(node);
    
21.             if ( node->right != NULL )
22.             {
23.                 node->right->bPushed = false; // 左右子树均设置为false
24.                 S.push(node->right);
25.             }
26.             if ( node->left != NULL )
27.             {
28.                 node->left->bPushed = false;
29.                 S.push(node->left);
30.             }            
31.         }
32.     }
33. }

和中序遍历的第2个版本比较，仅仅只是把左孩子入栈和根节点入栈顺序调换一下；这种差别就跟递归版本的中序与后序一样。

4.层序遍历

这个很简单，就不说。

1. // 层序遍历伪代码：非递归版本，用队列完成
2. void LevelOrder(TNode *root)
3. {
4.     Queue Q;
5.     Q.push(root);
7.     while (!Q.empty())
8.     {
9.         node = Q.front();        // 取出队首值并访问
10.         Visit(node);
12.         if (NULL != node->left)  // 左孩子入队
13.         {          
14.             Q.push(node->left);    
15.         }
16.         if (NULL != node->right) // 右孩子入队
17.         {
18.             Q.push(node->right);
19.         }
20.     }
21. }

结一下：

用栈来实现比增加指向父节点指针回溯更方便；

采用第一个思想，就是跟踪指针移动 用栈保存中间结果的实现方式，先序与中序难度一致，后序很困难。先序与中序只需要修改一下访问的位置即可。

采用第二个思想，直接用栈来模拟递归，先序非常简单；而中序与后序难度一致。先序简单是因为节点可以直接访问，访问完毕后无需记录。而中序与后序时，节点在弹栈后还不能立即访问，还需要等其他节点访问完毕后才能访问，因此节点需要设置标志位来判定，因此需要额外的O(n)空间。