h現在のコードはツリーのパラメーターを考慮していないため、作成プロセスは停止しません。それを考慮に入れる必要があります。ツリーを作成するために指定したルールも、実際には完全ではありません。データ値がゼロのノードで何が起こるかを定義していません。
ツリーのような構造を開発する場合、利用可能な構造を解放するコードと、構造を出力する関数を用意する価値があります。私が含めたのは特殊なケースのバージョンで、(FILE *引数を取る代わりに) 標準出力のみに書き込み、出力される構造を識別するためのタグはありません。通常、私のツリー ダンプ関数には署名がありますがvoid dump_tree(FILE *fp, const char *tag, struct node *tree);、以下に示すコードを一般化するのは簡単です。
コード
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
/*
** h is the height of the tree and x is the key of the root node.
**
** To dynamically create the tree, the rules are as follows:
**
** - The root node is x.
** - If the parent node is x, then the children will be x - 1 (left), 1 (right).
** - If the parent node is x - 1, then the children will be x - 1 (left) and 1 (right).
** - If the parent node is 1, then the children will be x (left) and 0 (right).
** - If the parent node is 0, then the child pointers will be null.
** - When the nodes are at level h in the tree, the child pointers will be null.
*/
struct node
{
int data;
struct node *left;
struct node *right;
};
/* Create a tree with value v at with d levels below it with the parameter x */
static struct node *create_node(int x, int d, int v)
{
struct node *n = malloc(sizeof(*n));
if (n == 0)
{
fprintf(stderr, "Out of memory\n");
exit(1);
}
n->data = v;
if (d == 0 || v == 0)
{
n->left = 0;
n->right = 0;
}
else if (v == x || v == x - 1)
{
n->left = create_node(x, d-1, x-1);
n->right = create_node(x, d-1, 1);
}
else if (v == 1)
{
n->left = create_node(x, d-1, x);
n->right = create_node(x, d-1, 0);
}
else
assert(0);
return n;
}
static void print_node(struct node *tree)
{
putchar('(');
if (tree->left)
print_node(tree->left);
printf("[%d]", tree->data);
if (tree->right)
print_node(tree->right);
putchar(')');
}
static void print_tree(struct node *tree)
{
print_node(tree);
putchar('\n');
}
static int path_products(struct node *tree)
{
if (tree->left == 0 && tree->right == 0)
{
//printf("Leaf node: %d\n", tree->data);
return tree->data;
}
else
{
int lhs = path_products(tree->left);
int rhs = path_products(tree->right);
int rv = tree->data * (lhs + rhs);
//printf("Interior node: lhs = %d, rhs = %d, data = %d, return %d\n", lhs, rhs, tree->data, rv);
return rv;
}
}
static void release_tree(struct node *tree)
{
if (tree == 0)
return;
release_tree(tree->left);
release_tree(tree->right);
free(tree);
}
int main(int argc, char **argv)
{
if (argc != 3)
{
fprintf(stderr, "Usage: %s height root\n", argv[0]);
exit(1);
}
int h = atoi(argv[1]);
if (h <= 0)
{
fprintf(stderr, "Invalid height %s (should be greater than zero)\n", argv[1]);
exit(1);
}
int x = atoi(argv[2]);
if (x <= 2)
{
fprintf(stderr, "Invalid root value %s (should be greater than two)\n", argv[2]);
exit(1);
}
struct node *tree = create_node(x, h-1, x);
print_tree(tree);
printf("Sum of products of paths = %d\n", path_products(tree));
release_tree(tree);
return 0;
}
サンプル出力
$ tree 1 4
([4])
H = 1, X = 4: Sum of products of paths = 4
$ tree 2 4
(([3])[4]([1]))
H = 2, X = 4: Sum of products of paths = 16
$ tree 3 4
((([3])[3]([1]))[4](([4])[1]([0])))
H = 3, X = 4: Sum of products of paths = 64
$ tree 4 4
(((([3])[3]([1]))[3](([4])[1]([0])))[4]((([3])[4]([1]))[1]([0])))
H = 4, X = 4: Sum of products of paths = 256
$ tree 5 4
((((([3])[3]([1]))[3](([4])[1]([0])))[3]((([3])[4]([1]))[1]([0])))[4](((([3])[3]([1]))[4](([4])[1]([0])))[1]([0])))
H = 5, X = 4: Sum of products of paths = 1024
$ tree 6 4
(((((([3])[3]([1]))[3](([4])[1]([0])))[3]((([3])[4]([1]))[1]([0])))[3](((([3])[3]([1]))[4](([4])[1]([0])))[1]([0])))[4]((((([3])[3]([1]))[3](([4])[1]([0])))[4]((([3])[4]([1]))[1]([0])))[1]([0])))
H = 6, X = 4: Sum of products of paths = 4096
$
ツリー ダンプの形式は明確ですが、これに慣れていない人には不可解です。複数行に渡って出力する汎用のツリー ダンプを作成するのは、かなり難しい作業です。
$ for j in {3..7}; do for i in {1..5}; do ./tree $i $j; done; done | grep -v '^(' | so
H = 1, X = 3: Sum of products of paths = 3
H = 2, X = 3: Sum of products of paths = 9
H = 3, X = 3: Sum of products of paths = 27
H = 4, X = 3: Sum of products of paths = 81
H = 5, X = 3: Sum of products of paths = 243
H = 1, X = 4: Sum of products of paths = 4
H = 2, X = 4: Sum of products of paths = 16
H = 3, X = 4: Sum of products of paths = 64
H = 4, X = 4: Sum of products of paths = 256
H = 5, X = 4: Sum of products of paths = 1024
H = 1, X = 5: Sum of products of paths = 5
H = 2, X = 5: Sum of products of paths = 25
H = 3, X = 5: Sum of products of paths = 125
H = 4, X = 5: Sum of products of paths = 625
H = 5, X = 5: Sum of products of paths = 3125
H = 1, X = 6: Sum of products of paths = 6
H = 2, X = 6: Sum of products of paths = 36
H = 3, X = 6: Sum of products of paths = 216
H = 4, X = 6: Sum of products of paths = 1296
H = 5, X = 6: Sum of products of paths = 7776
H = 1, X = 7: Sum of products of paths = 7
H = 2, X = 7: Sum of products of paths = 49
H = 3, X = 7: Sum of products of paths = 343
H = 4, X = 7: Sum of products of paths = 2401
H = 5, X = 7: Sum of products of paths = 16807
$