C言語での深さ優先探索の実装についての質問です。
下に添付してあるのは幅優先探索のコードです。
このコードを元に深さ優先探索を実装したいのですが、どのように実装すればようでしょうか。
わかる方、教えてください。
また、木構造のTextデータは下のとおりです。
txt
11 2 2 3 3 4 4 5 5 6 6
C
1#include <stdio.h> 2#include <stdlib.h> 3 4#define BUFSIZE 256 5 6struct node{ 7 int value; 8 struct node *left; 9 struct node *right; 10}; 11 12int search_breadth1(int key, struct node *remain[]){ 13 int idx = 0; 14 int last = 1; 15 16 while(remain[idx] != NULL){ 17 if(remain[idx]->value == key){ 18 return 1; 19 }else{ 20 if(remain[idx]->left != NULL){ remain[last++] = remain[idx]->left; } 21 if(remain[idx]->right != NULL){ remain[last++] = remain[idx]->right; } 22 idx++; 23 } 24 } 25 26 return 0; 27} 28 29int search_breadth(struct node *root, int key){ 30 struct node *remain[BUFSIZE]; 31 int i; 32 33 remain[0] = root; 34 for(i = 1; i < BUFSIZE; i++){ remain[i] = NULL; } 35 36 return search_breadth1(key, remain); 37} 38 39struct node *addnode(struct node *root, int depth, int val){ 40 struct node *n, *new; 41 42 new = (struct node *)malloc(sizeof(struct node)); 43 new->value = val; 44 new->left = new->right = NULL; 45 46 if(root == NULL){ 47 return new; 48 }else{ 49 n = root; 50 } 51 52 for( ; depth > 1; depth--){ 53 if(n->right != NULL){ 54 n = n->right; 55 }else if(n->left != NULL){ 56 n = n->left; 57 }else{ 58 return NULL; 59 } 60 } 61 62 if(n->left == NULL){ 63 n->left = new; 64 }else if(n->right == NULL){ 65 n->right = new; 66 }else{ 67 return NULL; 68 } 69 70 return root; 71} 72 73struct node *loaddata(char *filename){ 74 int depth, val; 75 FILE *input; 76 struct node *root = NULL; 77 char line[BUFSIZE]; 78 79 input = fopen(filename, "r"); 80 if(input == NULL){ 81 fprintf(stderr, "Can't open file: %s\n", filename); 82 exit(1); 83 } 84 85 while(fgets(line, sizeof(line), input) != NULL){ 86 depth = 0; 87 while(line[depth] == ' '){ 88 depth++; 89 } 90 91 sscanf(&line[depth], "%d", &val); 92 root = addnode(root, depth, val); 93 if(root == NULL){ 94 fprintf(stderr, "illegal input file: %s\n", line); 95 exit(1); 96 } 97 } 98 99 fclose(input); 100 101 return root; 102} 103 104int main(int ac, char **av){ 105 int result; 106 struct node *root; 107 108 if(ac != 3){ 109 fprintf(stderr, "Usage: %s <datafile> <key>\n", av[0]); 110 exit(1); 111 } 112 113 root = loaddata(av[1]); 114 115 result = search_breadth(root, atoi(av[2])); 116 117 printf("Key \"%s\" is %s.\n", av[2], result == 1 ? "found" : "not found"); 118 119 return 0; 120} 121
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。