问题描述

关于c语言二叉树的问题，求大神解答，急

这是一段关于二叉树的代码。*list_from_tree这个函数是用来建立二叉树的，但我不太懂它是如何建立二叉树的，求大神详细解释。

#include
#include

typedef struct tnode Tnode;
struct tnode{
Tnode *left;
Tnode *right;

int data;

};

Tnode *new_tnode(int data);
void print_tree(Tnode *tree, int depth);
void free_tree(Tnode *tree);

typedef struct lnode Lnode;
struct lnode{
Lnode *next;
int data;
};

Lnode *new_node(int data);
void print_list(Lnode *list);
void free_list(Lnode *list);

Lnode *list_from_tree(Tnode *root, Lnode *list);

int main(int argc, char *argv[]){
Tnode *root = new_tnode(6);
root->left = new_tnode(5);
root->right = new_tnode(8);
root->right->left = new_tnode(7);
root->right->right = new_tnode(9);

Lnode *list = list_from_tree(root, NULL);

print_tree(root, 0);
printf("n");
print_list(list);

free_list(list);
free_tree(root);
return EXIT_SUCCESS;

}

Lnode *new_node(int data){
Lnode *new = malloc(sizeof(Lnode));
new->next = NULL;
new->data = data;
return new;
}

Tnode *new_tnode(int data){
Tnode *new = malloc(sizeof(Tnode));
new->left = NULL;
new->right = NULL;
new->data = data;
return new;
}

void print_tree(Tnode *tree, int depth){
if(tree != NULL){
printf("(");
print_tree(tree->left, depth+1);
if(tree->left == NULL){
printf("x");
}
printf("<-");
printf("%d", tree->data);
printf("->");
if(tree->right == NULL){
printf("x");
}
print_tree(tree->right, depth+1);
printf(")");
}
}

void print_list(Lnode *list){
Lnode *curr = list;
while(curr != NULL){
printf("%d -> ", curr->data);
curr = curr->next;
}
printf("xn");
}

void free_tree(Tnode *tree){
if(tree != NULL){
free_tree(tree->left);
free_tree(tree->right);
free(tree);
}
}

void free_list(Lnode *list){
Lnode *curr = list;
Lnode *tmp;
while(curr != NULL){
tmp = curr;
curr = curr->next;
free(tmp);
}
}

Lnode *list_from_tree(Tnode *root, Lnode *list){
if(root == NULL){
return list;
}

Lnode *right = list_from_tree(root->right, list);
Lnode *new = new_node(root->data);

new->next = right;

Lnode *left = list_from_tree(root->left, new);
return left;

}

解决方案

你理解错了，listfromtree是根据二叉树得到一个链表，不是构建二叉树。用的办法就是简单的递归，把找到的插入链表尾部。

解决方案二：

在结构体内建一个List，然后就灵活的运用指针来访问、遍历孩子节点，最后再外层加一些约束条件，大概就是这样，多看看C语言的指针，你就懂了吧