C中的二叉搜索樹

Question

我是一個Python傢伙。學習C語言，我一直試圖在C中實現二叉搜索樹。我寫下了代碼，並且我一直試着從幾個小時，但不能按預期得到輸出。請幫忙！

請糾正我。

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

typedef int ElementType; 

typedef struct TreeNode { 
    ElementType element; 
    struct TreeNode *left, *right; 
} TreeNode; 

TreeNode *createTree(){ 
    //Create the root of tree 
    TreeNode *tempNode; 
    tempNode = malloc(sizeof(TreeNode)); 
    tempNode->element = 0; 
    tempNode->left = NULL; 
    tempNode->right = NULL; 
    return tempNode; 
} 

TreeNode *createNode(ElementType X){ 
    //Create a new leaf node and return the pointer 
    TreeNode *tempNode; 
    tempNode = malloc(sizeof(TreeNode)); 
    tempNode->element = X; 
    tempNode->left = NULL; 
    tempNode->right = NULL; 
    return tempNode; 
} 

TreeNode *insertElement(TreeNode *node, ElementType X){ 
    //insert element to Tree 
    if(node==NULL){ 
     return createNode(X); 
    } 
    else{ 
     if(X < node->element){ 
      node->left = insertElement(node->left, X); 
     } 
     else if(X > node->element){ 
      node->right = insertElement(node->right, X); 
     } 
     else if(X == node->element){ 
      printf("Oops! the element is already present in the tree."); 
     } 
    } 
} 

TreeNode *displayTree(TreeNode *node){ 
    //display the full tree 
    if(node==NULL){ 
     return; 
    } 
    displayTree(node->left); 
    printf("| %d ", node->element); 
    displayTree(node->right); 
} 

main(){ 
    //pointer to root of tree #2 
    TreeNode *TreePtr; 
    TreeNode *TreeRoot; 
    TreeNode *TreeChild; 

    //Create the root of tree 
    TreePtr = createTree(); 

    TreeRoot = TreePtr; 

    TreeRoot->element = 32; 
    printf("%d\n",TreeRoot->element); 

    insertElement(TreeRoot, 8); 
    TreeChild = TreeRoot->left; 
    printf("%d\n",TreeChild->element); 

    insertElement(TreeRoot, 2); 
    insertElement(TreeRoot, 7); 
    insertElement(TreeRoot, 42); 
    insertElement(TreeRoot, 28); 
    insertElement(TreeRoot, 1); 
    insertElement(TreeRoot, 4); 
    insertElement(TreeRoot, 5); 

// the output is not as expected :(
    displayTree(TreeRoot); 
} 

Answer 1

問題在於插入。如果node是NULL，則創建一個新節點並將其返回。但是如果節點不是NULL。您正在對右/左子樹進行正確更改，但是您沒有返回任何內容。

變化

if(X < node->element){ 
    node->left = insertElement(node->left, X); 
} 
else if(X > node->element){ 
    node->right = insertElement(node->right, X); 
} 

到：

if(X < node->element){ 
    node->left = insertElement(node->left, X); 
    return node; // add this. 
} 
else if(X > node->element){ 
    node->right = insertElement(node->right, X); 
    return node; // add this. 
} 

Answer 2

您的insertElement並不總是返回一個值。這就是爲什麼你的遞歸調用出錯。告訴你的編譯器警告你類似的錯誤（例如，在gcc上，使用-Wall）。

displayTree有一個類似的錯誤，當它被指定返回一個TreeNode*時什麼也不返回。

main也應該返回一個值（或者你應該聲明它的void）。