二叉树 - 解引用指针

Question

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

---

#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 

---

有什么问题的错误消息的一群？另外我对双重间接指针不太舒服，所以有人可以解释我如何传递和检索双重间接指针（如果我需要在上述程序中传递它们）。

Answer 1

以下只是编译错误，所以修复这些错误并编译您的程序。

问题＃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：
你在main()错误定义root：

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()
你总是插入一个新值d到左节点。您应该更改递归调用insertnode(p->lchild, d);的任一个：

insertnode(p->rchild, d); 

根据您想如何组织你的树。

问题＃6：
就像AndersK指出，传递指针root它被传递给insertnode()后不会改变，所以这是一个重大的错误。

在你的情况下，当你想改变传递的指针本身（即指向另一个地址）并且不改变指针本身时，双重间接指针是必须的。

你想改变root内insertnode()，因此增加一个间接的另一个层次，并通过的root地址，即&root，使根也可以在函数中被改变。

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

insertnode(struct treenode** p, int d) 

Answer 2

为了让你改变一个指针指向你需要提供间接

的一个多层次

例如数据你写

insertnode(root,data); 

但根在启动设置为NULL，不能insertnode您提供它的功能的方式改变了里面。

，而不是申报insertnode作为

insertnode(struct treenode **p,int d) 

，并呼吁insertnode与

insertnode(&root, data);