平衡二叉树上的删除 [英] Deletion on Balancing Binary Tree
问题描述
我有一个用于将数据插入平衡二叉树的代码，所以示例是，如果我输入以下输入:
I'm having a code for inserting data into a balancing binary tree, so the example is, if I enter these inputs:
20, 10, 30, 5, 15, 25, 4
我希望输入后的树看起来像这样:
I expect the tree after input would look like this:
20
/ \
10 30
/ \ / \
5 15 25 4
因此，在删除时，除了删除4个以外，其他所有功能都正常4在删除功能中属于情况1，
问题是，我不明白为什么删除4无效，但是删除5、15、25时有效吗?
So, when deleting, everything works fine except deleting 4
4 belongs to the case 1 in Delete function,
Question is, I can't understand why does deletion 4 doesn't work, but when I delete 5, 15, 25, it works?
我从 https://www.youtube.com/watch?v获得了删除功能= gcULXE7ViZw
它用于二叉搜索树，但我认为即使在二叉树中使用它也不会造成问题
I got the Delete function from https://www.youtube.com/watch?v=gcULXE7ViZw
It's for binary search tree, but I thought it would cause no problem even if it is used in a Binary Tree
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<conio.h>
struct node{
int data, balance;
struct node *left, *right;
};
int insert(struct node **root, struct node **curr, int data){
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode -> data = data;
newNode -> left = NULL;
newNode -> right = NULL;
newNode -> balance = 0;
if((*root) == NULL){
(*root) = (*curr) = newNode;
(*root) -> left = NULL;
(*root) -> right = NULL;
return 0;
} else {
if((*curr)->left == NULL && (*curr)->balance == 0){
(*curr) -> balance = (*curr) -> balance - 1;
(*curr) -> left = newNode;
return 0;
} else if ((*curr)->right == NULL && (*curr)->balance == -1){
(*curr) -> balance = (*curr) -> balance + 1;
(*curr) -> right = newNode;
return 0;
} else if ((*curr)->balance == 0 && (*curr)->left->balance == 0){
(*curr) -> balance = (*curr) -> balance - 1;
(*curr) = (*curr)->left;
return insert(root,curr,data);
} else if ((*curr)->balance < 0 && (*curr)->left->balance < 0){
(*curr) -> balance = (*curr) -> balance - 1;
(*curr) = (*curr) -> left;
return insert(root,curr,data);
} else if ((*curr)->balance < 0 && (*curr)->left->balance == 0){
(*curr) -> balance = (*curr) -> balance + 1;
(*curr) = (*curr)->right;
return insert(root, curr, data);
}
}
}
void preorder(struct node *root){
if(root == NULL) return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
void postorder(struct node *root){
if(root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
void inorder(struct node *root){
if(root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
void search(struct node *root, int *key, int *found){
if(root == NULL) return;
search(root->left, key, found);
if(root->data == *key){
*found = 1;
return ;
}
search(root->right, key, found);
}
struct node *findMin(struct node *root){
while(root->left != NULL) root = root->left;
return root;
}
struct node *Delete(struct node *root, int data){
if(root == NULL) return root;
else if(data < root->data) root->left = Delete(root->left, data);
else if(data > root->data) root->right = Delete(root->right, data);
else {
//Case 1: no child / leaf node
if(root->left == NULL && root->right == NULL){
free(root);
root = NULL;
}
//Case 2: one child, left or right
else if(root->left == NULL){
struct node *temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL){
struct node *temp = root;
root = root->left;
free(temp);
}
//Case 3: two children
else{
struct node *temp = findMin(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}
}
return root;
}
int main(){
struct node *root, *curr;
int choice, data, key, found, delKey;
root = curr = NULL;
while(1){
found = 0;
printf("Balanced Binary Tree Menu\n");
printf("1. Insert Data\n");
printf("2. View on pre order\n");
printf("3. View on post order\n");
printf("4. View on in order\n");
printf("5. Search\n");
printf("6. Delete\n");
printf("7. Exit\n");
printf("Pilihan: ");scanf("%d", &choice);fflush(stdin);
if(choice == 1){
printf("Enter data : "); scanf("%d", &data);
curr = root;
insert(&root, &curr, data);
} else if (choice == 2){
preorder(root);
system("pause");
} else if (choice == 3){
postorder(root);
system("pause");
} else if (choice == 4){
inorder(root);
system("pause");
} else if (choice == 5){
printf("Search: "); scanf("%d", &key);
search(root, &key, &found);
if(found == 1){
printf("Data found !\n");
} else {
printf("Data not found !\n");
}
system("pause");
} else if (choice == 6){
curr = root;
printf("Data : ");
preorder(root);
printf("\n\n");
printf("Enter data to be deleted: "); scanf("%d", &delKey);
Delete(curr, delKey);
printf("Data after deletion : ");
preorder(root);
system("pause");
} else if (choice == 7){
return 1;
}
system("cls");
}
return 0;
}
推荐答案
问题出在删除功能上.您将删除操作作为二进制搜索树执行.因此，从根节点(在您的示例中为20)开始搜索左侧子节点中的4.因此代码从20开始，依次为10和5，然后由于找不到4而停止.
the problem lies in the delete function. you perform the deletion as a binary search tree. So, from the root node (20 in your example), it proceeds to search for 4 in the left children. so the code starts at 20, goes to 10 and then 5 and then it stops because it doesn't find 4.
因此，您需要在删除操作中更改搜索策略(遍历顺序，后置订单，预购订单或级别订单).请记住，您的树不是二叉搜索树；它只是平衡.因此，当您要删除时，您需要查看每个节点.
So you need to change the strategy of your search in the delete (an inorder, postorder, preorder or level order traversal). Just keep in mind your tree isn't a binary search tree; it is just balanced. So you need to look at every node when you want to delete.
这篇关于平衡二叉树上的删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
