Binäre Suche Baum in C

Question

Ich bin ein Kerl Python. C Sprache zu lernen, und ich habe versucht, binären Suchbaum zu implementieren in C. ich den Code notiert hat, und ich habe von einigen Stunden versucht, aber nicht in der Lage, die Ausgabe zu erhalten, wie erwartet. Bitte Hilfe!

Bitte korrigieren Sie mich.

#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

Das Problem ist in der Insertion. Wenn node ist NULL erstellen Sie einen neuen Knoten und gibt es zurück. Aber was, wenn der Knoten nicht NULL. Sie sind richtig, Änderungen an den rechten / linken Unterbaum zu machen, aber sie sind nicht alles zurück.

Ändern

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

zu:

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

Ihre insertElement kehrt nicht immer einen Wert. Deshalb ist Ihre rekursive Aufrufe schief gehen. Lassen Sie Ihre Compiler Sie über Fehler, so warnen (zum Beispiel auf gcc, Verwendung -Wall).

displayTree hat einen ähnlichen Fehler, nichts zurückkehrt, wenn es angegeben ist eine TreeNode* zurückzukehren.

main sollte auch einen Wert zurückgeben (oder sollten Sie erklären es void).