2

我只是想编写一个简单的二叉搜索树程序，用户可以在其中插入节点并以中序、前序或后序模式查看树中的所有节点。我的代码是

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

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

void insertnode(struct treenode *p,int d)
{
    if(p==NULL)
    {
         // means the tree is empty
         p=(struct treenode *)malloc(sizeof(struct treenode));
         p->data=d;
         p->lchild=NULL;
         p->rchild=NULL;
    }

    else
    {
         // start comparing the new data from root
         if( d<p->data )
             insertnode((&(p->lchild)),d);

        else
             insertnode((&(p->lchild)),d);
    }
}

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

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

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

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

void inorder(struct treeode *p)
{
    if(p==NULL)
    {
        printf("\nThe list is empty");
    }

    else
    {
        preorder(p->lchild);
        printf("%d",p->data);
        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 enetred an invalid choice. Please try again");
    }
}

return 0;
}

有一堆错误信息说

dereferencing pointer to incomplete type

问题是什么 ？另外我对双间接指针不太满意，所以有人可以解释一下我如何传递和检索双间接指针（如果我需要在上面的程序中传递它们）。

4

2 回答 2

6

以下只是编译错误，因此请修复这些错误，您的程序将编译。

问题＃1：
您将结构定义为：

struct treenode
{
    /* Blah blah... */
} *root;  /* Mistake: should be root, not *root */

相反，命名它root，而不是*root。


问题2：
你insertnode()打错了。而不是这个：

insertnode((&(p->lchild)),d);  /* Mistake: taking the address of the pointer */

你应该这样称呼它：

insertnode(p->lchild,d);


问题#3：
你定义错误：rootmain()

root = NULL;  /* Mistake: root is implicitly declared as int */

你应该做的是：

struct treenode* root = NULL;


问题#4：

您的声明中有错字inorder()：

void inorder(struct treeode *p)  /* Typo: should be treenode and not treeode */

它应该是：

void inorder(struct treenode *p)

下一组问题是程序中的逻辑错误：

问题#5：你总是在左节点中插入一个新
值。您应该将任一递归调用更改为：insertnode()dinsertnode(p->lchild, d);

insertnode(p->rchild, d);

取决于你想如何组织你的树。


问题 #6：
就像 AndersK 指出的那样，传递的指针root在传递给 之后永远不会改变insertnode()，所以这是一个主要错误。

在您的情况下，当您想要更改传递的指针本身（即指向另一个地址）而不更改指针对象本身时，需要使用双重间接指针。

您想在root内部进行更改insertnode()，因此添加另一层间接并传递ieroot的地址，以便根也可以在函数内更改。 &root

相应的，声明insertnode()应该是：

insertnode(struct treenode** p, int d)
于 2012-07-16T09:02:29.543 回答
1

为了让您更改指针指向的数据，您需要提供更多的间接级别

例如你写

insertnode(root,data);

但是 root 在开始时被设置为 NULL 并且不能在 insertnode 内以您将其提供给函数的方式进行更改。

而是将 insertnode 声明为

insertnode(struct treenode **p,int d)

并调用 insertnode

insertnode(&root, data);
于 2012-07-16T09:14:48.553 回答