K******g
发帖数: 1870 | 1 把一个BST in-place变成双向链表，
right指向后边，left指向前一个。
下面是调用函数的代码，假设已经有了个root
这个代码有问题，但是调了好久，都没有调出来
NODE head_node;
NODE* head = &head_node;
NODE** last = BSTtoDLL(root, head);
(*last)->right = NULL;
head = head_node.right;
head->left = NULL;
NODE** BSTtoDLL(NODE* &node, NODE* &list)
{
if(node==NULL) return NULL;
NODE** rtn_list = BSTtoDLL(node->left, list);
if(rtn_list == NULL)
{
list->right = node;
node->left = list;
}
else
{
(*rtn_list)->right = node; |
p******r
发帖数: 2999 | 2 没看懂为什么要Node**
【在 K******g 的大作中提到】
: 把一个BST in-place变成双向链表，
: right指向后边，left指向前一个。
: 下面是调用函数的代码，假设已经有了个root
: 这个代码有问题，但是调了好久，都没有调出来
: NODE head_node;
: NODE* head = &head_node;
: NODE** last = BSTtoDLL(root, head);
: (*last)->right = NULL;
: head = head_node.right;
: head->left = NULL;
|
g**e
发帖数: 6127 | 3 发一个我昨天写的
private static void join(Node a, Node b) {
a.right = b;
b.left = a;
}
/**
helper function -- given two circular doubly linked
lists, append them and return the new list.
*/
private static Node append(Node a, Node b) {
if (a==null) return b;
if (b==null) return a;
Node aLast = a.left;
Node bLast = b.left;
【在 K******g 的大作中提到】
: 把一个BST in-place变成双向链表，
: right指向后边，left指向前一个。
: 下面是调用函数的代码，假设已经有了个root
: 这个代码有问题，但是调了好久，都没有调出来
: NODE head_node;
: NODE* head = &head_node;
: NODE** last = BSTtoDLL(root, head);
: (*last)->right = NULL;
: head = head_node.right;
: head->left = NULL;
|
Z*****Z
发帖数: 723 | 4 这个不错。赞一个。
我原来写过一个dsw，发现java不能传递指针引用太痛苦了
【在 g**e 的大作中提到】
: 发一个我昨天写的
: private static void join(Node a, Node b) {
: a.right = b;
: b.left = a;
: }
:
: /**
: helper function -- given two circular doubly linked
: lists, append them and return the new list.
: */
|
l****q
发帖数: 177 | 5 首先你的list不断后移，最后全返回了，你再走到头？
其次，当一个点有左右儿子的时候，貌似你的右儿子自己不是NULL的时候就没有被
append上去啊
rtn_list = BSTtoDLL(node->right, node);
if(rtn_list == NULL)
{
return &node;
}
else
{
return rtn_list;
}
写代码一般是从拙入巧的，慢慢改进，一下子写很巧妙的代码会很容易错的
这里有现成的代码
http://cslibrary.stanford.edu/109/TreeListRecursion.html
因为double linked list操作有对称性，它是把tree转成了circular的double list
最后要把头尾break才是你要的 |
J******e
发帖数: 225 | 6 NODE** BSTtoDLL(NODE* &node, NODE* &list)
如果没有理解错误的话，lz定义的这个递归函数是要将以node为根节点的BST转化为DLL
，将其链接到list节点之后，并返回新的DLL尾节点。那么问题在于，在程序中，当左
子树返回的链表不为空的时候，并没有操作将其链接到list上。
指针跟应用的用法可能还要加强一下。 |
