二叉搜索树的遍历

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同主要分为前序遍历，中序遍历，后序遍历。注意，二叉搜索树和普通的二叉树其遍历是一模一样的，因此下文中，不区分是二叉搜索树还是二叉树。

前序遍历

对一颗二叉树的前序遍历操作如下：

• 访问根节点
• 前序遍历左子树
• 前序遍历右子树

例如下图中二叉树前序遍历节点访问顺序为3 1 2 5 4 6：

根据前面所分析的前序遍历的操作步骤，不难看出很容易用递归的方法实现二叉树的前序访问：

//前序遍历递归版本void preOrder(struct node *root){
   
    if(root != NULL)
    {
   
        cout << root->data << " ";
        preOrder(root->left);
        preOrder(root->right);
    }}

其实，还能以非递归的方式实现二叉树的前序遍历：由于在遍历完根节点后还要将其找回来以便遍历该根节点对应的右子树，因此可以考虑使用栈来存储访问过的根节点，代码实现如下：

//前序遍历的非递归版本void preOrder(struct node *root) { 
    stack<struct node *> s;  
    while (root != NULL || !s.empty()) 
    {
     
        if (root != NULL) 
        {
     
        //访问结点并入栈
            cout << root->data << " ";   
            s.push(root);                
            root = root->left; //访问左子树 
       } 
       else 
       {
     
            root = s.top();  //回溯至父亲结点 
            s.pop();  
            root = root->right; //访问右子树 
       }  
    }  
    cout << endl;  }  

中序遍历

对一颗二叉树的中序遍历操作如下：

• 中序遍历左子树
• 访问根节点
• 中序遍历右子树

例如下图中二叉树中序遍历节点访问顺序为1 2 3 4 5 6：

如同前序遍历一样，也可以用递归或者非递归的方式实现，而且其思想也类似，只是访问的顺序不一样了，其两种实现方式如下：

//中序遍历递归版本void inOrder(struct node *root){
   
    if(root != NULL)
    {
   
        inOrder(root->left);
    //和前序遍历相比，只是输出语句换了个位置唯一
    cout << root->data << " ";
        inOrder(root->right);
    }}

//中序遍历的非递归版本void inOrder(struct node *root) { 
    stack<struct node *> s;  
    while (root != NULL || !s.empty()) 
    {
     
        if (root != NULL) 
        {
     
            s.push(root);  
            root = root->left;  
        }  
        else 
        {
     
        //访问完左子树后才访问根结点 
            root = s.top();  
            cout << root->data << " ";  
            s.pop();  
            root = root->right; //访问右子树 
        }  
    }  
    cout << endl;  }  

后续遍历

对一颗二叉树的后序遍历操作如下：

• 后序遍历左子树
• 后序遍历右子树
• 访问根节点

例如下图中二叉树后序遍历节点访问顺序为2 1 4 6 5 3：

二叉树后序遍历递归版本与前序中序类似，如下：

//后序遍历递归版本void postOrder(struct node *root){
   
    if(root != NULL)
    {
   
        postOrder(root->left);
        postOrder(root->right);

        //最后访问根节点
        cout << root->data << " ";
    }}

后序遍历的非递归算法较复杂，使用一个栈可以实现，但是过程很繁琐，我们可以考虑用两个栈来实现后序遍历的非递归算法。注意到后序遍历可以看作是下面遍历的逆过程：即先遍历某个结点，然后遍历其右孩子，然后遍历其左孩子。这个过程逆过来就是后序遍历。算法步骤如下：

(1) push根结点到第一个栈s中。

(2) 从栈s中pop一个结点，将其push到栈output中。

(3) 然后push结点的左孩子和右孩子到第一个栈s中。

(4) 重复过程2和3直到栈s为空。

(5) 现在所有结点已经push到栈output中，且按照后序遍历的顺序存放，直接全部 pop出来即是二叉树后序遍历结果。

代码实现如下：

//后序遍历的非递归版本void postOrder(struct node *root) { 
    if (!root) return;  
    stack<struct node*> s, output;  
    s.push(root);  
    while (!s.empty())     {
     
        struct node *curr = s.top();  
        output.push(curr);  
        s.pop();  
        if (curr->left)  
            s.push(curr->left);  
        if (curr->right)  
            s.push(curr->right);  
    }  

    while (!output.empty())     {
     
        cout << output.top()->data << " ";  
        output.pop();  
    }  
    cout << endl;  }  
          s.push(curr->right);  
    }  

    while (!output.empty())     {
     
        cout << output.top()->data << " ";  
        output.pop();  
    }  
    cout << endl;  }