微软等面试100题答案V0.2版部分答案精选[第1-20题]
作者:July 、何海涛等网友—————————
开诚布公，接受读者检验
本文，是根据我之前上传的，微软等面试100题，的答案V0.2版[第1-20题答案]的部分答案精选，此后来不断的粗略的看了看，发现这些答案大部分都有可取之处，但存在的小问题还是不少。
所以，特意把之前上传的答案V0.2版，中部分精彩、和有争议的答案，开诚布公，放到我的博客上，给读者除了帖子外，多提供一个反馈与交流的机会。
要感谢很多的网友，在此，就不一一列出了。
ok，话不絮烦。 此文永久勘误，永久优化。各位，对以下任何一题的答案有任何问题，请把您的意见回复于此贴上：本微软等100题系列V0.1版，永久维护（网友，思路回复）地址：
2010年 10月18日下午 July——————————–1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 10 / / 6 14/ / / /4 8 12 16 转换成双向链表4=6=8=10=12=14=16。
首先我们定义的二元查找树 节点的数据结构如下：struct BSTreeNode{ int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node};
//引用 245 楼 tree_star 的回复#include <stdio.h>#include <iostream.h>
struct BSTreeNode{ int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node};
typedef BSTreeNode DoubleList;DoubleList * pHead;DoubleList * pListIndex;
void convertToDoubleList(BSTreeNode * pCurrent);// 创建二元查找树void addBSTreeNode(BSTreeNode * & pCurrent, int value){ if (NULL == pCurrent) { BSTreeNode * pBSTree = new BSTreeNode(); pBSTree->m_pLeft = NULL; pBSTree->m_pRight = NULL; pBSTree->m_nValue = value; pCurrent = pBSTree;
} else { if ((pCurrent->m_nValue) > value) { addBSTreeNode(pCurrent->m_pLeft, value); } else if ((pCurrent->m_nValue) < value) { addBSTreeNode(pCurrent->m_pRight, value); } else { //cout<<"重复加入节点"<<endl; } }}
// 遍历二元查找树 中序void ergodicBSTree(BSTreeNode * pCurrent){ if (NULL == pCurrent) { return; } if (NULL != pCurrent->m_pLeft) { ergodicBSTree(pCurrent->m_pLeft); }
// 节点接到链表尾部 convertToDoubleList(pCurrent); // 右子树为空 if (NULL != pCurrent->m_pRight) { ergodicBSTree(pCurrent->m_pRight); }}
// 二叉树转换成listvoid convertToDoubleList(BSTreeNode * pCurrent){
pCurrent->m_pLeft = pListIndex; if (NULL != pListIndex) { pListIndex->m_pRight = pCurrent; } else { pHead = pCurrent; } pListIndex = pCurrent; cout<<pCurrent->m_nValue<<endl;}
int main(){ BSTreeNode * pRoot = NULL; pListIndex = NULL; pHead = NULL; addBSTreeNode(pRoot, 10); addBSTreeNode(pRoot, 4); addBSTreeNode(pRoot, 6); addBSTreeNode(pRoot, 8); addBSTreeNode(pRoot, 12); addBSTreeNode(pRoot, 14); addBSTreeNode(pRoot, 15); addBSTreeNode(pRoot, 16); ergodicBSTree(pRoot); return 0;}///////////////////////////////////////////////4681012141516Press any key to continue//////////////////////////////////////////////
快乐要懂得分享，才能加倍的快乐
