- 浏览: 898207 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (537)
- Java SE (114)
- Struts (18)
- Hibernate (25)
- Spring (3)
- Page_Tech (41)
- Others (87)
- Database (29)
- Server (24)
- OpenSource_Tools (15)
- IDE_Tool (22)
- Algorithm (28)
- Interview (22)
- Test (28)
- Hardware (1)
- Mainframe (25)
- Web application (4)
- Linux (3)
- PHP (17)
- Android (1)
- Perl (6)
- ubuntu (1)
- Java EE (9)
- Web Analysis (5)
- Node.js (2)
- javascript (2)
最新评论
-
一键注册:
request.getRequestURL()和request.getRequestURI() -
SuperCustomer:
...
SED的暂存空间和模式空间 -
juyo_ch:
讲得挺好理解的,学习了
java 死锁及解决 -
chinaalex:
最后一题答案正确,但是分析有误.按照如下过程,上一行为瓶,下一 ...
zz智力题 -
liaowuxukong:
多谢博主啦,弱弱的了解了一点。
C++/Java 实现多态的方法(C++)
题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。
比如将二元查找树
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
分析:本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决,本题也不例外。下面我们用两种不同的递归思路来分析。
思路一:当我们到达某一结点准备调整以该结点为根结点的子树时,先调整其左子树将左子树转换成一个排好序的左子链表,再调整其右子树转换右子链表。最近链接左子链表的最右结点(左子树的最大结点)、当前结点和右子链表的最左结点(右子树的最小结点)。从树的根结点开始递归调整所有结点。
思路二:我们可以中序遍历整棵树。按照这个方式遍历树,比较小的结点先访问。如果我们每访问一个结点,假设之前访问过的结点已经调整成一个排序双向链表,我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后,整棵树也就转换成一个排序双向链表了。
参考代码:
首先我们定义二元查找树结点的数据结构如下:
- struct BSTreeNode // a node in the binary search tree
- {
- int m_nValue; // value of node
- BSTreeNode *m_pLeft; // left child of node
- BSTreeNode *m_pRight; // right child of node
- };
struct BSTreeNode // a node in the binary search tree
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
思路一对应的代码:
- ///////////////////////////////////////////////////////////////////////
- // Covert a sub binary-search-tree into a sorted double-linked list
- // Input: pNode - the head of the sub tree
- // asRight - whether pNode is the right child of its parent
- // Output: if asRight is true, return the least node in the sub-tree
- // else return the greatest node in the sub-tree
- ///////////////////////////////////////////////////////////////////////
- BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
- {
- if(!pNode)
- return NULL;
- BSTreeNode *pLeft = NULL;
- BSTreeNode *pRight = NULL;
- // Convert the left sub-tree
- if(pNode->m_pLeft)
- pLeft = ConvertNode(pNode->m_pLeft, false);
- // Connect the greatest node in the left sub-tree to the current node
- if(pLeft)
- {
- pLeft->m_pRight = pNode;
- pNode->m_pLeft = pLeft;
- }
- // Convert the right sub-tree
- if(pNode->m_pRight)
- pRight = ConvertNode(pNode->m_pRight, true);
- // Connect the least node in the right sub-tree to the current node
- if(pRight)
- {
- pNode->m_pRight = pRight;
- pRight->m_pLeft = pNode;
- }
- BSTreeNode *pTemp = pNode;
- // If the current node is the right child of its parent,
- // return the least node in the tree whose root is the current node
- if(asRight)
- {
- while(pTemp->m_pLeft)
- pTemp = pTemp->m_pLeft;
- }
- // If the current node is the left child of its parent,
- // return the greatest node in the tree whose root is the current node
- else
- {
- while(pTemp->m_pRight)
- pTemp = pTemp->m_pRight;
- }
- return pTemp;
- }
- ///////////////////////////////////////////////////////////////////////
- // Covert a binary search tree into a sorted double-linked list
- // Input: the head of tree
- // Output: the head of sorted double-linked list
- ///////////////////////////////////////////////////////////////////////
- BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
- {
- // As we want to return the head of the sorted double-linked list,
- // we set the second parameter to be true
- return ConvertNode(pHeadOfTree, true);
- }
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
// asRight - whether pNode is the right child of its parent
// Output: if asRight is true, return the least node in the sub-tree
// else return the greatest node in the sub-tree
///////////////////////////////////////////////////////////////////////
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
{
if(!pNode)
return NULL;
BSTreeNode *pLeft = NULL;
BSTreeNode *pRight = NULL;
// Convert the left sub-tree
if(pNode->m_pLeft)
pLeft = ConvertNode(pNode->m_pLeft, false);
// Connect the greatest node in the left sub-tree to the current node
if(pLeft)
{
pLeft->m_pRight = pNode;
pNode->m_pLeft = pLeft;
}
// Convert the right sub-tree
if(pNode->m_pRight)
pRight = ConvertNode(pNode->m_pRight, true);
// Connect the least node in the right sub-tree to the current node
if(pRight)
{
pNode->m_pRight = pRight;
pRight->m_pLeft = pNode;
}
BSTreeNode *pTemp = pNode;
// If the current node is the right child of its parent,
// return the least node in the tree whose root is the current node
if(asRight)
{
while(pTemp->m_pLeft)
pTemp = pTemp->m_pLeft;
}
// If the current node is the left child of its parent,
// return the greatest node in the tree whose root is the current node
else
{
while(pTemp->m_pRight)
pTemp = pTemp->m_pRight;
}
return pTemp;
}
///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
// As we want to return the head of the sorted double-linked list,
// we set the second parameter to be true
return ConvertNode(pHeadOfTree, true);
}
思路二对应的代码:
- ///////////////////////////////////////////////////////////////////////
- // Covert a sub binary-search-tree into a sorted double-linked list
- // Input: pNode - the head of the sub tree
- // pLastNodeInList - the tail of the double-linked list
- ///////////////////////////////////////////////////////////////////////
- void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
- {
- if(pNode == NULL)
- return;
- BSTreeNode *pCurrent = pNode;
- // Convert the left sub-tree
- if (pCurrent->m_pLeft != NULL)
- ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
- // Put the current node into the double-linked list
- pCurrent->m_pLeft = pLastNodeInList;
- if(pLastNodeInList != NULL)
- pLastNodeInList->m_pRight = pCurrent;
- pLastNodeInList = pCurrent;
- // Convert the right sub-tree
- if (pCurrent->m_pRight != NULL)
- ConvertNode(pCurrent->m_pRight, pLastNodeInList);
- }
- ///////////////////////////////////////////////////////////////////////
- // Covert a binary search tree into a sorted double-linked list
- // Input: pHeadOfTree - the head of tree
- // Output: the head of sorted double-linked list
- ///////////////////////////////////////////////////////////////////////
- BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
- {
- BSTreeNode *pLastNodeInList = NULL;
- ConvertNode(pHeadOfTree, pLastNodeInList);
- // Get the head of the double-linked list
- BSTreeNode *pHeadOfList = pLastNodeInList;
- while(pHeadOfList && pHeadOfList->m_pLeft)
- pHeadOfList = pHeadOfList->m_pLeft;
- return pHeadOfList;
- }
发表评论
-
IGT JAVA Test
2012-06-18 10:18 01. static synchronized vs synch ... -
zz IBM 面试问题
2012-05-30 14:31 9401.JAVA内存回收机制 2.抽象类与接口的区别 3. ... -
面试的准备与发挥
2012-04-26 10:00 848面试是一场智力的较 ... -
栈内存和堆内存
2010-10-21 11:55 755堆:顺序随意栈:先进 ... -
淘宝面试的几个算法题
2010-10-21 11:27 1451一、给你1副扑克牌,你 ... -
程序员面试题精选(18)-用两个栈实现队列
2010-10-18 22:45 1055题目:某队列的声明如下: C++代码 t ... -
程序员面试题精选(17)-把字符串转换成整数
2010-10-18 22:44 978题目:输入一个表示整 ... -
程序员面试题精选(16)-O(logn)求Fibonacci数列
2010-10-18 22:41 1794题目:定义Fibonacci数列如下: / ... -
程序员面试题精选(15)-含有指针成员的类的拷贝
2010-10-18 22:41 863题目:下面是一个数组类的声明与实现。请分析这个类有什么问题,并 ... -
程序员面试题精选(14)-圆圈中最后剩下的数字
2010-10-18 22:40 1426题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始 ... -
程序员面试题精选(13)-第一个只出现一次的字符
2010-10-18 22:38 870题目:在一个字符串中找到第一个只出现一次的字符。如输入abac ... -
程序员面试题精选(12)-从上往下遍历二元树
2010-10-18 22:37 950题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按 ... -
程序员面试题精选(11)-求二元查找树的镜像
2010-10-18 22:36 1315题目:输入一颗二元查 ... -
程序员面试题精选(10)-在排序数组中查找和为给定值的两个数字
2010-10-18 22:33 1011题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两 ... -
程序员面试题精选(09)-查找链表中倒数第k个结点
2010-10-18 22:32 1124题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数 ... -
程序员面试题精选(08)-求1+2+...+n
2010-10-18 22:31 952题目:求1+2+…+n,要求不能使用乘除法、for、while ... -
程序员面试题精选(07)-翻转句子中单词的顺序
2010-10-18 22:30 1152题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺 ... -
程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果
2010-10-18 22:27 760题目:输入一个整数数 ... -
程序员面试题精选(05)-查找最小的k个元素
2010-10-18 22:24 1416题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3, ... -
程序员面试题精选(04)-在二元树中找出和为某一值的所有路径
2010-10-18 22:22 823题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到 ...
相关推荐
二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4...
微软面试题第一题 直接就可以运行 不过二元查找树 不知道怎么自动生成 所以硬生生地一个个敲出来的 为了学习二元树的就不用下了
程序员面试题精选 100 题(01)-把二元查找树转变成排序的 双向链表 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点, 只调整指针的指向。 程序员面试题精选 100 题...
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表 要求不能创建任何新的节点,只调整指针的指向 微软面试题
由第三方作者花费大量时间收集并整理散落在茫茫网络中的面经,并从中精选出若干具有代表性的技术类的面试题展开讨论,希望能给读者带来...把二元查找树转变成排序的双向链表 设计包含min函数的栈 把字符串转换成整数
微软面试题,输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。适合新手入门结构清晰易懂
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为...
排序树 变成双向链表排序树
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表...
这个是某公司的一道题,是把二叉查找树 转为双向链表的,我用程序实现了。希望对你有帮助!
二叉排序树变成双向循环链表,二叉排序树变成双向循环链表,二叉排序树变成双向循环链表
用双向起泡排序法对带头结点的双向链表按升序进行排序
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
http://msdn.microsoft.com/en-us/library/95z04bas(v=VS.71).aspx 双向链表
双向链表
数据结构算法设计笔试面试题100题内含C语言解析。 (01)把二元查找树转变成排序的双向链表 (02)设计包含min函数的栈 ...
把二元查找树转变成排序的双向链表 设计包含min函数的栈。
面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 交换排序 面试题3:编码实现冒泡排序 面试题4:编码实现快速...
java基础面试题二叉搜索树与双向链表本资源系百度网盘分享地址