c-无法创建二进制搜索树

Question

好吧，我正试图从给定的输入中创建一个不平衡的二进制搜索树，作为（未排序的）整数序列
我的方法是递归地为每个节点找到合适的位置，然后为它分配内存并定义数据。
但我无法有效地调试程序，因为尽管我仔细检查了它，但似乎无法确定问题所在。输入如下：
因此输入：

11
15 6 4 8 5 3 1 10 13 2 11

预期输出应该是post-order和in-order遍历，但奇怪的是，没有打印任何内容（除了我在两者之间给出的换行符）。

更新：
1.[2015年3月20日]-考虑到警告，删除了malloc类型转换
2.[2015年3月21日]进行了某些更改，尽管现在，代码只给出以下输出：

11 13
11 13 

这是代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define arrmax 100
/***Pointer-based BST implementation, developed by Abhineet Saxena***/
/***The data-type declaration***/
typedef struct node{
int data;
struct node* parent;
struct node* leftChild;
struct node* rightChild;
}Node;
typedef struct tree
{
    Node* root;
    int size;
}BSTree;
/***Method prototypes***/
/*Method to create a tree*/
Node* createTree(int[],int,int);
//Changed from void to Node*: void createNode(Node*,int);
Node* createNode(Node*,int);
void inOrder(Node* root);
void postOrder(Node *root);
int main(void) {
    BSTree* bs_tree;
    //Incorrect here: bs_tree=(BSTree*)malloc(sizeof(BSTree));
    bs_tree=malloc(sizeof(BSTree));
    bs_tree->root=NULL;
    bs_tree->size=0;
    /****Taking the input****/
    int num_elem,iterv;
    scanf("%dn",&num_elem);
    //Incorrect here: int *arr=(int*)malloc(sizeof(int)*(num_elem));
    int *arr=malloc(sizeof(int)*(num_elem));
    for(iterv=0;iterv<num_elem;iterv++)
    {
        scanf("%d",&arr[iterv]);
    }
    bs_tree->root=createTree(arr,0,num_elem-1);
    postOrder(bs_tree->root);
    printf("n");
    inOrder(bs_tree->root);
    return 0;
}
Node* createTree(int marr[],int left,int right)
{
    int iterv;
    Node* root;
    root=NULL;
    for(iterv=left;iterv<=right;iterv++)
    {
        //Made changes here: Old:-createNode(root,marr[iterv]);
         root=createNode(root,marr[iterv]);
    }
    return root;
}
Node* createNode(Node* root,int key)
{
    if(root==NULL)
    {
        root=malloc(sizeof(Node));
        //printf("Used malloc here for key: %dn",key);
        root->data=key;
        root->leftChild=NULL;
        root->rightChild=NULL;
        root->parent=NULL;
        //Changed here: [old]return;
        return root; 
    }
    else
    {
        if(key<root->data)
                {
                        //Added code here[Old: createNode(root->leftChild,key);]
                        if(root->leftChild!=NULL)
                            createNode(root->leftChild,key);
                       else
                       {
                           root->leftChild=createNode(root->leftChild,key);
                           return root;
                       }
                }
        else
                //Added Code here: [old codeline:-] createNode(root->rightChild,key);
                 {
                     if(root->rightChild!=NULL)
                          createNode(root->rightChild,key);
                    else
                     {
                         root->rightChild=createNode(root->rightChild,key);
                         return root;
                     }
                 }                  
    }
}
void inOrder(Node* bst_tree)
{
    if(bst_tree!=NULL)
    {
        inOrder(bst_tree->leftChild);
        printf("%d ",bst_tree->data);
        inOrder(bst_tree->rightChild);
    }
    else
        return;
}
void postOrder(Node* bst_tree)
{
    if(bst_tree!=NULL)
    {
        postOrder(bst_tree->leftChild);
        postOrder(bst_tree->rightChild);
        printf("%d ",bst_tree->data);
    }
    else
        return;
}

Answer 1

我认为问题出在void createNode(Node* root,int key)函数中。变量Node* root是函数的局部变量。因此，这些变化不会反映在createNode()之外。

仅供参考，C使用传递值传递函数参数。

所以，你要么去

1. CCD_ 5从CCD_ 7接收新分配的CCD_。您还需要将createNode()函数的返回类型更改为Node *（或void *，至少）

或

2. 使用指向Node *的指针作为createNode()中的参数

重要提示：使用完分配的内存后，始终free()。否则，会导致内存泄漏。

Answer 2

createNode()函数为节点分配内存并填充数据，但我看不到它将新节点链接到数据结构的其余部分。所有的leftChild和rightChild指针以及树root都保持为NULL。

所以堆上有很多节点，但树是空的。。。

当你在main() 中这样做时

bs_tree->root = createTree(arr,0,num_elem-1);

你也应该在createTree() 中做

root = createNode(root,marr[iterv]);

以及在createNode() 中

root->leftChild = createNode(root->leftChild,key);
root->rightChild = createNode(root->rightChild,key);

当然还有来自所有这些功能的CCD_ 21。

编辑

可能的实施：

Node* insertNode(Node* root, int value)
{
    if(root == NULL)
    {
        root = malloc(sizeof(Node));
        root->data = val;
        root->leftChild = NULL;
        root->rightChild = NULL;
    }
    else
        if(val < root->data)
            root->leftChild = insertNode(root->leftChild, val);
        else
            root->rightChild = insertNode(root->rightChild, val);
    return root;
}

Answer 3

此部分不正确：

void createNode(Node* root,int key)
{
     ...
     root=(Node*)malloc(sizeof(Node));
     ...
}

root是您的参数，更改它的值（您在其中存储另一个地址）很少是一个好主意。您必须使用指向该指针的指针：

void createNode(Node** root,int key)
{
     ...
     *root = malloc(sizeof(Node));
     ...
}

或在末尾返回新值：

Node* createNode(Node* root,int key)
{
     ...
     root = malloc(sizeof(Node));
     ...
     return root;
}