在C99中创建二叉搜索树

我有一个编程课程作业将于今晚8点CDT到期，我遇到了麻烦。 我们将通过阅读文件来获取以下数字的列表：

9 30 20 40 35 22 48 36 37 38

将它们放在一个数组中（很容易），然后使用C将它们读入二进制搜索树。列表中的第一个数字是树中元素的数量。 其余的放在以下结构中：

typedef struct node_struct { int data; struct node_struct* left; struct node_struct* right; } Node; 

我想我已经完成了第一部分。 拿东西使用fscanf（我没有选择使用这个方法，我更喜欢fgets），在数组的每个成员上调用一个插入函数，然后在插入函数中调用一个“createNode”函数。

问题是，我只有一名成员进入BST。 此外，BST必须满足条件node->left->data data right->data …换句话说，节点必须在树中按顺序排列。

这是我到目前为止所拥有的：

 #include  #include  #include  // def BST node struct typedef struct node_struct { int data; struct node_struct* left; struct node_struct* right; } Node; // prototypes Node* createNode(int data); Node* bstInsert(Node* root, int data); // helper function prototypes void padding(char ch, int n); void displayTree(Node* root, int depth); int main(int argc, char **argv) { FILE *in = NULL; int num_read, count=0, array_size = 0; if(argc != 2){ printf("hw3 \n"); return 1; } in = fopen(argv[1], "r"); if(in == NULL){ printf("File can not be opened.\n"); return 2; } // read in the first line to get the array size fscanf(in, "%d", &array_size); // declare the array int array[array_size]; // read from the second line to get each element of the array while(!feof(in)){ fscanf(in, "%d", &num_read); array[count] = num_read; count++; } fclose(in); if (array_size != count) { printf("data error. Make sure the first line specifies the correct number of elements."); return 3; } Node *root1 = NULL, *root2 = NULL, *root3 = NULL; int i; // task1: construct a bst from the unsorted array printf("=== task1: construct a bst from the unsorted array ===\n"); for (i = 0; i left; next = root->right; else{ if(previous->data data){ } } return root; } Node* createNode(int data) { // TODO Node* aRoot; if(!data) return NULL; aRoot = malloc(sizeof(Node)); if(!aRoot){ printf("Unable to allocate memory for node.\n"); return NULL; } aRoot->data = data; aRoot->left = NULL; aRoot->right = NULL; return aRoot; } /* helper functions to print a bst; You just need to call displayTree when visualizing a bst */ void padding(char ch, int n) { int i; for (i = 0; i right, depth+1); padding(' ', depth); printf ( "%d\n", root->data); displayTree(root->left, depth+1); } } 

我相信main ， createNode ， displayTree和padding displayTree 。 这是我遇到麻烦的地方。 我只是不确定如何订购以创建有效的树。

编辑：

我编辑了bstInsert并注入了更多逻辑。 它应该在树上打印出更多的叶子，但是，它只打印出数字“30”。 这是新function。

 Node* bstInsert(Node* root, int data) { if(root == NULL){ root = createNode(data); if(root != NULL){ root= createNode(data); } else{ printf("%d not inserted, no memory available.\n", data); } } else{ if(data data){ bstInsert(root->left, data); } else if(data > root->data || data == root->data){ bstInsert(root->right, data); } } return root; } 

Answer 1

您必须将新创建的节点指针分配给树的正确部分。 这段代码就是这样。 关键的变化是正确使用bstInsert()的返回值。 其他变化是化妆品。 请注意，我通过打印来检查输入数组; 此外，在建造BST时打印BST是明智的。

不要使用feof()作为循环控制条件。 当用作循环控件时几乎总是错误的，但至少你还必须检查后面的输入操作。 我的时间里写了很多程序; 我几乎没有使用feof() （我在自己的代码中找到了两个地方;在两者中，它在输入失败后正确用于区分EOF和错误。）

 #include  #include  #include  // def BST node struct typedef struct node_struct { int data; struct node_struct* left; struct node_struct* right; } Node; // prototypes Node *createNode(int data); Node *bstInsert(Node *root, int data); // helper function prototypes void padding(char ch, int n); void displayTree(Node *root, int depth); int main(int argc, char **argv) { FILE *in = NULL; int num_read, count=0, array_size = 0; if (argc != 2) { printf("hw3 \n"); return 1; } in = fopen(argv[1], "r"); if (in == NULL) { printf("File can not be opened.\n"); return 2; } // read in the first line to get the array size fscanf(in, "%d", &array_size); // declare the array int array[array_size]; // read from the second line to get each element of the array while (count < array_size && fscanf(in, "%d", &num_read) == 1) array[count++] = num_read; fclose(in); if (array_size != count) { printf("data error. Make sure the first line specifies the correct number of elements."); return 3; } for (int i = 0; i < array_size; i++) printf("%d: %d\n", i, array[i]); Node *root1 = NULL; // task1: construct a bst from the unsorted array printf("=== task1: construct a bst from the unsorted array ===\n"); for (int i = 0; i < array_size; i++) { root1 = bstInsert(root1, array[i]); displayTree(root1, 0); } displayTree(root1, 0); return 0; } Node *bstInsert(Node *root, int data) { if (root == NULL) { root = createNode(data); if (root == NULL) printf("%d not inserted, no memory available.\n", data); } else if (data < root->data) root->left = bstInsert(root->left, data); else root->right = bstInsert(root->right, data); return root; } Node *createNode(int data) { Node *aRoot; aRoot = malloc(sizeof(Node)); if (!aRoot) { printf("Unable to allocate memory for node.\n"); return NULL; } aRoot->data = data; aRoot->left = NULL; aRoot->right = NULL; return aRoot; } /* helper functions to print a bst; You just need to call displayTree when visualizing a bst */ void padding(char ch, int n) { for (int i = 0; i < n; i++) printf("%c%c%c%c", ch, ch, ch, ch); } void displayTree(Node *root, int depth) { if (root == NULL) { padding (' ', depth); printf("-\n"); } else { displayTree(root->right, depth+1); padding(' ', depth); printf ( "%d\n", root->data); displayTree(root->left, depth+1); } } 

Answer 2

好的，想想你想在不同的树配置中做什么：

• 当树为空时 – >创建根节点
• 当树不为空时 – >如何插入值和根比较值？
  • 上面 – >插入右边的子树
  • 下面 – >插入左子树
  • 相等 – >什么都不做（这实际上取决于你的作业如何告诉你处理重复）

从这个基本算法，你应该能够找出所有角落的情况。

Answer 3

一个简化的解决方案（带递归的天真插入，删除数据输入噪声）：

 #include  #include  #include  static int nums[] = { 6, 8, 4, 1, 3, 7, 14, 10, 13 }; // instead of the user input typedef struct _node { int value; struct _node *left; struct _node *right; } node; node *node_new(int v) { node *n = malloc(sizeof(*n)); assert(n); n->value = v; n->left = NULL; n->right = NULL; return n; } void insert(node **tree, node *leaf) { if (*tree == NULL) { *tree = leaf; } else if (leaf->value > (*tree)->value) { insert(&((*tree)->right), leaf); } else { insert(&((*tree)->left), leaf); } } void dump(node *tree, int level) { static const char *pad = "\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t"; if (tree != NULL) { printf("%sSelf: %d\n", pad + 16 - level, tree->value); if (tree->left) { printf("%sLeft node:\n", pad + 16 - level); dump(tree->left, level + 1); } if (tree->right) { printf("%sRight node:\n", pad + 16 - level); dump(tree->right, level + 1); } } else { printf("%sEmpty\n", pad + 16 - level); } } int main() { size_t n = sizeof(nums) / sizeof(*nums); int i; node *tree = NULL; for (i = 0; i < n; i++) { insert(&tree, node_new(nums[i])); } dump(tree, 0); // give some work to the kernel return 0; } 

Answer 4

你应该考虑递归地做这件事。 请记住，每个节点本身都是一棵树：

 #include  #include  typedef struct tree_struct { int value; struct tree_struct* left; struct tree_struct* right; } Tree; Tree* addToTree(int value, Tree* tree) { if (tree == NULL) { tree = malloc(sizeof(Tree)); tree->value = value; tree->left = NULL; tree->right = NULL; } else { if (value < tree->value) { tree->left = addToTree(value, tree->left); } else { tree->right = addToTree(value, tree->right); } } return tree; } int main(int argc, char** argv) { Tree* tree = NULL; int in; while (scanf("%d", &in) != EOF) { tree = addToTree(in, tree); } return 0; }