我正在尝试从二叉树创建链接列表。
问题是,是否可以使用简单链表代替双向链表?
我尝试过这个:
typedef struct arvbin* ABin;
typedef struct arvbin
{
int value;
ABin right;
ABin left;
} arvb;
typedef struct slist
{
int value;
struct slist* next;
} *SList;
void preorder(ABin tree, SList *l)
{
if(tree)
{
(*l)->value = tree->value;
(*l)->next = (SList) malloc(sizeof(struct slist));
l = &((*l)->next);
printf("tese\n");
preorder(tree->left, l);
preorder(tree->right, l);
}
return;
}
当然,只有树的一部分被转换。
调用主函数
int main(){
SList l = (SList) malloc(sizeof(struct slist));
preorder(tree, &l);
SList l = (SList) malloc(sizeof(struct slist));
preorder(tree, &l);
printf("height tree. %d \n", height(clone));
print_t(tree);
plist(l);
}
谢谢。
最佳答案
这是我对您的代码的改编:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct arvbin* ABin;
typedef struct arvbin
{
int value;
ABin right;
ABin left;
} arvb;
typedef struct slist
{
int value;
struct slist* next;
} *SList;
static void insert(SList *l, int value)
{
assert(l != 0);
SList node = malloc(sizeof(*node));
if (node == 0)
{
fprintf(stderr, "Out of memory\n");
exit(EXIT_FAILURE);
}
node->value = value;
node->next = *l;
*l = node;
}
static void preorder(ABin tree, SList *l)
{
if (tree)
{
insert(l, tree->value);
preorder(tree->left, l);
preorder(tree->right, l);
}
}
static arvb test_tree[] =
{
{ .value = 19, .left = &test_tree[2], .right = &test_tree[5] }, /*0*/
{ .value = 11, .left = 0, .right = 0 }, /*1*/
{ .value = 13, .left = &test_tree[1], .right = &test_tree[3] }, /*2*/
{ .value = 17, .left = 0, .right = 0 }, /*3*/
{ .value = 101, .left = 0, .right = 0 }, /*4*/
{ .value = 103, .left = &test_tree[4], .right = &test_tree[6] }, /*5*/
{ .value = 107, .left = 0, .right = &test_tree[7] }, /*6*/
{ .value = 109, .left = 0, .right = 0 }, /*7*/
};
static void print_tree_inorder_recursive(arvb *tree)
{
if (tree)
{
print_tree_inorder_recursive(tree->left);
printf(" %d", tree->value);
print_tree_inorder_recursive(tree->right);
}
}
static void print_tree_inorder(arvb *tree)
{
printf("Tree: %p\n", (void *)tree);
print_tree_inorder_recursive(tree);
putchar('\n');
}
static void print_list(SList list)
{
while (list != 0)
{
printf(" %d", list->value);
list = list->next;
}
putchar('\n');
}
int main(void)
{
SList l = 0;
print_tree_inorder(test_tree);
preorder(test_tree, &l);
print_list(l);
return 0;
}
我使用了 C99 指定的初始值设定项,因为您在 left
之前列出了 right
组件,这让我措手不及,当我省略指定的初始值设定项时,因此,与我的预期相比,树是“从后到前”的。 (它是有效的,但不是我所期望的。)请注意,我使用了静态数组来创建树;您不必对树进行动态内存管理,尽管这样做肯定更传统。
代码运行时的输出:
Tree: 0x101df5060
11 13 17 19 101 103 107 109
109 107 101 103 17 11 13 19
如果您愿意,您可以启动格式(%3d
而不是 %d
也可以)。
有时,您应该访问 Is it a good idea to typedef
pointers ;简短的答案是“否”,如果由我决定,我将使用 typedef struct Tree Tree;
和 typedef struct List List;
而不是指针 typedefs全部。
关于将二叉树转换为链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31259665/