logo标签列表

使用一个元素数组创建二叉树

cbinary-tree
3

所以我正在尝试使用给定的数组创建一个二叉树，然后按顺序、前序和后序打印结果，但似乎我在某个地方犯了一个错误，但就我所看到的情况来看，一切应该没问题。

这是它打印出来的结果。

1 2 3 4 5 6 7 8 9 10  #inorder
10 9 8 7 6 5 4 3 2 1  #postorder
1 2 3 4 5 6 7 8 9 10  #preorder

这是我目前做的。有人能指出错误并给予修复建议吗？
#include <stdio.h>
#include <stdlib.h>

typedef struct node_s node_t;
struct node_s
{
    int key;
    node_t *left,*right;
};
node_t *new_node(int val)
{
    node_t *new;
    new= malloc(sizeof (node_t));
    if(new==NULL)
    {
        exit(1);
    }
    new->key=val;
    new->left=NULL;
    new->right=NULL;
    return new;
}
void print_inorder(node_t *root)
{
    node_t *new=root;
    if (new != NULL) {
        print_inorder(new->left);
        printf("%d ",new->key);
        print_inorder(new->right);
    }
    return;

}
void print_postorder(node_t *root)
{
    node_t *new=root;
    if (new != NULL) {
        print_postorder(new->left);
        print_postorder(new->right);
        printf("%d ",new->key);
    }
    return;

}
void print_preorder(node_t *root)
{
    node_t *new=root;
    if (new != NULL) {
        printf("%d ",new->key);
        print_preorder(new->left);
        print_preorder(new->right);
    }
    return;

}
node_t *insert_node(node_t *root,int val)
{
     if(root==NULL)
            return new_node(val);
     else
     {
         if(val<root->left)
             root->left= insert_node(root->left,val);
         else if(val>root->left)
             root->right= insert_node(root->right,val);
     }
    return root;
}
int main() {

    int n;
    int v[]={1,2,3,4,5,6,7,8,9,10};
    node_t *root=NULL;
    FILE *file;
    file= fopen("file","r");
    if(file==NULL)
    {
        exit(1);
    }
    for (int i = 0; i < 10; ++i) {
        root= insert_node(root,v[i]);
    }

    print_inorder(root);
    printf("\n");
    print_postorder(root);
    printf("\n");
    print_preorder(root);

    return 0;
}
1
从输出来看，你的代码似乎创建了一个链表。 - user3386109
1
我只是粗略地浏览了代码，但我看过的部分似乎还可以。话虽如此，让我指出来的是，保持树的平衡占了99%的工作量。 - user3386109
1
我只是粗略地看了一下代码，但我看过的部分似乎还可以。话虽如此，让我指出来的是，保持树的平衡占了99%的工作量。 - user3386109
1
@user3386109 好的，说得对。但是现在我只是在努力适应二叉树，稍后再来处理平衡问题，不过我会听取你的建议。 - Severjan Lici
1
请注意，通过对 v[] 数组进行排序，您将不会在 root 节点上有一个左分支。所有数据都存储在 root 的右分支上。尝试使用未排序的输入，例如 int v[] = { 5, 6, 7, 8, 9, 0, 1, 2, 3, 4 };（或类似的输入）。您明白为什么您当前已排序的 v[] 只填充了树的右分支吗？ - David C. Rankin
显示剩余21条评论
3个回答
2

节省时间，启用所有编译器警告。

问题在几秒钟内被发现！
代码至少有这个问题：

整数和指针之间的比较

// warning: comparison between pointer and integer
if (val < root->left) // Bad

可能需要的内容：

if (val < root->key)

同样地，使用else if (val > root->left)。
2
如果你的目标是从一个排序数组构建一个平衡二叉树，你可以尝试以下递归策略：
node_t* createBinaryTree(int* items, size_t count) {
    size_t mid = count/2;
    node_t* newNode = NULL;

    if (count == 0) {
        return NULL;
    }

    newNode = new_node(items[mid]);

    if (count > 1) {
        newNode->left = createBinaryTree(items, mid);
        newNode->right = createBinaryTree(items+mid+1, count-mid-1);
    }

    return newNode;
}

然后，您可以按照以下步骤创建树：
int v[]={1,2,3,4,5,6,7,8,9,10};
size_t count = sizeof(v)/sizeof(*v); // 10
node_t* root = createBinaryTree(v, count);

如果数组还没有排序，你可以使用标准的C库函数qsort来进行排序，具体步骤如下：
qsort(v, count, sizeof(*v), compareFunction)

在调用createBinaryTree之前，需要先定义一个名为compareFunction的函数，其形式如下：
int compareFunction(const void *p1, const void *p2) {
    int v1 = *(int*)p1;    
    int v2 = *(int*)p2;
    return (v1 - v2);
}
真的很喜欢你的方法。候选简化版本：node_t* createBinaryTree(int *items, size_t count) { node_t *newNode = NULL; if (count > 0) { size_t mid = count / 2; newNode = new_node(items[mid]); newNode->left = createBinaryTree(items, mid); newNode->right = createBinaryTree(items + mid + 1, count - mid - 1); } return newNode; } ` - chux - Reinstate Monica
真的很喜欢你的方法。候选简化：node_t* createBinaryTree(int *items, size_t count) { node_t *newNode = NULL; if (count > 0) { size_t mid = count / 2; newNode = new_node(items[mid]); newNode->left = createBinaryTree(items, mid); newNode->right = createBinaryTree(items + mid + 1, count - mid - 1); } return newNode; }` - chux - Reinstate Monica
小问题：v1 - v2 的风险溢出。 (v1 &gt; v2) - (v1 &lt; v2) 总是有效的。 - chux - Reinstate Monica
小问题：v1 - v2 的风险溢出。(v1 > v2) - (v1 < v2) 总是有效的。 - chux - Reinstate Monica
-1
我的答案似乎能够创建任何类型的二叉树。
如果有人能告诉我我的答案存在问题的地方，我会很乐意进行修正。
#include <stdio.h>
#include <stdlib.h>

typedef struct node_s node_t;
struct node_s
{
    char key;
    node_t *left,*right;
};


/*
node_t *new_node(char val)
{
    node_t *new;
    new= malloc(sizeof (node_t));
    if(new==NULL)
    {
        exit(1);
    }
    new->key=val;
    new->left=NULL;
    new->right=NULL;
    return new;
}
*/


void ClearTree(node_t** root)
{ 
    if(*root) 
    {
        if((*root)->left)
        {
            ClearTree(&(*root)->left);
        }
        if((*root)->right) 
        {
            ClearTree(&(*root)->right); 
        }

        free(*root);
        *root=NULL;
    }
}

void print_inorder(node_t *root)
{
    node_t *new=root;
    if (new == NULL)
       return;
    print_inorder(new->left);
    printf("%c ",new->key);
    print_inorder(new->right);

}
void print_postorder(node_t *root)
{
    node_t *new=root;
    if (new == NULL)
        return;
    print_postorder(new->left);
    print_postorder(new->right);
    printf("%c ",new->key);
    

}
void print_preorder(node_t *root)
{
    node_t *new=root;
    if (new == NULL)
        return;
    printf("%c ",new->key);
    print_preorder(new->left);
    print_preorder(new->right);
    

}
void CreateTree(node_t** root)
{
    char v[]={'A','B','#','D','#','#','C','#','#'};
    static int i = 0;
    if(v[i] == '#'){
        *root = NULL;
        i++;
    }
    else{
        *root = (node_t*)malloc(sizeof(node_t));
        if(NULL == *root){
            printf("No space\n");
            exit(1);
        }
        (*root)->key = v[i];
        i++;
        CreateTree(&(*root) -> left);
        CreateTree(&(*root) -> right);
    }
}
int main() {

    node_t *root=NULL;
    
//    FILE *file;
//    file= fopen("file","r");
//    if(file==NULL)
//    {
//        exit(1);
//    }    

    CreateTree(&root);

    printf("preorder:  ");
    print_preorder(root);
    printf("\n");

    printf("inorder:   ");
    print_inorder(root);
    printf("\n");

    printf("postorder: ");
    print_postorder(root);
    printf("\n");

    ClearTree(&root);

    return 0;
}

运行它将输出：
preorder:  A B D C 
inorder:   B D A C 
postorder: D B C A

作为数字，请参见下面的代码：
#include <stdio.h>
#include <stdlib.h>

typedef struct node_s node_t;
struct node_s
{
    char key;
    node_t *left,*right;
};


/*
node_t *new_node(char val)
{
    node_t *new;
    new= malloc(sizeof (node_t));
    if(new==NULL)
    {
        exit(1);
    }
    new->key=val;
    new->left=NULL;
    new->right=NULL;
    return new;
}
*/


void ClearTree(node_t** root)
{ 
    if(*root) 
    {
        if((*root)->left)
        {
            ClearTree(&(*root)->left);
        }
        if((*root)->right) 
        {
            ClearTree(&(*root)->right); 
        }

        free(*root);
        *root=NULL;
    }
}

void print_inorder(node_t *root)
{
    node_t *new=root;
    if (new == NULL)
       return;
    print_inorder(new->left);
    printf("%d ",new->key);
    print_inorder(new->right);

}
void print_postorder(node_t *root)
{
    node_t *new=root;
    if (new == NULL)
        return;
    print_postorder(new->left);
    print_postorder(new->right);
    printf("%d ",new->key);
    

}
void print_preorder(node_t *root)
{
    node_t *new=root;
    if (new == NULL)
        return;
    printf("%d ",new->key);
    print_preorder(new->left);
    print_preorder(new->right);
    

}
void CreateTree(node_t** root)
{
    int v[]={1,2,4,8,'#','#',9,'#','#',5,10,'#','#','#',3,6,'#','#',7,'#','#'};
    static int i = 0;
    if(v[i] == '#'){
        *root = NULL;
        i++;
    }
    else{
        *root = (node_t*)malloc(sizeof(node_t));
        if(NULL == *root){
            printf("No space\n");
            exit(1);
        }
        (*root)->key = v[i];
        i++;
        CreateTree(&(*root) -> left);
        CreateTree(&(*root) -> right);
    }
}
int main() {

    node_t *root=NULL;
    
//    FILE *file;
//    file= fopen("file","r");
//    if(file==NULL)
//    {
//        exit(1);
//    }    

    CreateTree(&root);

    printf("preorder:  ");
    print_preorder(root);
    printf("\n");

    printf("inorder:   ");
    print_inorder(root);
    printf("\n");

    printf("postorder: ");
    print_postorder(root);
    printf("\n");

    ClearTree(&root);

    return 0;
}

运行它将输出
preorder:  1 2 4 8 9 5 10 3 6 7 
inorder:   8 4 9 2 10 5 1 6 3 7 
postorder: 8 9 4 10 5 2 6 7 3 1
我并不是你的反对票，但是我从未听说过在基本二叉树中添加一个特殊字符来标记节点终止。（是的，在更特殊的树结构中，比如前缀搜索中的三叉搜索树中可能会有用，但是在基本树中并不需要）。你能提供一份参考或引用的来源吗？ - David C. Rankin
@DavidC.Rankin 你能理解中文吗？我的信息是来自中文的引用或引证。我是中国人。我认为我的答案是正确的，可以得到正确的结果。我不明白为什么有人会对我的答案投下反对票，当我相信我的答案是正确的时候。 - Tom
@DavidC.Rankin 你懂中文吗？我的信息来源或引用来自中文。我是中国人。我认为我的答案是正确的，可以得到正确的结果。我不明白为什么有人会对我的答案投反对票，当我相信我的答案是正确的时候。 - Tom
谢谢你的跟进。我并没有冒犯的意思。我只是真诚地好奇想知道你所指的是什么。再次声明，我不是你的反对者。 - David C. Rankin
@DavidC.Rankin 虽然添加一个特殊字符作为终止节点可能看起来有些粗糙，但我觉得它可以解决这个问题。有一句话说“无论猫是黑色还是白色，只要能抓住老鼠就行。” - Tom
显示剩余6条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接