2017-11-30 18 views
0

以下のコードは、一連の挿入と削除の後にバイナリ検索ツリーの最終的な高さを出力することを想定しています。挿入と削除後のバイナリ検索ツリーの高さの検索

#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; 
} 

答えて

2

これは、追加されたノードを決してリンクしなかったためです。

if(data < root -> data) root->left= Insert(data, root -> left); 
else if(data >= root -> data) root->right = Insert(data, root -> right); 

はまた、両方のケースでInsert()にあなたがroot->leftを使用していたことに注意してください。それは上記の通りでなければなりません。

Find()機能でも

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); 
    // ^ You need to make it >= 
    return NULL; //<----Add it 
} 

また、あなたが得たワンセグ障害があるため、誤った削除ロジックです。正しいものはまたfindMinのバージョンだけで、すべてのノード値の最小値を返します

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) 
     { 
      struct Node *temp = root->right; 
      free(root); 
      return temp; 
     } 
     else if (root->right == NULL) 
     { 
      struct Node *temp = root->left; 
      free(root); 
      return temp; 
     } 
     else 
     { 
      struct Node *temp = FindMin(root->right); 
      root->data = temp->data; 
      root->right = Delete(temp->data, root->right); 
     } 
    } 
    return root; 
} 

ようなものです。しかし、これは、Delete()の機能に必要なものではありません。だからこそ、この機能です。

struct Node*FindMin(struct Node* node) 
{ 
    struct Node *current = node; 
    while (current->left != NULL) 
      current = current->left; 
    return current; 
} 
+0

これはテストしましたか?私は私のコードでこれを行う場合、私はこれらの行にセグメンテーションフォールトを取得します。 – Ruan

+0

@Ruan:あなたのコードでさえ、それは遅く返事のために残念です。しかし、それ以外の場合はそれを割り当てていないので、あなたはこのような変更を行う必要があります。 'Find()'に 'NULL'を返します。私はノードを追加する別の方法を追加しましたが、あなたはこれも同様にそれを行うことができます。 – coderredoc

+0

@Ruan:これらの変更により、このコードは適切に動作し、与えられた入力セットに対して '5'が出力されます。あなたが挿入をチェックし、高さをチェックするだけでそれが機能するでしょう。 – coderredoc

関連する問題