技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。

�W−５

変数 root は次の図にある二分木の根を参照している。この二分木を次のＣ言語の関数で探索する。なお、構造体のメンバ left と right が0のときは子がないものとする。search(root, 34) という引数で関数を呼出し、終了した場合の変数 count の値を選べ。

struct nodes { int value; struct nodes *right, *left; };
typedef struct nodes *Node;

int count = 0;

int search( Node node, int value ) {
　count ++;
　if (node->value == value) return 0;
　if (node->right != 0 && search(node->right, value) == 0)
　　return 0;
　if (node->left != 0 && search(node->left, value) == 0)
　　return 0;
　return -1;
}

---

正解

�C

---

解説

1回目:search(root, 34) で呼び出した時、
node->value = 29, node->right = 45, node->left = 82である。
if (node->right != 0 && search(node->right, value)== 0) により、
search(45, 34) を呼び出し。

　2回目:search(45, 34) で呼び出した時
　node->value = 45, node->right = 82, node->left = 34である。
　if (node->right != 0 && search(node->right, value)== 0) により、
　search(82, 34) で呼び出し。

　　3回目:search(82, 34) で呼び出した時
　　node->value = 82, node->right = 56, node->left = 19である。
　　if (node->right != 0 && search(node->right, value)== 0) により、
　　search(56, 34) で呼び出し。

　　　4回目:search(56, 34) で呼び出した時
　　　node->value = 56, node->right = 0, node->left = 0である。
　　　return値 -1で返る。

　　if (node->left != 0 && search(node->left, value) == 0) により、
　　search(19, 34) で呼び出し。

　　　5回目:search(19, 34) で呼び出した時
　　　node->value = 19, node->right = 0, node->left = 0である。
　　　return値 -1で返る。

　　return値　-1で返る。

　if (node->left != 0 && search(node->left, value)== 0) により、
　search(34, 34) で呼び出し。

　　6回目:search(34, 34) で呼び出した時
　　node->value = 34, node->right = 0, node->left = 0である。
　　if (node->value == value) return 0; により、return値 0 で返る。

　return値　0で返る。

return値 0で返る。

従って6回。

�W−４

目次

�W−６

---