添加到一个完整的二叉树使用递归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。

关于问题的标题，我建议递归insert方法，即遵循，深挖模式的根：

// 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); 

只要你不重新平衡树，这将基本上导致一种行为，其中任何有效的输入将自行返回，并在树层次结构下添加新值，并且输入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比较在一个地方。但正如所说的，这个签名和用法还允许更复杂的插入方法，其中子树结构在插入时完全更改。