B*****p
发帖数: 339 | 1 Write a function to convert a Binary Search Tree into a sorted doubly linked
list. The algorithm should be done
in place. left becomes prev, and right becomes next
唉,没答出来 |
j**l
发帖数: 2911 | 2 这题我在版上问过贴过
http://www.mitbbs.com/article0/JobHunting/31602199_0.html
linked
【在 B*****p 的大作中提到】
: Write a function to convert a Binary Search Tree into a sorted doubly linked
: list. The algorithm should be done
: in place. left becomes prev, and right becomes next
: 唉,没答出来
|
j**l
发帖数: 2911 | 3 推荐下面这段相当简洁的代码
发信人: zhj (green field), 信区: JobHunting
标 题: Re: BST和有序双向链表的相互转换？
发信站: BBS 未名空间站 (Wed May 12 16:46:20 2010, 美东)
void bst2dll(tnode* root, tnode*& list)
{
if(!root)
return;
bst2dll(root->right, list);
root->right = list;
if(list)
list->left = root;
list = root;
bst2dll(root->left, list);
}
linked
【在 B*****p 的大作中提到】
: Write a function to convert a Binary Search Tree into a sorted doubly linked
: list. The algorithm should be done
: in place. left becomes prev, and right becomes next
: 唉,没答出来
|
g****n
发帖数: 431 | 4 phone or on-site?
linked
【在 B*****p 的大作中提到】
: Write a function to convert a Binary Search Tree into a sorted doubly linked
: list. The algorithm should be done
: in place. left becomes prev, and right becomes next
: 唉,没答出来
|
r****o
发帖数: 1950 | 5 最开始调用这个函数的时候, list是个指向tnode的空指针吗?
【在 j**l 的大作中提到】
: 推荐下面这段相当简洁的代码
: 发信人: zhj (green field), 信区: JobHunting
: 标 题: Re: BST和有序双向链表的相互转换？
: 发信站: BBS 未名空间站 (Wed May 12 16:46:20 2010, 美东)
: void bst2dll(tnode* root, tnode*& list)
: {
: if(!root)
: return;
: bst2dll(root->right, list);
: root->right = list;
|
j**l
发帖数: 2911 | 6 应该是的，利用了C++支持的引用参数
【在 r****o 的大作中提到】
: 最开始调用这个函数的时候, list是个指向tnode的空指针吗?
|
f*********5
发帖数: 576 | 7 其实就是一个recursion，利用了BST是一个sorted data structure的缺省条件
root的左子树所有node得值都比root的值小，
将其转化为sorted doubly linked list，放在当前节点前面。
。。。
linked
【在 B*****p 的大作中提到】
: Write a function to convert a Binary Search Tree into a sorted doubly linked
: list. The algorithm should be done
: in place. left becomes prev, and right becomes next
: 唉,没答出来
|
b******v
发帖数: 1493 | 8 这题感觉是把一个BST变成balanced BST的逆操作
可以用递归来做
首先，对于特殊的BST，即root节点左右子树都是单链到底
如何把它转化为一个双链表。这个应该比较简单。
其次，对于一般的BST，可以用递归把左子树变成单链到底，
右子树变成单链到底，然后用第一步的函数合并成双链表。
具体如何实现估计还要想一想。
linked
【在 B*****p 的大作中提到】
: Write a function to convert a Binary Search Tree into a sorted doubly linked
: list. The algorithm should be done
: in place. left becomes prev, and right becomes next
: 唉,没答出来
|
b******v
发帖数: 1493 | 9 嗯，看来我的思路是对的
【在 j**l 的大作中提到】
: 推荐下面这段相当简洁的代码
: 发信人: zhj (green field), 信区: JobHunting
: 标 题: Re: BST和有序双向链表的相互转换？
: 发信站: BBS 未名空间站 (Wed May 12 16:46:20 2010, 美东)
: void bst2dll(tnode* root, tnode*& list)
: {
: if(!root)
: return;
: bst2dll(root->right, list);
: root->right = list;
|
f*******r
发帖数: 1086 | 10 刚刚写了一个，欢迎大家拍砖！
struct DLNode
{
int val;
DLNode* prev;
DLNode* next;
DLNode()
{
int val = -1;
prev = NULL;
next = NULL;
}
};
DLNode* ConvertBSTToDLL(BST_Node* root, bool bRight)
{
if(root==NULL) return NULL;
DLNode* newNode = new DLNode();
newNode->val = root->val;
DLNode* pPrevNode = ConvertBSTToDLL(root->left, false);
if(pPrevNode!=NULL)
{
【在 B*****p 的大作中提到】
: Write a function to convert a Binary Search Tree into a sorted doubly linked
: list. The algorithm should be done
: in place. left becomes prev, and right becomes next
: 唉,没答出来
|
|
|
f*******r
发帖数: 1086 | 11 这个代码我刚才run了一下，貌似会出错的，
大家注意一下:)
【在 j**l 的大作中提到】
: 推荐下面这段相当简洁的代码
: 发信人: zhj (green field), 信区: JobHunting
: 标 题: Re: BST和有序双向链表的相互转换？
: 发信站: BBS 未名空间站 (Wed May 12 16:46:20 2010, 美东)
: void bst2dll(tnode* root, tnode*& list)
: {
: if(!root)
: return;
: bst2dll(root->right, list);
: root->right = list;
|
m*****g
发帖数: 226 | 12 node* bst2dll(node *root, node *start)
{
if(!root) return NULL;
node *prevEnd = start;
if(root->left)
{
prevEnd = bst2dll(root->left, start);
}
root->left = prevEnd;
if(prevEnd) prevEnd->right = root;
if(root->right) return bst2dll(root->right, root);
else return root;
} |
j**l
发帖数: 2911 | 13 太长的话,白板写不下,时间也会不够的
【在 f*******r 的大作中提到】
: 刚刚写了一个，欢迎大家拍砖！
: struct DLNode
: {
: int val;
: DLNode* prev;
: DLNode* next;
: DLNode()
: {
: int val = -1;
: prev = NULL;
|
m*****g
发帖数: 226 | 14 bst的题
容易把自己搞晕
【在 j**l 的大作中提到】
: 太长的话,白板写不下,时间也会不够的
|
f*******r
发帖数: 1086 | 15 谢谢建议的!的确，觉得白板可能20几行程序就显得很多了！
【在 j**l 的大作中提到】
: 太长的话,白板写不下,时间也会不够的
|
q*****n
发帖数: 311 | 16 I don't think this would work.
try this tree
5
/ \
2 7
\ /
4 6
【在 j**l 的大作中提到】
: 推荐下面这段相当简洁的代码
: 发信人: zhj (green field), 信区: JobHunting
: 标 题: Re: BST和有序双向链表的相互转换？
: 发信站: BBS 未名空间站 (Wed May 12 16:46:20 2010, 美东)
: void bst2dll(tnode* root, tnode*& list)
: {
: if(!root)
: return;
: bst2dll(root->right, list);
: root->right = list;
|
a****x
发帖数: 89 | 17 非常经典和有意思的题目
linked
【在 B*****p 的大作中提到】
: Write a function to convert a Binary Search Tree into a sorted doubly linked
: list. The algorithm should be done
: in place. left becomes prev, and right becomes next
: 唉,没答出来
|
x********r
发帖数: 1206 | 18 MARK
linked
【在 B*****p 的大作中提到】
: Write a function to convert a Binary Search Tree into a sorted doubly linked
: list. The algorithm should be done
: in place. left becomes prev, and right becomes next
: 唉,没答出来
|
