本文主要是介绍[程序员面试题精选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;
}
这篇关于[程序员面试题精选100题]1.把二叉查找树转变成排序的双向链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
