首页 文章

C编程二进制树递归插入（非二进制搜索树）

提问于
浏览 次
0

这是我的代码 . 我想以递归方式将项插入二叉树中 . 它不是二叉搜索树（左子不需要<父或右子不需要>父） .

它只是一个二叉树，每个节点最多可以有两个子节点 . 当我执行遍历时，它只是在无限循环中无限地打印出起始节点（5-> 5-> 5 - > ....） . 请帮帮我 .

我搜索了Stack Overflow并没有基于此 . 大多数是二叉搜索树 . 如果这是一个糟糕的问题，我很抱歉 .

struct node {
    int info;
    struct node* left;
    struct node* right;
}*temp, *ptr, *prev;

struct node *root, *start=NULL;

void insert(struct node*);
void inorder(struct node*);

void insert(struct node* ptr)
{
    int ch;

    if(start==NULL)  // if start is null, new node is made as start node.
        start=ptr;
    else
    {
        temp=(struct node*)malloc(sizeof(struct node)); //new node created
        temp->left=NULL;
        temp->right=NULL;
        puts("Enter value");
        scanf("%d", &temp->info);
        ptr=temp;     //ptr is set as new node
    }

    printf("Does %d have a left node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        if(ptr==start)
            insert(start->left); //start->left will be the new 'ptr' in the next insertion scenario
        else
            insert(ptr->left);  //same principle as above
    }

    printf("Does %d have a right node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        if(start==ptr)
            insert(start->left);
        else
            insert(ptr->right);
    }

}

void inorder(struct node* ptr)
{
    while(ptr!=NULL)
    {
        inorder(ptr->left);
        printf("%d -> ", ptr->info);
        inorder(ptr->right);
    }
}

void main(){
    int ch;
    do{
        puts("1. Insert 2.Traverse 3.Exit");
        scanf("%d",&ch);
        switch(ch){
            case 1:
                puts("Enter root node");
                root=(struct node *)malloc(sizeof(struct node));
                root->left=NULL;
                root->right=NULL;
                scanf("%d", &root->info);
                insert(root);
                break;
            case 2:
                inorder(start);
        }
    }while(ch!=3);
}

先谢谢你，伙计们 .

c binary-tree insertion

3 回答

  • 0

    尝试这种添加节点的方式：

    struct node *createTree()
{
    struct node *node;
    int resp;

    node=malloc(sizeof(struct node)); //new node created
    node->left=NULL;
    node->right=NULL;
    puts("Enter value");
    scanf("%d", &node->info);

    printf("Does %d have a left node? (1/0)\n", node->info);
    scanf("%d", &resp);
    if(resp==1)
        node->left = createTree();

    printf("Does %d have a right node? (1/0)\n", node->info);
    scanf("%d", &resp);
    if(resp==1)
        node->right = createTree();

    return node;
}

    然后在 main() 做：

    root = createTree();

    请注意，如果使用 "%d" 格式扫描 resp 变量，则该变量的类型为 int . 对于 char 类型，您应该使用格式 "%c" .

    回复于
  • 2

    你的遍历创建无限循环，你应该将 while 更改为 if

    void inorder(struct node* ptr)
{
    if (ptr != NULL)
    {
        inorder(ptr->left);
        printf("%d -> ", ptr->info);
        inorder(ptr->right);
    }
}

    在 insert(struct node* ptr) 当你执行 ptr=temp; 时它只是在函数范围内改变ptr，所以实际上你从不为根分配左右节点

    回复于
  • 0

    我找到了解决方案 . 抱歉浪费你的时间 . 我的代码的问题是：

    1）while而不是if在遍历函数中2）其次，当我传递参数ptr时，它不知道将ptr链接到何处 . 我所做的一切都是ptr = temp . 它必须链接到前一个节点的左/右，对吗？

    @ huxley对函数范围的解释是错误的 . 它必须指向同一个对象 - 这就是我们使用指针的原因，对吧？然而，它敲响了我的脑袋 . 所以这是下面的解决方案：

    void insert(struct node* ptr, int side)
{
    int ch;

    if(start==NULL)  // if start is null, new node is made as start node.
        start=ptr;
    else
    {
        temp=(struct node*)malloc(sizeof(struct node)); //new node created
        temp->left=NULL;
        temp->right=NULL;
        puts("Enter value");
        scanf("%d", &temp->info);
        ptr=temp;
        if(side==1)
            prev->left=ptr;
        else
            prev->right=ptr;
    }

    printf("Does %d have a left node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        insert(ptr->left, 1);
    }

    printf("Does %d have a right node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        insert(ptr->right, 2);
    }

}

void inorder(struct node* ptr)
{
    if(ptr!=NULL)
    {
        inorder(ptr->left);
        printf("%d -> ", ptr->info);
        inorder(ptr->right);
    }
}

    我详细解释了它，因为使用递归没有适当的二叉树插入代码 . 我希望每个人都理解 .

    谢谢所有帮助过的人 .

    干杯，阿希尔

    回复于

相关问题