计算机应届毕业生常见面试题目.pdf

计算机应届毕业生常见面试题目汇总 1. 把二元查找树转换成排序的双向链表 题目 ：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能 创建任何新的结点，只调整指针的指向。 比如将二元查找树 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16 。 分析：本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也 不例外。二元查找树 BST 的一个重要特性便是如果按照中序方式对其进行遍历，结果是一个 有序的序列。 所以我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点总是最先被访问。 如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序好的双向链表，我们 再调整当前结点的指针，将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转 换成一个排序双向链表了。 源码： #include iostream using namespace std; typedef struct node { int data; struct node *left; struct node *right; }BSTNode; int InsertBST(BSTNode *bt, int k) { //作为叶子结点插入 BST 树 if(bt NULL) { bt=(BSTNode*)malloc(sizeof(BSTNode)); bt-data=k; bt-left=bt-right=NULL; return 1; } if(bt-data k) return 0; if(bt-datak) return InsertBST(bt-left, k); if(bt-datak) return InsertBST(bt-right, k); } 计算机应届毕业生常见面试题目汇总 void CreateBST(BSTNode *bt, int r[], int n) { int i; for(i=0; in; i++) { InsertBST(bt, r[i]); } } void ConvertToDLinkList(BSTNode *bt, BSTNode *visited) { BSTNode *cur=bt; if(cur!=NULL) { ConvertToDLinkList(cur-left, visited); cur-left=visited; if(visited!=NULL) visited-right=cur; visited=cur; ConvertToDLinkList(cur-right, visited); } } void DispDLinkList(BSTNode *bt) { while(bt!=NULL) { printf(%d , bt-data); bt=bt-right; } } int main() { int r[5]={3,88,9,42,16}; BSTNode *bt=NULL; CreateBST(bt, r, 5); BSTNode *h=NULL; ConvertToDLinkList(bt, h); //查找双链表的开始结点 while(h-left!