c - 在 C 中使用递归添加到完全二叉树

Question

我正在尝试学习递归，所以我尝试了一个程序来创建一个完整的二叉树，然后打印其所有元素的总和，我自己编写了插入部分，我对我的指针变量 "curr 感到困惑" 指向一个树节点，为什么我能够执行 "curr = curr->left" 因为它只是一个指向节点的指针。不应该只有实际的树节点包含这些左字段和右字段吗？请给我一个关于这个新手疑问的提示。但我很惊讶我的程序能完成这项工作。

谢谢:)

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

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

struct node *head = NULL;
struct node *curr = NULL;

void insert_Data(int val,struct node* curr){
    struct node *tempnode = (struct node*)malloc(sizeof(struct node));
    tempnode->data = val;
    tempnode->left = NULL;
    tempnode->right = NULL;
    if(head==NULL){
        head = tempnode;
        curr = head;
        printf("head element is : %d\n",head->data);
    }
    else{
        if(curr->left == NULL){
            curr->left = tempnode;
        }
        else if(curr->right == NULL){
            curr->right = tempnode;
        }
        else{
            curr = curr->left;
            insert_Data(val,curr);
        }
    }
}

//to test program
int sumNode(struct node* root ) {
  // if there is no tree, its sum is zero
  if( root == NULL ) {
    return 0 ;

  } else { // there is a tree
   printf("element is = %d\n",root->data);
    return root->data + sumNode( root->left ) + sumNode( root->right ) ;
  }
}

int main() {
    int arr[] = {1,2,3,4,5,6,7,8,9};
    int i;
    for(i=0;i<9;i++){
        insert_Data(arr[i],head);
    }
    int result = sumNode(head);
    printf("\n\n%d",result);
    return 0;
}

Answer 1

有关箭头运算符 -> 的含义，请参阅此相关问题 Arrow operator (->) usage in C .

关于问题标题，我建议采用递归插入方法，该方法遵循根入，根出模式:

// in: the value to be inserted as new node
//     the head of the sub-tree that should contain the new node
// out: the new head of the subtree
struct node* insert_Data(int val, struct node* subtreeRoot);

只要您不重新平衡树，这基本上会导致以下行为:任何有效的 subtreeRoot 输入都会返回自身，并在树层次结构中的某处添加新值和 NULL 输入将返回新创建的节点作为输出。

struct node* insert_Data(int val, struct node* subtreeRoot)
{
    if (subtreeRoot == NULL)
    {
        struct node *tempnode = (struct node*)malloc(sizeof(struct node));
        tempnode->data = val;
        tempnode->left = NULL;
        tempnode->right = NULL;
        return tempnode;
    }
    else if (val < subtreeRoot->data)
    {
        subtreeRoot->left = insert_Data(val, subtreeRoot->left);
    }
    else // val is bigger than the subtree root data
    {
        subtreeRoot->right = insert_Data(val, subtreeRoot->right);
    }
    return subtreeRoot;
}

使用如下:

head = insert_Data(arr[i], head);

目前，返回值仅有助于将 NULL 比较保留在一个位置。但如上所述，这种签名和用法还允许使用许多更复杂的插入方法，其中子树结构在插入时完全改变。