조건이 이상한 방식으로 작동하는 이유

Question

저는 이진 검색 트리에서 키를 검색하려고합니다. 내가 한 일은 다음과 같습니다.

int searchBST(int key,node *root){ 

    if(root->data == key){ 
     printf("The key %d is in the tree.\n",key); 
     return 1; 
    } 
    if(root->left != NULL){ 
     searchBST(key,root->left); 
     return 0; 
    } 
    if(root->right != NULL){ 
     searchBST(key,root->right); 
     return 0; 
    } 
} 

주 함수에서 함수가 1을 반환하는지 확인하고, 그렇지 않으면 함수가 키에 있는지 확인합니다. 키가 트리에없는 경우

printf("Please enter the key value you wish to search for: "); 
scanf("%d",&key); 
if((searchBST(key,root)) != 1) 
    printf("The key %d is not in the tree.\n",key); 

이 인쇄됩니다 : 올바른

The key %d is not in the tree. 

합니다. 키가 트리에있는 경우 그래서 여기에 이상한 부분은 온다, 언젠가 시스템은 인쇄됩니다

The key %d is in the tree. 

과 다른 시간 시스템이 인쇄됩니다 모두 :

The key %d is in the tree. 
The key %d is not in the tree. 

그래서 해결하기 위해 무엇을 할 수 있는지 그것?

여기 내 전체 코드

#include<stdio.h> 
#include<malloc.h> 
// This program will create a binary search tree or a max-heap, as chosen from a menu. 
typedef struct BSTNode{ 
int data; 
struct Node *left; 
struct Node *right; 
}node; 
node* getNewNode(int data){ 
    node *new = (node*)malloc(sizeof(node)); 
    new->data = data; 
    new->left = new->right = NULL; 
    return new; 
} 
void heapPreOrder(int heapRootIndex,int array[],int numOfNodes){ 
int i = heapRootIndex; 
printf("%d\t",array[i]); 
if(2*i+1<numOfNodes) 
    heapPreOrder(2*i+1,array,numOfNodes); 
if(2*i+2<numOfNodes) 
    heapPreOrder(2*i+2,array,numOfNodes); 
} 
void disLevelOrder(int array[],int numOfNodes){ 
int i; 
for(i = 0;i < numOfNodes;i++){ 
    printf("%d\t",array[i]); 
} 
printf("\n"); 
} 
node* insertBST(int data,node *root){ 
if(root == NULL){ 
    root = getNewNode(data); 
} 
else{ 
    if(data <= root->data){ 
     root->left = insertBST(data,root->left); 
    } 
     else if(data >= root->data) 
     root->right= insertBST(data,root->right); 
    } 
    return root; 

} 

int searchBST(int key,node *root){ 

if (!root) return 0; 
if (root->data == key) return 1; 
if (root->data > key) return searchBST(root->left, key); 
return searchBST(root->right, key); 
} 
void levelOrder(node* root, int level){ 
if (root == NULL) 
    return; 
if (level == 1) 
    printf("%d\t", root->data); 
else if (level > 1) 
{ 
    levelOrder(root->left, level-1); 
    levelOrder(root->right, level-1); 
} 
} 
int findHeight(node* root) 
{ 
if (root==NULL) 
    return 0; 
else 
{ 
    int leftHeight = findHeight(root->left); 
    int rightHeight = findHeight(root->right); 

    if(leftHeight >= rightHeight) 
     return leftHeight+1; 
    else 
     return rightHeight+1; 
} 

} 
void insertHeap(int key,int numOfNodes,int array[]){ 
int i,j; 
i = numOfNodes-1; 
if(i%2 == 1 && array[i] > array[(i-1)/2]){ //if left child is greater than parent 
      swap(&array[i],&array[(i-1)/2]); 
      for(j = (i-1)/2;j > 0,array[j]>array[(j- 1)/2]; j = (j- 1)/2){ 
       swap(&array[j],&array[(j-1)/2]); 
      } 
     } 
     if(i%2 == 0 && array[i] > array[(i-2)/2]){//if right child is greater than parent 
      swap(&array[i],&array[(i-2)/2]); 
      for(j = (i-1)/2;j > 0,array[j]>array[(j- 1)/2]; j = (j- 1)/2){ 
       swap(&array[j],&array[(j-1)/2]); 
      } 
     } 
} 
void searchHeap(int key,int array[],int numOfNodes){ 
int i; 
for(i = 0;i < numOfNodes;i++){ 
    if(key == array[i]){ 
     printf("The key %d is in the heap.\n",key); 
     return; 
    } 
} 
printf("The key %d is not in the heap.\n",key); 
} 
void preorder(node *root){ 
if(root!=NULL){ 
    printf("%d\t",root->data); 
    preorder(root->left); 
    preorder(root->right); 
} 
} 
void swap(int *a,int *b){ 
int temp; 
temp = *a; 
*a = *b; 
*b = temp; 

} 
int main(){ 
int i,j,numOfNodes,key,height; 
char choice,option; 
node *root = (node*)malloc(sizeof(node));  //initialize root; 
root = NULL; 
printf("Enter the number of nodes in the linked list to be initially created: "); 
scanf("%d",&numOfNodes); 
int array[numOfNodes];   //store all the data in the array first 
printf("Enter the data value to be placed in the node: "); 
scanf("%d",&array[0]); 
root = insertBST(array[0],root);   //create the root 
//root->left = getNewNode(array[0]); 
for(i = 1;i < numOfNodes;i++){ 
    printf("Enter the data value to be placed in the node: ");     //put each data into array, leave the index 0 empty 
    scanf("%d",&array[i]); 
} 
printf("What do you wish to create a Binary search Tree (B) or a Max-Heap (H)?: "); 
scanf(" %c",&choice); 
if(choice == 'B' || choice == 'b'){   //if user wants to build a Binary search Tree 
    for(i = 1;i<numOfNodes;i++){ 
     insertBST(array[i],root); 
    } 
     printf("Binary search tree build successfully.\n"); 
} 


if(choice == 'H'|| choice == 'h'){   //if user wants to build a Max-Heap 
     for(i = 1;i<numOfNodes;i++){   //build the max heap 
     if(i%2 == 1 && array[i] > array[(i-1)/2]){ //if left child is greater than parent 
      swap(&array[i],&array[(i-1)/2]); 
      for(j = (i-1)/2;j > 0,array[j]>array[(j- 1)/2]; j = (j- 1)/2){ 
       swap(&array[j],&array[(j-1)/2]); 
      } 
     } 
     if(i%2 == 0 && array[i] > array[(i-2)/2]){ //if right child is greater than parent 
      swap(&array[i],&array[(i-2)/2]); 
      for(j = (i-1)/2;j > 0,array[j]>array[(j- 1)/2]; j = (j- 1)/2){ 
       swap(&array[j],&array[(j-1)/2]); 
      } 
     } 
    } 
     printf("Heap successfully created.\n"); 
    } 
while(choice == 'B'||choice == 'b'){ 
    printf("What do you wish to do?\n"); 
    printf("Show Preorder Traversal(P)\tShow Level order Traversal(L)\tSearch(S)\tInsert(I)\tQuit(Q)\n"); 
    printf("Please enter a choice: "); 
    scanf(" %c",&option); 
     if(option == 'p'||option == 'P'){ 
     preorder(root); 
     printf("\n"); 
    } 
    if(option == 'L'||option == 'l'){ 
     height = findHeight(root); 
     for(i = 1;i <= height;i++){ 
      levelOrder(root,i); 
     } 
     printf("\n"); 
    } 
    if(option == 'S'||option == 's'){  //This is the part I have trouble with 
     printf("Please enter the key value you wish to search for: "); 
     scanf("%d",&key); 
     if((searchBST(key,root)) != 1) 
     printf("The key %d is not in the tree.\n",key); 
    } 
    if(option == 'I'||option == 'i'){  //if user wants to insert a number 
     printf("please enter the key value you wish to insert: "); 
     scanf("%d",&key); 
     insertBST(key,root); 
     printf("The key value %d was successfully inserted.\n",key); 
    } 
    if(option == 'q'||option == 'Q'){ 
     printf("Thanks for using my program, please rate 100 as feedback! Have a wonderful day :)"); 
     return 0; 
    } 
    printf("\n"); 
} 
while(choice == 'H'|| choice == 'h'){ 
    printf("What do you wish to do?\n"); 
    printf("Show Preorder Traversal(P)\tShow Level order Traversal(L)\tSearch(S)\tInsert(I)\tQuit(Q)\n"); 
    printf("Please enter a choice: "); 
    scanf(" %c",&option); 
    if(option == 'p'||option == 'P'){ 
     heapPreOrder(0,array,numOfNodes); 
     printf("\n"); 
    } 
    if(option == 'L'||option == 'l'){ 
     disLevelOrder(array,numOfNodes); 
     printf("\n"); 
    } 
    if(option == 'S'||option == 's'){ 
     printf("Please enter the key value you wish to search for: "); 
     scanf("%d",&key); 
     searchHeap(key,array,numOfNodes); 
    } 
    if(option == 'I'||option == 'i'){  //if user wants to insert a number 
     printf("please enter the key value you wish to insert: "); 
     scanf("%d",&key); 
     numOfNodes++; 
     array[numOfNodes-1] = key; 
     insertHeap(key,numOfNodes,array); 
     printf("The key value %d was successfully inserted.\n",key); 
    } 
    if(option == 'q'||option == 'Q'){ 
     printf("Thanks for using my program, please rate 100 as feedback! Have a wonderful day :)"); 
     return 0; 
    } 
    printf("\n"); 
} 

}

Answer 1

당신은 키의 전체 이진 검색 트리를 검색하지 말아야합니다. 올바른 경로를 따라야합니다. 그래서 키를 현재 루트 값과 비교해야합니다. 값이 key와 같으면 출력입니다. 키가 루트 값보다 작 으면 왼쪽 하위 트리로 이동해야합니다. 그렇지 않으면 오른쪽 하위 트리로 이동해야합니다.

int searchBST(int key, node* root) { 
    if (!root) return 0; 
    if(root->data == key) { 
     printf("The key %d is in the tree.\n",key); 
     return 1; 
    } 
    if (root->data > key) return searchBST(key, root->left); 
    return searchBST(key, root->right); 
} 

이 경우 키를 발견하더라도 전체 트리를 탐색하고 있습니다. 그렇기 때문에 언젠가 두 가지 출력을 모두 얻게됩니다.

Answer 2

이 시도 :

int searchBST(int key,node *root){ 
    if (!root){ 
     return 0; 
    } 
    if(root->data == key){ 
     printf("The key %d is in the tree.\n",key); 
     return 1; 
    } 
    if(root->left != NULL){ 
     return searchBST(key,root->left); 
     //return 0; 
    } 
    if(root->right != NULL){ 
     return searchBST(key,root->right); 
     //return 0; 
    } 
} 

Answer 3

편집 답변 -을 : 문제는 반환 값에 관한 한

1. . 키를 찾았더라도 다음 반복 루프에서 값 0을 반환합니다. 이것은 주 기능에서 검사되고 키를 찾을 수 없다고보고됩니다.
2. 두 번째로 노드의 오른쪽 링크에서 검색이 수행되지 않았습니다.
3. 특히 첫 번째 항목을 추가하는 동안 루트 링크 된 목록의 중복 항목.

그냥,

printf("Please enter the key value you wish to search for: "); 
    scanf("%d",&key); 
    if(0 != searchBST(key,root)) 
    printf("The key %d is not in the tree.\n",key); 

반환 값 0은 성공을 의미

int searchBST(int key,node *root){ 

     int bRet = 1; /// 1 means error 
     if(root->data == key){ 
      printf("The key %d is in the tree.\n",key); 
      bRet = 0; /// 0 means success 
      return bRet; 
     } 
     if(root->left != NULL){ 
      bRet = searchBST(key,root->left); 
      if(!bRet) 
      { 
       return bRet; 
      } 
     } 
     if(root->right != NULL){ 
      bRet = searchBST(key,root->right); 
      if(!bRet) 
      { 
       return bRet; 
      } 
     } 

     return bRet; 
    } 

주요 기능, 다음과 같이 코드를 변경 한을 포함하여 다른 모든 값은 오류/키를 찾을 수 없음을 의미합니다.

내가뿐만 아니라 사소한 문제를 발견하지만 난 그 컴파일 시간 그 자체와 같은에서 발견해야한다고 생각

1. int 배열 [numOfNodes] 배열 선언에는 변수가 아닌 const 번호가 필요합니다.
2. 노드 대신 노드를 사용합니다.
3. "새"키워드를 변수로 사용.
4. 스왑 함수는 위에 정의 된대로 정의해야합니다.