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）。