以下のコードは、一連の挿入と削除の後にバイナリ検索ツリーの最終的な高さを出力することを想定しています。挿入と削除後のバイナリ検索ツリーの高さの検索
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct Node{
int data;
struct Node *left;
struct Node *right;
};
struct Node* Insert(int data, struct Node *root){
if(root == NULL){
root = malloc(sizeof(struct Node));
root -> data = data;
root -> left = root -> right = NULL;
}
else{
if(data < root -> data) Insert(data, root -> left);
else if(data > root -> data) Insert(data, root -> left);
}
return root;
}
struct Node* Find(int data, struct Node *root){
if(root == NULL || root -> data == data) return root;
if(data < root -> data) return Find(data, root -> left);
if(data > root -> data) return Find(data, root -> right);
}
int FindMin(struct Node *root){
int min, l_min, r_min;
if(root == NULL) return INT_MIN;
min = root -> data;
l_min = FindMin(root -> left);
r_min = FindMin(root -> right);
if(l_min < min) min = l_min;
if(r_min < min ) min = r_min;
return min;
}
struct Node* Delete(int data, struct Node *root){
struct Node *temp;
if(data < root -> data) root -> left = Delete(data, root -> left);
else if(data > root -> data) root -> right = Delete(data, root -> right);
else{
if(root -> left != NULL && root -> right != NULL){
root -> data = FindMin(root -> right);
root -> right = Delete(root -> data, root -> right);
}
else{
temp = root;
if(root -> left == NULL) root = root -> right;
if(root -> right == NULL) root = root -> left;
free(temp);
}
}
return root;
}
int Height(struct Node *root){
int l_height, r_height;
if(root == NULL) return 0;
else{
l_height = Height(root -> left);
r_height = Height(root -> right);
if(l_height > r_height) return l_height + 1;
else return r_height + 1;
}
}
int main(){
struct Node *root = NULL, *temp = NULL;
int n, a, b;
scanf("%i",&n);
while(n--){
scanf("%i %i",&a,&b);
if(a == 1){
temp = Find(b,root);
if(temp != NULL) continue;
root = Insert(b,root);
}
else if(a == 2){
temp = Find(b,root);
if(temp == NULL) continue;
root = Delete(b,root);
}
else{
continue;
}
}
printf("Height: %i\n",Height(root));
return 0;
}
最初の入力は、続く行数であるnです。
次の行はすべて、整数「a b」を持ちます。 a == 1は挿入を意味し、b == 2は削除を意味し、bは挿入または削除される値です。 "Find"関数は、BSTに値が存在するかどうかを検査し、既存のものを挿入したり、BSTに存在しないものを削除しようとしないようにします。
ので、例えば、これが有効なテストケースであり、それは5を返す必要があります。
10
1 5
1 8
1 3
1 4
1 2
1 1
1 0
1 7
1 9
2 3
しかし、私のコードはこれを行うに失敗していると簡単に可能なすべてのテストケースのために「1」を返します。なぜ私はこれが起こっているのか分からない。何か案は?
解決策:@ codeeredredocのおかげで、このコードは完全に機能しています。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct Node{
int data;
struct Node *left;
struct Node *right;
};
struct Node* Insert(int data, struct Node *root){
if(root == NULL){
root = malloc(sizeof(struct Node));
root -> data = data;
root -> left = root -> right = NULL;
}
else{
if(data < root -> data) root -> left = Insert(data, root -> left);
else if(data > root -> data) root -> right = Insert(data, root -> right);
}
return root;
}
struct Node* Find(int data, struct Node *root){
if(root == NULL || root -> data == data) return root;
if(data < root -> data) return Find(data, root -> left);
if(data >= root -> data) return Find(data, root -> right);
return NULL;
}
struct Node* FindMin(struct Node *root){
struct Node *temp = root;
while(temp -> left != NULL) temp = temp -> left;
return temp;
}
struct Node* Delete(int data, struct Node *root){
struct Node *temp;
if(root == NULL) return NULL;
if(data < root -> data) root -> left = Delete(data, root -> left);
else if(data > root -> data) root -> right = Delete(data, root -> right);
else{
if(root -> left == NULL){
temp = root -> right;
free(root);
return temp;
}
else if(root -> right == NULL){
temp = root -> left;
free(root);
return temp;
}
else{
temp = FindMin(root -> right);
root -> data = temp -> data;
root -> right = Delete(temp -> data, root -> right);
}
}
return root;
}
int Height(struct Node *root){
int l_height, r_height;
if(root == NULL) return 0;
else{
l_height = Height(root -> left);
r_height = Height(root -> right);
if(l_height > r_height) return l_height + 1;
else return r_height + 1;
}
}
int main(){
struct Node *root = NULL, *temp = NULL;
int n, a, b;
scanf("%i",&n);
while(n--){
scanf("%i %i",&a,&b);
if(a == 1){
temp = Find(b,root);
if(temp != NULL) continue;
root = Insert(b,root);
}
else if(a == 2){
temp = Find(b,root);
if(temp == NULL) continue;
root = Delete(b,root);
}
else{
continue;
}
}
printf("%i\n",Height(root));
return 0;
}
これはテストしましたか?私は私のコードでこれを行う場合、私はこれらの行にセグメンテーションフォールトを取得します。 – Ruan
@Ruan:あなたのコードでさえ、それは遅く返事のために残念です。しかし、それ以外の場合はそれを割り当てていないので、あなたはこのような変更を行う必要があります。 'Find()'に 'NULL'を返します。私はノードを追加する別の方法を追加しましたが、あなたはこれも同様にそれを行うことができます。 – coderredoc
@Ruan:これらの変更により、このコードは適切に動作し、与えられた入力セットに対して '5'が出力されます。あなたが挿入をチェックし、高さをチェックするだけでそれが機能するでしょう。 – coderredoc