好吧，我试图从一个给定的输入创建一个不平衡的二叉搜索树，作为一个（未排序的）整数序列。
我的方法是递归地为每个节点找到正确的位置，然后为其分配内存并为其定义数据。
但我无法有效地调试程序，因为尽管我仔细检查过它，但似乎无法确定问题所在。
输入如下：
所以对于输入：
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("%d\n",&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: %d\n",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;
}
最佳答案
我认为，问题出在void createNode(Node* root,int key)函数中。变量Node* root是函数的局部变量。因此，这些变化不会反映在createNode()之外。
仅供参考，C使用传递值传递函数参数。
所以，要么你必须return从root中新分配的createNode()并将其收集到调用者中。您还需要将createNode()函数的返回类型更改为Node *（或void *，至少）。
或
使用指向Node *的指针作为createNode()中的参数
重要提示：使用完后，始终free()分配的内存。否则，会导致内存泄漏。
关于c - 无法创建二进制搜索树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29165479/