[程序员面试题精选100题]1.把二叉查找树转变成排序的双向链表

【题目】

输入一棵二叉查找树，将该二叉查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

比如将二叉查找树
                                            10
                                          /    \
                                        6       14
                                      /  \     /　 \
                                   　     4     8  12 　  16
转换成双向链表4=6=8=10=12=14=16

参考：程序员面试题精选100题(01)－把二元查找树转变成排序的双向链表

【思路】

本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也不例外。

我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，

我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

【代码】

/*********************************
*   日期：2013-12-17
*   作者：SJF0115
*   题目: 把二元查找树转变成排序的双向链表
*   来源：微软
*   分类：经典面试题
**********************************/
#include <iostream>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};
//中序遍历过程中改变
// 转换后pre指向双向链表的最后一个节点
// root成为中间节点
void ConvertDoubleList(TreeNode* root, TreeNode*& pre) {
    if(root == NULL){
        return;
    }
    // 当前节点
    TreeNode* cur = root;
    // 左子节点
    if(cur->left){
        ConvertDoubleList(cur->left,pre);
    }
    // 中间节点 改成双向链表
    cur->left = pre;
    if(pre != NULL){
        pre->right = cur;
    }//if
    // 前一节点
    pre = cur;
    // 右子节点
    if(cur->right){
        ConvertDoubleList(cur->right,pre);
    }//if
}
// 二叉查找树插入
void TreeInsert(TreeNode*& root,int val){
    // 创建新节点
    TreeNode* node = new TreeNode(val);
    if(root == NULL){
        root = node;
    }
    else{
        TreeNode *pre = NULL;
        TreeNode *cur = root;
        // 寻找插入位置
        while(cur){
            // 父节点
            pre = cur;
            // 沿左子树方向下降
            if(val < cur->val){
                cur = cur->left;
            }
            // 沿右子树方向下降
            else{
                cur = cur->right;
            }
        }//while
        // 插入左子结点处
        if(val < pre->val){
            pre->left = node;
        }
        // 插入右子结点处
        else{
            pre->right = node;
        }//if
    }//if
}

// 中序遍历
void InOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    if(root->left){
        InOrder(root->left);
    }
    cout<<root->val<<endl;
    if(root->right){
        InOrder(root->right);
    }
}
//输出双向链表
void PrintDoubleList(TreeNode *head){
    TreeNode *cur = head;
    if(cur == NULL){
        return;
    }
    // 反向遍历
    while(cur->left){
        cout<<cur->val<<"->";
        cur = cur->left;
    }
    cout<<cur->val<<"->NULL"<<endl;
    // 正向遍历
    while(cur){
        cout<<cur->val<<"->";
        cur = cur->right;
    }
    cout<<"NULL"<<endl;
}

int main(){
    int array[] = {10,6,14,4,8,12,16};
    // 创建二叉查找树
    TreeNode *root = NULL;
    for(int i = 0;i < 7;i++){
        TreeInsert(root,array[i]);
    }
    // 中序遍历
    // InOrder(root);
    // 二叉查找树转换为双向链表
    TreeNode *pre = NULL;
    ConvertDoubleList(root,pre);
    // 打印双向链表
    PrintDoubleList(pre);
    return 0;
}