在二叉樹中插入元素

Question

該代碼用於使用級別遍歷在二叉樹中插入元素。我會先告訴你它是如何工作的。它首先遍歷每個級別的節點，如果有任何節點沒有兩個子節點，則將該節點作爲子節點插入該節點，並使用隊列存儲和檢索節點地址。我的問題是，每次我調用create函數時，即使在插入節點後，根值仍未更改，傳遞的根值始終爲空，並且它仍然爲空。我無法弄清楚這有什麼問題。誰能幫我嗎？

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

struct node 
{ 
    int data; 
    struct node *left,*right; 
}*root; 

struct queue 
{ 
    int capacity,rear,front; 
    struct node **qu; 
}; 


void enqueue(struct queue *q,struct node *n) 
{ 
    q->front=(++(q->front))%q->capacity; 
    (q->qu)[q->front]=n; 
    if(q->rear==-1) 
    q->rear++; 
} 

struct node* dequeue(struct queue *q) 
{ 
    struct node *temp; 
    temp=q->qu[q->rear]; 
    if(q->front==q->rear) 
    q->front=q->rear=-1; 
    else 
    q->rear=(++(q->rear))%q->capacity; 
} 

int isempty(struct queue *q) 
{ 
    return(q->rear==-1); 
} 

struct queue* create(unsigned int capacity) 
{ 
    struct queue *p; 
    p=(struct queue*)malloc(sizeof(struct queue)); 
    p->capacity=capacity; 
    p->front=p->rear=-1; 
    p->qu=(struct node**)malloc(sizeof(struct node)*capacity); 
    return p; 
} 


void insert(struct node *root) 
{ 
    int n; 
    struct node *p,*q; 
    struct queue *tmp; 
    p=(struct node*)malloc(sizeof(struct node)); 
    p->left=p->right=NULL; 
    scanf("%d",&n); 
    p->data=n; 
    if(root==NULL) 
    { 
     root=p; 
     return; 
    } 
    tmp=create(20); 
    enqueue(tmp,root); 
    while(isempty(tmp)) 
    { 
     q=dequeue(tmp); 
     printf("%d %d\n",p,root); 
     if((!q->right)||(!q->left)) 
     { 
      if(!q->right) 
      q->right=p; 
      else 
      q->left=p; 
      return; 
     } 
     else 
     { 
     enqueue(tmp,q->left); 
     enqueue(tmp,q->right); 
     } 
    } 
} 

void traverse(struct node *root) 
{ 
    if(!root) 
    return; 
    traverse(root->left); 
    printf("%d ",root->data); 
    traverse(root->right); 
} 

void main() 
{ 
    int i,n; 
    while(1) 
    { 
     printf("1.insert\n2.exit\n"); 
     scanf("%d",&n); 
     switch(n) 
     { 
      case 2:goto end; 
      case 1:insert(root); 
     } 
    } 
    end: 
    traverse(root); 
} 

謝謝。

Answer 1

您已將root定義爲全局變量，但您的插入函數還定義了它自己的本地版本root，該版本優先。因爲你通過值而不是參考root，改變它的值沒有效果。你有兩個選擇來解決這個問題。

• 通root參照

您更改插入是void insert(struct node **root)，然後用(*root)取代的root所有實例功能。您還需要當你調用它的指針傳遞給根 - insert(&root)

• 返回root

改變返回類型的新值struct node *並確保您return root末和在任何時候你已經從函數返回。當你給它打電話時，你會將返回值分配給root，如root=insert(root)

兩者都是同樣有效的選項。