プログラムの出力が予想と異なっています

Question

私はバイナリツリープログラムを持っています。そして、プログラムのいくつかの部分をテストして、入力が期待される出力にicualであるかどうかを確認しようとしています。しかし、下記の2つの問題があります。

たとえば、このテストを以下のように実行しようとすると、テストパスに「同じ」、失敗したときに「同じではない」と表示されます。

INPUT              OUTPUT 
Insert 10 nodes(55, 31, 49, 64, 65, 39, 47, 98, 97, 1) 55, 31, 49, 64, 65, 39, 47, 98, 97, 1 
Insert node 4          55, 31, 49, 64, 65, 39, 47, 98, 97, 1, 4 
print_preorder()          55, 31, 1, 4, 49, 39, 47, 64, 65, 98, 97 
search(55)           55 

問題はイムが正しい入力を与え、私はいつも、以下の結果を得ることにある、最後のテストでは、「同じではありません」常に表示され、テストは、コードの他の部分ではない「と同じではない」を示す場合実行される。

same 
same 
not same 

と私は期待：

same 
same 
same 
55 

そして、他の問題は、私はこのメッセージを取得するときに「同じではありません」以下の他のコードが実行されていないということです。

例：

int main(void) { 
    node *root = NULL; 
    int i, j; 
    node *tmp; 
    int arr[] = {55, 31, 49, 64, 65, 39, 47, 98, 97, 1}; 
    int n = sizeof(arr)/sizeof(*arr); 
    int arrExp[sizeof(arr)/sizeof(*arr)] = {0}; 
    int arrExp2[] = {55, 31, 1, 4, 49, 39, 47, 64, 65, 98, 97}; 

    int *aporder = arr; 
    int *ap = arrExp; 


    // insert 10 nodes on tree 
    for (i = 0; i < n; i++) 
     insert(&root, arr[i]); 

    // check if the array elements are the same of the tree 
    outToArray(root, &ap); 
    qsort(arr, n, sizeof(*arr), cmp); 
    for (i = 0; i < n; i++) { 
     if (arr[i] != arrExp[i]) { 
      puts("not same"); 
      return -1; 
     } 
    } 
    puts("same"); 

    // insert node 4 on tree 
    insert(&root, 4); 

    // check if tree nodes are now icual to arrExp that has now the 4 node 
    outToArray(root, &ap); 
    qsort(arr, n, sizeof(*arr), cmp); 
    for (i = 0; i < n; i++) { 
     if (arr[i] != arrExp[i]) { 
      puts("not same"); 
      return -1; 
     } 
    } 
    puts("same"); 

    // check if pre order display is icual to ArrExp2 
    outToArrayPorder(root, &aporder); 
    for (i = 0; i < n; i++) { 
     if (arr[i] != arrExp2[i]) { 
      puts("not same"); 
      return -1; 
     } 
    } 
    puts("same"); 

    tmp = search(&root, 55); 
    if (tmp) 
    { 
     printf("Searched node=%d\n", tmp->data); 
    } 
    else 
    { 
     printf("Data Not found in tree.\n"); 
    } 

    /* Deleting all nodes of tree */ 
    deltree(root); 

    return 0; 
} 



    int cmp(const void *a, const void *b){ 
    int x = *(int *)a; 
    int y = *(int *)b; 
    return x < y ? -1 : x > y; 
} 

void outToArrayPorder(node *tree, int **arr){ 
    //pre-order output 
    if(tree){ 
     *(*arr)++ = tree->data; 
     outToArrayPorder(tree->left, arr); 
     outToArrayPorder(tree->right, arr); 
    } 
} 

void outToArray(node *tree, int **arr){ 
    //Write elements of tree to the array. 
    if(tree){ 
     outToArray(tree->left, arr); 
     *(*arr)++ = tree->data; 
     outToArray(tree->right, arr); 
    } 
} 


int print_preorder(node * tree) 
{ 
    if (tree) 
    { 
     printf("%d ",tree->data); 
     int left = print_preorder(tree->left); 
     int right = print_preorder(tree->right); 
     return left+right+1; 
    } else{ 
     return 0; 
    } 

} 

完全なプログラム：

#include<stdlib.h> 
#include<stdio.h> 

struct bin_tree { 
    int data; 
    struct bin_tree * right, * left; 
}; 
typedef struct bin_tree node; 

void insert(node ** tree, int val) 
{ 
    node *temp = NULL; 
    if(!(*tree)) 
    { 
     temp = (node *)malloc(sizeof(node)); 
     temp->left = temp->right = NULL; 
     temp->data = val; 
     *tree = temp; 
     return; 
    } 

    if(val < (*tree)->data) 
    { 
     insert(&(*tree)->left, val); 
    } 
    else if(val > (*tree)->data) 
    { 
     insert(&(*tree)->right, val); 
    } 

} 

int print_preorder(node * tree) 
{ 
    if (tree) 
    { 
     printf("%d ",tree->data); 
     int left = print_preorder(tree->left); 
     int right = print_preorder(tree->right); 
     return left+right+1; 
    } else{ 
     return 0; 
    } 

} 

int print_inorder(node * tree) 
{ 
    if (tree) 
    { 

     int left = print_inorder(tree->left); 
     printf("%d ",tree->data); 
     int right = print_inorder(tree->right); 
     return left+right+1; 
    }else{ 
     return 0; 
    } 
} 
int print_postorder(node * tree) 
{ 
    if (tree) { 
     int left = print_postorder(tree->left); 
     int right = print_postorder(tree->right); 
     printf("%d ",tree->data); 
     return left + right + 1; 
    } else { 
     return 0; 
    } 
} 

void deltree(node * tree) 
{ 
    if (tree) 
    { 
     deltree(tree->left); 
     deltree(tree->right); 
     free(tree); 
    } 
} 

node* search(node ** tree, int val) 
{ 
    if(!(*tree)) 
    { 
     return NULL; 
    } 

    if(val < (*tree)->data) 
    { 
     search(&((*tree)->left), val); 
    } 
    else if(val > (*tree)->data) 
    { 
     search(&((*tree)->right), val); 
    } 
    else if(val == (*tree)->data) 
    { 
     return *tree; 
    } 
} 


int cmp(const void *a, const void *b){ 
    int x = *(int *)a; 
    int y = *(int *)b; 
    return x < y ? -1 : x > y; 
} 

void outToArrayPorder(node *tree, int **arr){ 
    //pre-order output 
    if(tree){ 
     *(*arr)++ = tree->data; 
     outToArrayPorder(tree->left, arr); 
     outToArrayPorder(tree->right, arr); 
    } 
} 

void outToArray(node *tree, int **arr){ 
    //Write elements of tree to the array. 
    if(tree){ 
     outToArray(tree->left, arr); 
     *(*arr)++ = tree->data; 
     outToArray(tree->right, arr); 
    } 
} 



int main(void) { 
    node *root = NULL; 
    int i, j; 
    node *tmp; 
    int arr[] = {55, 31, 49, 64, 65, 39, 47, 98, 97, 1}; 
    int n = sizeof(arr)/sizeof(*arr); 
    int arrExp[sizeof(arr)/sizeof(*arr)] = {0}; 
    int arrExp2[] = {55, 31, 1, 4, 49, 39, 47, 64, 65, 98, 97}; 

    int *aporder = arr; 
    int *ap = arrExp; 


    // insert 10 nodes on tree 
    for (i = 0; i < n; i++) 
     insert(&root, arr[i]); 

    // check if the array elements are the same of the tree 
    outToArray(root, &ap); 
    qsort(arr, n, sizeof(*arr), cmp); 
    for (i = 0; i < n; i++) { 
     if (arr[i] != arrExp[i]) { 
      puts("not same"); 
      return -1; 
     } 
    } 
    puts("same"); 

    // insert node 4 on tree 
    insert(&root, 4); 

    // check if tree nodes are now icual to arrExp that has now the 4 node 
    outToArray(root, &ap); 
    qsort(arr, n, sizeof(*arr), cmp); 
    for (i = 0; i < n; i++) { 
     if (arr[i] != arrExp[i]) { 
      puts("not same"); 
      return -1; 
     } 
    } 
    puts("same"); 

    // check if pre order display is icual to ArrExp2 
    outToArrayPorder(root, &aporder); 
    for (i = 0; i < n; i++) { 
     if (arr[i] != arrExp2[i]) { 
      puts("not same"); 
      return -1; 
     } 
    } 
    puts("same"); 

    tmp = search(&root, 55); 
    if (tmp) 
    { 
     printf("Searched node=%d\n", tmp->data); 
    } 
    else 
    { 
     printf("Data Not found in tree.\n"); 
    } 

    /* Deleting all nodes of tree */ 
    deltree(root); 

    return 0; 
} 

はなくて、それが「同じではありません」私は以下のようにしようとしていた表示されたときに実行されないコードに関する問題を修正しようとします-1を返しますが、同じ問題が発生します。 「同じではない」と言うと、その部分は実行されないので、search = "55"は表示されません。現在

// insert node 4 on tree 
    insert(&root, 4); 

    // check if tree nodes are now icual to arrExp2 that has now the 4 node 
    int out2[++n]; 
    ap = out2; 
    bool test = true; 
    outToArray(root, &ap); 
    for (i = 0; i < n; i++) { 
     if (out2[i] != arrExp2[i]) { 
      puts("not same"); 
      test=false; 
     } 
    } 
    if(test == true){ 
     puts("same"); 
    } 

Answer 1

あなたのコードは要素の追加を考慮しません。
次のように変更します。コメントの

int main(void) { 
    node *root = NULL; 
    int i; 
    int arr[] = {55, 31, 49, 64, 65, 39, 47, 98, 97, 1}; 
    int n = sizeof(arr)/sizeof(*arr); 
    int arrExp1[sizeof(arr)/sizeof(*arr)] = {0}; 
    int arrExp2[] = {1, 4, 31, 39, 47, 49, 55, 64, 65, 97, 98}; 
    int arrExp3[] = {55, 31, 1, 4, 49, 39, 47, 64, 65, 98, 97}; 
    int *ap = arrExp1; 

    // insert nodes of arr on tree 
    for (i = 0; i < n; i++) 
     insert(&root, arr[i]); 

    // check if the array elements are the same of the tree 
    outToArray(root, &ap); 
    qsort(arr, n, sizeof(*arr), cmp); 
    for (i = 0; i < n; i++) { 
     if (arr[i] != arrExp1[i]) { 
      puts("not same"); 
      return -1; 
     } 
    } 
    puts("same"); 

    // insert node 4 on tree 
    insert(&root, 4); 

    // check if tree nodes are now icual to arrExp2 that has now the 4 node 
    int out2[++n]; 
    ap = out2; 
    outToArray(root, &ap); 
    for (i = 0; i < n; i++) { 
     if (out2[i] != arrExp2[i]) { 
      puts("not same"); 
      return -1; 
     } 
    } 
    puts("same"); 

    // check if pre order display is icual to ArrExp3 
    ap = out2; 
    outToArrayPorder(root, &ap); 
    for (i = 0; i < n; i++) { 
     if (out2[i] != arrExp3[i]) { 
      puts("not same"); 
      return -1; 
     } 
    } 
    puts("same"); 

    node *tmp = search(&root, 55); 
    if (tmp) 
    { 
     printf("Searched node=%d\n", tmp->data); 
    } 
    else 
    { 
     printf("Data Not found in tree.\n"); 
    } 

    /* Deleting all nodes of tree */ 
    deltree(root); 

    return 0; 
} 

---

。
サンプルコード：

n = sizeof(arr2)/sizeof(*arr2);//length of arr2 
for (i = 0; i < n; i++) 
    insert(&root, arr2[i]);//values of arr2 add to tree 

n = print_preorder(root);puts("");//number of elements of tree 

int out4[n];//new array for store tree to array 
ap = out4; 
outToArrayPorder(root, &ap); 

if(sizeof(out4) == sizeof(arrExp4) && memcmp(out4, arrExp4, sizeof(out4))==0)//Each size may not be equal. 
    puts("same4"); 
else 
    puts("not same"); 

Answer 2

明らかに期待通りに動作しているか、あなたのコードは、停止に設計されています。あなたはたぶんテストを他の方法で書いたでしょう。 search関数は、それ自体（リターン検索（...））の結果を返すことによって反復する修正されていたら

は、このコードが実行される：

// insert node 4 on tree 
insert(&root, 4); 

// check if tree nodes are now equal to arrExp that has now the 4 node 

を今：あなたはapに11ノードを出力しています10個の数字のために予約されたエリアを指しています。明らかにこのはの仕事をすることはできません。この場合、は、スタック上の次の変数を上書きしているため、が動作する（つまりクラッシュしない）と表示されます。

でも、11要素ツリーを10要素ベクトル（arr）と比較しています。彼らは単に等しいことはできません。

（ところで、あなたは再びARRのqsortする必要はありません）：

outToArray(root, &ap); 
qsort(arr, n, sizeof(*arr), cmp); 
for (i = 0; i < n; i++) { 
    if (arr[i] != arrExp[i]) { 
     puts("not same"); 
     return -1; 
    } 
} 
puts("same"); 

もちろん、上記のコードは、ARRではありません「4」の要素を、見つける出力「と同じではない」と停止します。おそらくたかった：

int arrExp[sizeof(arr)/sizeof(*arr) + 2]; 

あなたはそれで11個の要素を置くつもりだので、そこであなたは、arrにaporderポイントを作ることができません：あなたは仕事するのに十分なスペースを保持するための配列を修正する必要があり

outToArray(root, &ap); 
for (i = 0; i < n; i++) { 
    if (arr[i] != arrExp[i]) { 
     break; 
    } 
} 
if (i == n) { 
    puts("same. This should not happen"); 
    exit(1); 
} else { 
    puts("not same, as expected."); 
} 

をこれはスタックに上書きされる11要素をarrに書き込むことを意味します（そしてすべてのもののrootの値！）。あなたが値を変更する必要はありませんので、

int *aporder = arrExp; 

最後に、あなたがsearch()機能を簡素化することができますして指摘しました。私はいくつかのデバッグコードを追加しました：

node* search(node *tree, int val) 
{ 
    printf("Start %08lx\n", tree); 
    if (tree) { 
      if (val < tree->data) 
      { 
       printf("%d less than %d, going left\n", val, tree->data); 
       return search(tree->left, val); 
      } 
      if(val > tree->data) 
      { 
       printf("%d more than %d, going right\n", val, tree->data); 
       return search(tree->right, val); 
      } 
    } 
    return tree; 
}