添加到一個完整的二叉樹使用遞歸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比較在一個地方。但正如所說的，這個簽名和用法還允許更復雜的插入方法，其中子樹結構在插入時完全更改。