欢迎来到天天文库
浏览记录
ID:53002148
大小:432.08 KB
页数:84页
时间:2020-04-10
《微软等公司数据结构+算法面试100 前40(附答案).pdf》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、1.把二元查找树转变成排序的双向链表题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。10/614//481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下:structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};//引用245楼tree_star的回复#include#i
2、ncludestructBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};typedefBSTreeNodeDoubleList;DoubleList*pHead;DoubleList*pListIndex;voidconvertToDoubleList(BSTreeNode*pCurrent);//创建二元查找树voidaddBSTreeNode(BSTreeNode*&pCurren
3、t,intvalue){if(NULL==pCurrent){BSTreeNode*pBSTree=newBSTreeNode();2pBSTree->m_pLeft=NULL;pBSTree->m_pRight=NULL;pBSTree->m_nValue=value;pCurrent=pBSTree;}else{if((pCurrent->m_nValue)>value){addBSTreeNode(pCurrent->m_pLeft,value);}elseif((pCurrent->m_nValue)m_pRi
4、ght,value);}else{//cout<<"重复加入节点"<m_pLeft){ergodicBSTree(pCurrent->m_pLeft);}//节点接到链表尾部convertToDoubleList(pCurrent);//右子树为空if(NULL!=pCurrent->m_pRight){ergodicBSTree(pCurrent->m_pRight);}}
5、3//二叉树转换成listvoidconvertToDoubleList(BSTreeNode*pCurrent){pCurrent->m_pLeft=pListIndex;if(NULL!=pListIndex){pListIndex->m_pRight=pCurrent;}else{pHead=pCurrent;}pListIndex=pCurrent;cout<m_nValue<6、;addBSTreeNode(pRoot,4);addBSTreeNode(pRoot,6);addBSTreeNode(pRoot,8);addBSTreeNode(pRoot,12);addBSTreeNode(pRoot,14);addBSTreeNode(pRoot,15);addBSTreeNode(pRoot,16);ergodicBSTree(pRoot);return0;}///////////////////////////////////////////////4681012141516Pressanykeytocontinue/////////////////7、/////////////////////////////42.设计包含min函数的栈。定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。结合链表一起做。首先我做插入以下数字:10,7,3,3,8,5,2,60:10->NULL(MIN=10,POS=0)1:7->[0](MIN=7,POS=1)用数组表示堆栈,第0个元素表示栈底2:3->[1](MIN=3,POS=2)3:3->[2](MIN
6、;addBSTreeNode(pRoot,4);addBSTreeNode(pRoot,6);addBSTreeNode(pRoot,8);addBSTreeNode(pRoot,12);addBSTreeNode(pRoot,14);addBSTreeNode(pRoot,15);addBSTreeNode(pRoot,16);ergodicBSTree(pRoot);return0;}///////////////////////////////////////////////4681012141516Pressanykeytocontinue/////////////////
7、/////////////////////////////42.设计包含min函数的栈。定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。结合链表一起做。首先我做插入以下数字:10,7,3,3,8,5,2,60:10->NULL(MIN=10,POS=0)1:7->[0](MIN=7,POS=1)用数组表示堆栈,第0个元素表示栈底2:3->[1](MIN=3,POS=2)3:3->[2](MIN
此文档下载收益归作者所有