j**l
发帖数: 2911 | 1 要求in place就地转换
１．从BST转为sorted doubly-linked list可以用类似中序遍历的递归方法做，结果唯
一。
２．那么反过来，从sorted doubly-linked list转换为一棵BST, 结果不唯一，该如何
做才能尽可能的保证BST是平衡的呢(minimal height)？如果是从sorted array转为最
小高度的平衡BST，有类似binary search的思想。对双向链表，有什么好的思路？
1的白板代码如下
void TreeToList(Tree* root, Tree* &head, Tree* &tail)
{
// This is a very special case
if (root == NULL)
{
head = NULL;
tail = NULL;
return;
}
Tree* temp_head;
Tree* temp_tail;
if (root->left != NULL)
{
| m*****g
发帖数: 226 | 2 直接把中间的那个提出来当root，然后连接左子树和右子树的root，不行吗 | z*j
发帖数: 42 | 3 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);
} | z***e
发帖数: 5393 | 4 maybe you can count the double linked list to find out which one is the "
middle point"(root).
before the middle point:
for any consective a1,a2,a3 (a1 is the root for previous), you can create
a2
a1 a3
then for the next a4, a5, you can have
a4
a2 a5
until you reach the middle point.
After the middle point, you don't use the "root" for the previous tree, but
the "right child".
say you have:
b1
b2 b3
then for b4, b5, you use b3 as the root to create:
b3
b4 b5
just my thought...
【在 j**l 的大作中提到】
: 要求in place就地转换
: １．从BST转为sorted doubly-linked list可以用类似中序遍历的递归方法做，结果唯
: 一。
: ２．那么反过来，从sorted doubly-linked list转换为一棵BST, 结果不唯一，该如何
: 做才能尽可能的保证BST是平衡的呢(minimal height)？如果是从sorted array转为最
: 小高度的平衡BST，有类似binary search的思想。对双向链表，有什么好的思路？
: 1的白板代码如下
: void TreeToList(Tree* root, Tree* &head, Tree* &tail)
: {
: // This is a very special case
| H*****L
发帖数: 5705 | | j**l
发帖数: 2911 | 6 虽然没有具体验证，但看起来简洁而明快。
【在 z*j 的大作中提到】
: 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);
| s********l
发帖数: 998 | 7 这个是bst to double link list
楼主在问如何dll变成 一个balanced bst~
【在 z*j 的大作中提到】
: 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);
| h****t
发帖数: 184 | 8 这个对 输入的参数 list有要求吧。当第一次调用的时候，
要求用户初始化这个参数为null，
tnode * head = null;
bst2dll(root,head);
【在 z*j 的大作中提到】
: 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);
| h****t
发帖数: 184 | 9
我写了一个，请指正。
node * findmiddle( node *head, node *tail)
{
if ( head == null || tail == null )
return null;
while ( head != tail && head->right != tail)
{
head = head->right;
tail = tail->left;
}
return head;
}
void ListToTree(node *head, node *tail, node *& root)
{
node *mid,*tr;
if ( head == null || tail == null )
{
root = null;
return;
}
if ( head == tail )
{
root = head;
root->left = root->right = nu
【在 j**l 的大作中提到】
: 要求in place就地转换
: １．从BST转为sorted doubly-linked list可以用类似中序遍历的递归方法做，结果唯
: 一。
: ２．那么反过来，从sorted doubly-linked list转换为一棵BST, 结果不唯一，该如何
: 做才能尽可能的保证BST是平衡的呢(minimal height)？如果是从sorted array转为最
: 小高度的平衡BST，有类似binary search的思想。对双向链表，有什么好的思路？
: 1的白板代码如下
: void TreeToList(Tree* root, Tree* &head, Tree* &tail)
: {
: // This is a very special case
| i*o
发帖数: 149 | 10 link list 的 node (two pointers to prev, next)， 不可以直接用作BST的node (
three pointers to left, right and parent).
link-list -> BST 一定要从新allocate memory (free memory).
怎末定义你的in place呢？
【在 j**l 的大作中提到】
: 要求in place就地转换
: １．从BST转为sorted doubly-linked list可以用类似中序遍历的递归方法做，结果唯
: 一。
: ２．那么反过来，从sorted doubly-linked list转换为一棵BST, 结果不唯一，该如何
: 做才能尽可能的保证BST是平衡的呢(minimal height)？如果是从sorted array转为最
: 小高度的平衡BST，有类似binary search的思想。对双向链表，有什么好的思路？
: 1的白板代码如下
: void TreeToList(Tree* root, Tree* &head, Tree* &tail)
: {
: // This is a very special case
| h**k
发帖数: 3368 | 11 Invariance:
调用build_bst时，list_cur总是指向这个树的第一个节点，len记录这个数的节点总数。
每次移动list_cur时，总是在list_cur指向一个树的root时。移动list_cur时，所有在
list_cur前的节点都已经处理完了。
Node * build_bst( Node* &list_cur, int len)
{
if( len == 0 )
return null;
Node* temp = build_bst( list_cur, len/2);
list_cur->left = temp;
temp = list_cur;
list_cur=list_cur->right;
temp->right = build_bst( list_cur, len-1-len/2);
return temp;
}
【在 j**l 的大作中提到】
: 要求in place就地转换
: １．从BST转为sorted doubly-linked list可以用类似中序遍历的递归方法做，结果唯
: 一。
: ２．那么反过来，从sorted doubly-linked list转换为一棵BST, 结果不唯一，该如何
: 做才能尽可能的保证BST是平衡的呢(minimal height)？如果是从sorted array转为最
: 小高度的平衡BST，有类似binary search的思想。对双向链表，有什么好的思路？
: 1的白板代码如下
: void TreeToList(Tree* root, Tree* &head, Tree* &tail)
: {
: // This is a very special case
| l****q
发帖数: 177 | 12 不明白，dsw算法不够么？
两个循环left rotate
【在 j**l 的大作中提到】
: 要求in place就地转换
: １．从BST转为sorted doubly-linked list可以用类似中序遍历的递归方法做，结果唯
: 一。
: ２．那么反过来，从sorted doubly-linked list转换为一棵BST, 结果不唯一，该如何
: 做才能尽可能的保证BST是平衡的呢(minimal height)？如果是从sorted array转为最
: 小高度的平衡BST，有类似binary search的思想。对双向链表，有什么好的思路？
: 1的白板代码如下
: void TreeToList(Tree* root, Tree* &head, Tree* &tail)
: {
: // This is a very special case
|
|
