我有一个BST，我必须将它变成预订基础上的双向链表。该函数应该更改树中每个节点的指针，以便左指针指向列表中的前一个成员，右指针指向下一个成员。 （根的前一个（左）是NULL;同样最后一个节点（右）的下一个是NULL。）我应该返回创建的DLL的头来打印列表。
障碍：您不能使用辅助功能，您必须更改树本身的指针而不是创建新列表。实施在C.
4
/ \
2 6 ---------> output of DLL: 4<->2<->1<->3<->6<->5<->7.
/ \ / \
1 3 5 7
这是我的代码;我希望有人能在这里帮助我。
Node* converToPreOrder(Node* root)
{
if (root == NULL) return root;
static Node* head = NULL;
static Node* prev = NULL;
Node* temp = root;
if (prev == NULL)
head = root;
if (root->right != NULL && root->left != NULL)
prev = root;
else
{
prev->right = root;
temp->left = prev;
}
converToPreOrder(root->left);
converToPreOrder(root->right);
return head;
}
这里有一些似乎有用的代码。转换功能在概念上非常简单，但在处理细节时需要一些小心。
对于这个问题，在我看来，当您处理任何给定节点时，您需要获得三个元素：
结果列表需要是：
鉴于问题中的树：
4
/ \
2 6 ---------> output of DLL: 4<->2<->1<->3<->6<->5<->7.
/ \ / \
1 3 5 7
最终结果是：
当然，节点2的列表是：
类似地，节点6的列表是：
因此最终的结果是：
列表是双向链接和空终止的。这意味着在返回调用处理节点4时，左侧列表具有以下组织：
+--------+ +--------+ +--------+
0 <----| |<----| |<----| |
| Node 2 | | Node 1 | | Node 3 |
| |---->| |---->| |----> 0
+--------+ +--------+ +--------+
这些简单的案例返回一个包含null next和previous指针的列表。右侧列表按顺序具有类似于节点6,5,7的组织。组装最终结果需要将节点4的左指针设置为空，将节点4的右指针设置为左列表的头部，将左列表头部的左指针设置为节点4，找到结束列表从节点4的右指针开始，然后在此之后添加右列表，并将右列表头部的左指针设置为指向右列表的节点的右指针。
左侧列表或右侧列表或两者都可以为空;这需要一点点的照顾。
这是生成的代码，包含三个测试用例。指向遍历列表的节点技术指针的指针相当强大，值得学习。您可以找到该技术的其他SO问题，例如：
/* SO 4784-9166 */
#include <inttypes.h>
#include <stdio.h>
typedef struct Node Node;
struct Node
{
int number;
Node *left;
Node *right;
};
static Node *convertToPreOrder(Node *root)
{
if (root == 0)
return 0;
Node *l_list = convertToPreOrder(root->left);
Node *r_list = convertToPreOrder(root->right);
root->left = 0;
/* Add left list */
root->right = l_list;
if (l_list != 0)
l_list->left = root;
/* Find the end */
Node **pos = &root;
while ((*pos)->right != 0)
pos = &(*pos)->right;
/* Add right list */
(*pos)->right = r_list;
if (r_list != 0)
r_list->left = *pos;
return root;
}
static void print_node(Node *node)
{
if (node != 0)
printf("Node = 0x%.12" PRIXPTR " - Number = %d - "
"Left = 0x%.12" PRIXPTR " - Right = 0x%.12" PRIXPTR "\n",
(uintptr_t)node, node->number, (uintptr_t)node->left, (uintptr_t)node->right);
}
static void print_BST_preorder(Node *root)
{
if (root == 0)
return;
print_node(root);
print_BST_preorder(root->left);
print_BST_preorder(root->right);
}
static void print_list(Node *list)
{
while (list != 0)
{
print_node(list);
list = list->right;
}
}
static Node *add_bst_node(Node *root, Node *node)
{
if (root == 0)
return node;
if (node->number >= root->number)
root->right = add_bst_node(root->right, node);
else
root->left = add_bst_node(root->left, node);
return root;
}
static void test_bst_to_list(size_t n_nodes, Node nodes[])
{
Node *root = 0;
for (size_t i = 0; i < n_nodes; i++)
root = add_bst_node(root, &nodes[i]);
printf("Print BST in pre-order:\n");
print_BST_preorder(root);
printf("Convert to list\n");
Node *list = convertToPreOrder(root);
printf("Print list:\n");
print_list(list);
putchar('\n');
}
int main(void)
{
Node array1[] =
{
{ 4, 0, 0 },
{ 2, 0, 0 },
{ 1, 0, 0 },
{ 3, 0, 0 },
{ 6, 0, 0 },
{ 5, 0, 0 },
{ 7, 0, 0 },
};
enum { ARRAY1_SIZE = sizeof(array1) / sizeof(array1[0]) };
test_bst_to_list(ARRAY1_SIZE, array1);
Node array2[] =
{
{ 19, 0, 0 },
{ 21, 0, 0 },
{ 20, 0, 0 },
{ 18, 0, 0 },
{ 22, 0, 0 },
{ 24, 0, 0 },
{ 17, 0, 0 },
{ 16, 0, 0 },
{ 23, 0, 0 },
{ 27, 0, 0 },
{ 26, 0, 0 },
{ 25, 0, 0 },
};
enum { ARRAY2_SIZE = sizeof(array2) / sizeof(array2[0]) };
test_bst_to_list(ARRAY2_SIZE, array2);
Node array3[] =
{
{ 16, 0, 0 },
{ 11, 0, 0 },
{ 21, 0, 0 },
{ 10, 0, 0 },
{ 22, 0, 0 },
{ 22, 0, 0 },
{ 21, 0, 0 },
{ 27, 0, 0 },
{ 27, 0, 0 },
{ 20, 0, 0 },
{ 22, 0, 0 },
{ 17, 0, 0 },
{ 12, 0, 0 },
};
enum { ARRAY3_SIZE = sizeof(array3) / sizeof(array3[0]) };
test_bst_to_list(ARRAY3_SIZE, array3);
return 0;
}
print_node()函数被调整为在Mac上运行（64位），其中内存地址通常在前4个nybbles中具有前导零，因此12个十六进制数字足以打印它们。
样本输出：
Print BST in pre-order:
Node = 0x7FFEE6F5B180 - Number = 4 - Left = 0x7FFEE6F5B198 - Right = 0x7FFEE6F5B1E0
Node = 0x7FFEE6F5B198 - Number = 2 - Left = 0x7FFEE6F5B1B0 - Right = 0x7FFEE6F5B1C8
Node = 0x7FFEE6F5B1B0 - Number = 1 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B1C8 - Number = 3 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B1E0 - Number = 6 - Left = 0x7FFEE6F5B1F8 - Right = 0x7FFEE6F5B210
Node = 0x7FFEE6F5B1F8 - Number = 5 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B210 - Number = 7 - Left = 0x000000000000 - Right = 0x000000000000
Convert to list
Print list:
Node = 0x7FFEE6F5B180 - Number = 4 - Left = 0x000000000000 - Right = 0x7FFEE6F5B198
Node = 0x7FFEE6F5B198 - Number = 2 - Left = 0x7FFEE6F5B180 - Right = 0x7FFEE6F5B1B0
Node = 0x7FFEE6F5B1B0 - Number = 1 - Left = 0x7FFEE6F5B198 - Right = 0x7FFEE6F5B1C8
Node = 0x7FFEE6F5B1C8 - Number = 3 - Left = 0x7FFEE6F5B1B0 - Right = 0x7FFEE6F5B1E0
Node = 0x7FFEE6F5B1E0 - Number = 6 - Left = 0x7FFEE6F5B1C8 - Right = 0x7FFEE6F5B1F8
Node = 0x7FFEE6F5B1F8 - Number = 5 - Left = 0x7FFEE6F5B1E0 - Right = 0x7FFEE6F5B210
Node = 0x7FFEE6F5B210 - Number = 7 - Left = 0x7FFEE6F5B1F8 - Right = 0x000000000000
Print BST in pre-order:
Node = 0x7FFEE6F5B230 - Number = 19 - Left = 0x7FFEE6F5B278 - Right = 0x7FFEE6F5B248
Node = 0x7FFEE6F5B278 - Number = 18 - Left = 0x7FFEE6F5B2C0 - Right = 0x000000000000
Node = 0x7FFEE6F5B2C0 - Number = 17 - Left = 0x7FFEE6F5B2D8 - Right = 0x000000000000
Node = 0x7FFEE6F5B2D8 - Number = 16 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B248 - Number = 21 - Left = 0x7FFEE6F5B260 - Right = 0x7FFEE6F5B290
Node = 0x7FFEE6F5B260 - Number = 20 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B290 - Number = 22 - Left = 0x000000000000 - Right = 0x7FFEE6F5B2A8
Node = 0x7FFEE6F5B2A8 - Number = 24 - Left = 0x7FFEE6F5B2F0 - Right = 0x7FFEE6F5B308
Node = 0x7FFEE6F5B2F0 - Number = 23 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B308 - Number = 27 - Left = 0x7FFEE6F5B320 - Right = 0x000000000000
Node = 0x7FFEE6F5B320 - Number = 26 - Left = 0x7FFEE6F5B338 - Right = 0x000000000000
Node = 0x7FFEE6F5B338 - Number = 25 - Left = 0x000000000000 - Right = 0x000000000000
Convert to list
Print list:
Node = 0x7FFEE6F5B230 - Number = 19 - Left = 0x000000000000 - Right = 0x7FFEE6F5B278
Node = 0x7FFEE6F5B278 - Number = 18 - Left = 0x7FFEE6F5B230 - Right = 0x7FFEE6F5B2C0
Node = 0x7FFEE6F5B2C0 - Number = 17 - Left = 0x7FFEE6F5B278 - Right = 0x7FFEE6F5B2D8
Node = 0x7FFEE6F5B2D8 - Number = 16 - Left = 0x7FFEE6F5B2C0 - Right = 0x7FFEE6F5B248
Node = 0x7FFEE6F5B248 - Number = 21 - Left = 0x7FFEE6F5B2D8 - Right = 0x7FFEE6F5B260
Node = 0x7FFEE6F5B260 - Number = 20 - Left = 0x7FFEE6F5B248 - Right = 0x7FFEE6F5B290
Node = 0x7FFEE6F5B290 - Number = 22 - Left = 0x7FFEE6F5B260 - Right = 0x7FFEE6F5B2A8
Node = 0x7FFEE6F5B2A8 - Number = 24 - Left = 0x7FFEE6F5B290 - Right = 0x7FFEE6F5B2F0
Node = 0x7FFEE6F5B2F0 - Number = 23 - Left = 0x7FFEE6F5B2A8 - Right = 0x7FFEE6F5B308
Node = 0x7FFEE6F5B308 - Number = 27 - Left = 0x7FFEE6F5B2F0 - Right = 0x7FFEE6F5B320
Node = 0x7FFEE6F5B320 - Number = 26 - Left = 0x7FFEE6F5B308 - Right = 0x7FFEE6F5B338
Node = 0x7FFEE6F5B338 - Number = 25 - Left = 0x7FFEE6F5B320 - Right = 0x000000000000
Print BST in pre-order:
Node = 0x7FFEE6F5B350 - Number = 16 - Left = 0x7FFEE6F5B368 - Right = 0x7FFEE6F5B380
Node = 0x7FFEE6F5B368 - Number = 11 - Left = 0x7FFEE6F5B398 - Right = 0x7FFEE6F5B470
Node = 0x7FFEE6F5B398 - Number = 10 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B470 - Number = 12 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B380 - Number = 21 - Left = 0x7FFEE6F5B428 - Right = 0x7FFEE6F5B3B0
Node = 0x7FFEE6F5B428 - Number = 20 - Left = 0x7FFEE6F5B458 - Right = 0x000000000000
Node = 0x7FFEE6F5B458 - Number = 17 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B3B0 - Number = 22 - Left = 0x7FFEE6F5B3E0 - Right = 0x7FFEE6F5B3C8
Node = 0x7FFEE6F5B3E0 - Number = 21 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B3C8 - Number = 22 - Left = 0x000000000000 - Right = 0x7FFEE6F5B3F8
Node = 0x7FFEE6F5B3F8 - Number = 27 - Left = 0x7FFEE6F5B440 - Right = 0x7FFEE6F5B410
Node = 0x7FFEE6F5B440 - Number = 22 - Left = 0x000000000000 - Right = 0x000000000000
Node = 0x7FFEE6F5B410 - Number = 27 - Left = 0x000000000000 - Right = 0x000000000000
Convert to list
Print list:
Node = 0x7FFEE6F5B350 - Number = 16 - Left = 0x000000000000 - Right = 0x7FFEE6F5B368
Node = 0x7FFEE6F5B368 - Number = 11 - Left = 0x7FFEE6F5B350 - Right = 0x7FFEE6F5B398
Node = 0x7FFEE6F5B398 - Number = 10 - Left = 0x7FFEE6F5B368 - Right = 0x7FFEE6F5B470
Node = 0x7FFEE6F5B470 - Number = 12 - Left = 0x7FFEE6F5B398 - Right = 0x7FFEE6F5B380
Node = 0x7FFEE6F5B380 - Number = 21 - Left = 0x7FFEE6F5B470 - Right = 0x7FFEE6F5B428
Node = 0x7FFEE6F5B428 - Number = 20 - Left = 0x7FFEE6F5B380 - Right = 0x7FFEE6F5B458
Node = 0x7FFEE6F5B458 - Number = 17 - Left = 0x7FFEE6F5B428 - Right = 0x7FFEE6F5B3B0
Node = 0x7FFEE6F5B3B0 - Number = 22 - Left = 0x7FFEE6F5B458 - Right = 0x7FFEE6F5B3E0
Node = 0x7FFEE6F5B3E0 - Number = 21 - Left = 0x7FFEE6F5B3B0 - Right = 0x7FFEE6F5B3C8
Node = 0x7FFEE6F5B3C8 - Number = 22 - Left = 0x7FFEE6F5B3E0 - Right = 0x7FFEE6F5B3F8
Node = 0x7FFEE6F5B3F8 - Number = 27 - Left = 0x7FFEE6F5B3C8 - Right = 0x7FFEE6F5B440
Node = 0x7FFEE6F5B440 - Number = 22 - Left = 0x7FFEE6F5B3F8 - Right = 0x7FFEE6F5B410
Node = 0x7FFEE6F5B410 - Number = 27 - Left = 0x7FFEE6F5B440 - Right = 0x000000000000
第一个测试用例对应于问题中的示例树。给定树的构造，节点在BST打印和列表打印中以相同的顺序呈现。但是，指针是完全不同的。那个测试用例有点过于简单而不舒服。它不测试BST中给定节点具有空左树或空右树（但不是两者都是叶节点）的情况。