将二叉树转换为链表 [英] Convert binary tree to linked list
问题描述
我正在尝试从二叉树创建一个链表.
I am trying to create a linked list from a binary tree.
问题是,是否可以使用简单链表而不是双向链表?
The thing is, is it possible to use a simple linked list instead of the doubly linked list?
我试过了:
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
");
preorder(tree->left, l);
preorder(tree->right, l);
}
return;
}
当然只转换了树的一部分.
Of course only a part of the tree is converted.
在主调用
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
", height(clone));
print_t(tree);
plist(l);
}
谢谢.c
推荐答案
这是我对您代码的改编:
Here's my adaptation of your code:
#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
");
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
", (void *)tree);
print_tree_inorder_recursive(tree);
putchar('
');
}
static void print_list(SList list)
{
while (list != 0)
{
printf(" %d", list->value);
list = list->next;
}
putchar('
');
}
int main(void)
{
SList l = 0;
print_tree_inorder(test_tree);
preorder(test_tree, &l);
print_list(l);
return 0;
}
我使用了 C99 指定初始化程序,因为您在 left
之前列出了 right
组件,这让我措手不及,当我省略指定初始化程序时,因此,与我的预期相比,树是从后到前"的.(它是有效的,但不是我所期望的.)请注意,我使用了一个静态数组来创建树;您不必对树进行动态内存管理,尽管这样做肯定更传统.
I've used C99 designated initializers because you listed the right
component before the left
, which caught me unawares, and when I omitted the designated initializers, therefore, the tree was 'back to front' compared with what I expected. (It was valid, but not what I expected.) Note that I've used a static array to create the tree; you don't have to do dynamic memory management of the tree, though it is certainly more conventional to do so.
代码运行时的输出:
Tree: 0x101df5060
11 13 17 19 101 103 107 109
109 107 101 103 17 11 13 19
如果你愿意,你可以开始格式化(%3d
而不是 %d
会工作).
You could tart up the formatting if you wished (%3d
instead of %d
would work).
有时,您应该访问 typedef
指针;简短的回答是否",如果由我决定,我将使用 typedef struct Tree Tree;
和 typedef struct List List;
而不是指针 typedefs 在全部.
Sometime, you should visit Is it a good idea to typedef
pointers; the short answer is 'No' and were it up to me, I'd be using typedef struct Tree Tree;
and typedef struct List List;
and not the pointer typedefs at all.
这篇关于将二叉树转换为链表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!