c - 如何将 Child 和 Child 添加到现有节点？

Question

我有以下 C 程序，它将节点添加到树中，然后用户可以选择排序方法。如何修改程序以允许我向每个节点添加 LChild 和 RChild？非常感谢任何帮助，因为我对 BST 完全陌生。

写这个是因为显然我的帖子主要是代码

代码:

#include <stdio.h>
#include <stdlib.h>

struct treenode {
    struct treenode *lchild;
    struct treenode *rchild;
    int data;
    } *root = NULL;

void insertnode(struct treenode **pp,int d)
{
    for( ;*pp; )
    {
         if (d < (*pp)->data) pp = &(*pp)->lchild;
         else  pp = &(*pp)->rchild;
    }
    *pp = malloc (sizeof **pp);
    (*pp)->data = d;
    (*pp)->lchild = NULL;
    (*pp)->rchild = NULL;
}

void preorder(struct treenode *p)
{
    if(p==NULL)
    {
        printf("\nThe list is empty");
        return;
    }

    printf("%d,",p->data);
    if (p->lchild) preorder(p->lchild);
    if (p->rchild) preorder(p->rchild);
}

void postorder(struct treenode *p)
{
    if(p==NULL)
    {
        printf("\nThe list is empty");
        return;
    }

    if (p->lchild) preorder(p->lchild);
    if (p->rchild) preorder(p->rchild);
    printf("%d,",p->data);
}
void inorder(struct treenode *p)
{
    if(p==NULL)
    {
        printf("\nThe list is empty");
        return;
    }

    if (p->lchild) preorder(p->lchild);
    printf("%d,",p->data);
    if (p->rchild) preorder(p->rchild);
}

int main(void)
{
    root=NULL;
    int choice,data;

    while(1)
    {
     printf("\nPress 1 for inserting a node in BST fashion: ");
     printf("\nPress 2 for traversing the tree in preorder fashion :");
     printf("\nPress 3 for traversing the tree in postorder fashion :");
     printf("\nPress 4 for traversing the tree in inorder fashion :");
     printf("\nPress 5 to exit :");


     printf("\nEnter your choice: ");
     scanf("%d", &choice);

    switch(choice)
    {
    case 1: printf("\nEnter the data to be inserted:");
        scanf("%d",&data);
        insertnode( &root,data);

        break;

    case 2: preorder(root);
        break;

    case 3: postorder(root);
        break;

    case 4: inorder(root);
        break;

    case 5: exit(0);
        break;
    default: printf("\nYou have entered an invalid choice. Please try     again");
    }
}

return 0;
}

Answer 1

当一个新值添加到 BST 时，它会检查条件，如果值“>”当前节点值，则我们移动到该节点的右子节点，如果值“<”则我们移动到左侧节点的子节点，我们这样做直到到达叶节点。

对于您的情况，只需将条件更改为 while 条件并检查它是否有效。

void insertnode(struct treenode **pp,int d)
{
    while((*pp)->data == NULL)
    {
       if (d < (*pp)->data) 
         pp = &(*pp)->lchild;

       else  
         pp = &(*pp)->rchild;
    }
      *pp = malloc (sizeof **pp);
      (*pp)->data = d;
      (*pp)->lchild = NULL;
     (*pp)->rchild = NULL;
}