Tag: binary search tree

从C二进制树中删除节点而不会弄乱它

我是一个初学者，正在研究一个C二叉树库。我想知道如何从二叉树中删除一个节点而不会搞乱整个事情。这就是我创建树的方法： 结构： struct Node { int value; struct Node *left; struct Node *right; }; typedef struct Node TNode; typedef struct Node *binary_tree; 创建树： binary_tree NewBinaryTree(int value_root) { binary_tree newRoot = malloc(sizeof(TNode)); if (newRoot) { newRoot->value = value_root; newRoot->left = NULL; newRoot->right = NULL; } return newRoot; } 添加元素： void Insert(binary_tree *tree, int val) { if […]

指针和二进制搜索树

我正在开发一个使用二叉搜索树的程序（作为练习）。 我的问题是，当我尝试添加一个客户时 （在我的代码行65-69中间）我得到一个BS_node未声明的错误，虽然我在此函数中插入了struct BST_node * root ..我的部分代码如下，只是为了让读者更容易阅读，如果要求我可以上传完整的代码！ 谢谢！ #include #include #include #define MAX_STRING 50 void flush(); struct customer { char *name; char *address; char *email; }; struct double_linked_list { struct customer *data; struct double_linked_list *previous; struct double_linked_list *next; }; struct double_linked_list *customers_head=0; struct BST_node { struct double_linked_list *data; struct BST_node *left; struct BST_node *right; }; […]

二叉搜索树获得0而不是null

我一直试图清除我的二叉树，当这样做时，我从下面的代码得到一个0而不是null。 当树引用NULL但未发生时，该树被定义为空。 在遍历树时可以看到错误。 如何更改它，以便在插入第二组数字时，0不显示？ #include #include typedef struct Node{ int value; struct Node * left; struct Node * right; } Node; Node * insert(Node * node, int value){ if(node == NULL){ Node *temp; temp = (Node *)malloc(sizeof(Node)); temp->value = value; temp->left = temp->right = NULL; return temp; } if(value >(node->value)){ node->right = insert(node->right,value); } else […]

使用二叉搜索树时遇到问题删除function

我试图从二叉搜索树中删除给定的值。 如果给定值存在，则函数返回1，如果不存在，则返回0。 我认为我没有正确回报价值观。 似乎删除了正确的值，但是当我不应该删除时，我正在打印删除消息，表示该函数在不应该返回时返回0。 任何人都可以帮我发现我的错误吗？ 谢谢。 /*Remove data from BST pointed to by rootRef, changing root if necessary. * For simplicity’s sake, always choose node’s in-order * successor in the two-child case. * Memory for removed node should be freed. * Return 1 if data was present, 0 if not found. */ int removeBST(struct TreeNode** […]

在二叉搜索树中查找节点的父节点

我在查找二叉搜索树中特定节点的父节点时遇到问题。 解决方案应该是直截了当的，但我不知道为什么我的代码不起作用…我尝试了不同的方法，并在网上搜索任何解决方案但没有找到任何结果。 我感谢任何帮助!! typedef struct Treenode{ int key; struct Treenode* lChild; struct Treenode* rChild; }node; node * getParent(node *root, int key){ if (root == NULL) return NULL; else if (root->rChild->key == key || root->lChild->key == key) return root; else if (root->key > key) getParent(root->lChild, key); else getParent(root->rChild, key); return root; }

将文本文件中的单词插入到C中的树中

在过去的两天里，我遇到了一个奇怪的问题，但我还是无法解决它。 我试图从2个文本文件中获取单词并将这些单词添加到树中。 我选择获取单词的方法在这里被引用： 将文本文件拆分为C中的单词 。 我用来将单词插入树中的函数如下： void InsertWord(typosWords Words, char * w) { int error ; DataType x ; x.word = w ; printf(” Trying to insert word : %s \n”,x.word ); Tree_Insert(&(Words->WordsRoot),x, &error) ; if (error) { printf(“Error Occured \n”); } } 正如发布的链接中所提到的，当我尝试将文本文件中的单词导入树中时，我收到“Error Occured”。 再次function： 文本文件： 一个 AAAH aaahh char this_word[15]; while (fscanf(wordlist, “%14s”, […]

完美平衡的二进制搜索树

我有关于Balanced BST的理论问题。 我想构建具有2^k – 1节点的Perfect Balanced Tree ，来自常规的unbalanced BST 。 我能想到的最简单的解决方案是使用排序的Array/Linked list并递归地将数组划分为子数组，并从中构建Perfect Balanced BST 。 但是，在树大小非常大的情况下，我需要创建一个相同大小的Array/List ，因此这种方法会占用大量内存。 另一种选择是使用AVL旋转function，逐个元素插入并根据树平衡因子平衡树和旋转 – 左和右子树的三个高度。 我的问题是，我对我的假设是对的吗？ 还有其他方法可以从不平衡的BST创建完美的BST吗？

在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* […]

在二叉树中插入元素

试图通过网络进行大量探索，但可以得到任何帮助，Everywhere就像在二进制搜索树中添加一个节点一样。 问题：请求用于将节点添加到二叉树的算法和代码片段。 （或指向我更正url） 假设：根据我的理解， 二叉树和二叉搜索树是不同的？ 如果我错了，请纠正我。 （请求：如果您正在编写代码片段，请使用适当的变量名称，这有助于理解） 例如：二叉树 5 7 3 x1 x2 x3 5 7 3 x1 x2 x3 二进制搜索树5 7 3 2 4 6 5 3 7 2 4 6 insert(int key, struct node **root) { if( NULL == *root )` { *root = (struct node*) malloc( sizeof( struct node ) );` (*root)->data […]

在二叉搜索树中删除

所以当我在二叉搜索树中删除时，我是否需要有7种不同的情况，即 左叶; 右叶; 左孩子只有左孩子。 //即要删除的节点是它父节点的左子节点，它只剩下子节点。 左孩子只有正确的孩子。 只有左孩子的右孩子。 没有合适孩子的正确孩子。 要删除的节点包含两个子节点，即右侧和左侧。 现在，当这段代码使用if-else它变得非常讨厌..有没有其他方法可以做到这一点。 这是我的代码片段 if(current->left==NULL && current->right==NULL && current->keykey) //left leaf prev->left=NULL; else if(current->left==NULL && current->right==NULL && current->key>prev->key) // right leaf prev->right=NULL; else if(current->left!=NULL && current->right==NULL && current->keykey) // left child with one child prev->left=current->left; else if(current->left==NULL && current->right!=NULL && current->keykey) prev->left=current->right; else if(current->left!=NULL && current->right==NULL && current->key>prev->key) […]