ポインター演算で混乱しています。ツリー トラバーサル関数を作成したいのですが、ツリー内の離れたノードを取得するためのポインター演算についてはよくわかりません。コードで見るとより明確になるので、ここに示します。
node **root = huffman_tree(probabilities); // I can only return that as a double ptr
ルート ノードからのデータが必要な場合:
printf("%lf", (*root)->data);
ルートの子からのデータが必要な場合:
printf("%lf", (*root)->left->data); // or (*root)->right->data
しかし、さらに詳細な検索を行いたい場合、それらのノードに到達する方法がわかりません。
printf("%lf", (*root)->left->left->data); // thats not working
また、ツリー トラバーサルの場合、これは機能しません。プログラムがクラッシュします。
node **root = huffman_tree(probabailities);
preorder(*root);
void preorder(node *n){
if(n == NULL) return;
printf("%lf", n->data);
preorder(n->left);
preorder(n->right);
}
上記の例では、プログラムがクラッシュします。
更新 1:
huffman_tree() が実際に破損したノードを含むツリーを返しているようです。それらのメモリ割り当てを間違って行っているに違いありません。
この関数には確率の配列が渡され、次のようにステップが取得されます。
1) 指定された確率でノードを作成します (n 確率 --> n 新しいノード) [正常に動作します]
2）確率が最も低い2つのノードを見つけます[正常に動作します] 3）確率が最も低い2つのノードの親である新しいノードを作成します
4) その子ノードの確率の合計に等しい新しいノード確率を割り当てます
5) 親のないノードが 1 つだけになるまで、手順 2) から繰り返します。
node **huffman_tree(double *probabs){
int num_of_nodes = NUM_OF_SYMBOLS;
int num = NUM_OF_SYMBOLS;
// 1) create nodes for given probabilities
node *leafs = (node*) malloc(num_of_nodes*sizeof(node));
int i;
for(i=0; i<num_of_nodes; i+=1){
node *n = (node *) malloc(sizeof(node));
n->probab = *(probabs + i);
n->symbol = *(SYMBOLS + i);
n->left = NULL;
n->right = NULL;
*(leafs+i) = *n;
//free(n);
}
node **root;
while(num_of_nodes > 1){
// 2) Find the two nodes with lowest probabilities
node *two_mins =(node *)malloc(2*sizeof(node));
two_mins = find_two_mins(leafs, num_of_nodes);
node min_n1 = two_mins[0];
node min_n2 = two_mins[1];
// 3) Create a parent node with probability equals to sum of its children probabilities
// add a parent node to leafs
node *new_node = (node *) malloc(sizeof(node));
new_node->probab = min_n1.probab + min_n2.probab;
new_node->left = &min_n1;
new_node->right = &min_n2;
leafs = add_node(leafs, new_node, num);
num += 1;
leafs = remove_node(leafs, &min_n1, num);
num -= 1;
leafs = remove_node(leafs, &min_n2, num);
num -= 1;
num_of_nodes -= 1;
root = &new_node;
}
return root;
関数 add_node() [正常に動作しているようです]
node *add_node(node *nodes, node *n, int num){
nodes = realloc(nodes, (num+1)*sizeof(node));
nodes[num] = *n;
return nodes;
関数 remove_node() [正常に動作しているようです]
node *remove_node(node *nodes, node *n, int num){
int i;
int index = 0;
for(i=0; i<num; i+=1){
if(nodes_are_equal(nodes[i], *n)) index = i;
}
for(i=index; i<num-1; i+=1){
nodes[i] = nodes[i+1];
}
nodes = realloc(nodes, (num-1)*sizeof(node));
return nodes;
更新 2
huffman_tree() 関数のいくつかを変更しました。
関数 find_two_mins() はもう存在しませんが、一度に 1 つの最小ノードのみを検出する別の関数 find_min() の 2 つの呼び出しに置き換えられます。また、この関数は、動的に割り当てられたノードへのポインターを受け取り、最小値が見つかった後、それを返します。
node *root;
while(num_of_nodes > 1){
// 2) Find two min nodes
node *min_n1= (node *)malloc(sizeof(node));
node*min_n2= (node *)malloc(sizeof(node));
*min_n1= *find_min(leafs, num, min_n1);
leafs = remove_node(leafs, min_n1, num);
num -= 1;
*min_n2= *find_min(leafs, num, min_n2);
leafs = remove_node(leafs, min_n2, num);
num -= 1;
printf("\nTwo Min Nodes: %lf\t%lf", min_n1->probab, min_n2->probab);
printf("\nSum Of All: %lf", s);
// 3) Create parent node of two min nodes
node *new_node = (node *) malloc(sizeof(node));
new_node->probab= min_n1->probab+ min_n2->probab;
new_node->left = min_n1;
new_node->right = min_n2;
leafs = add_node(leafs, new_node, num);
num += 1;
free(min_n1);
free(min_n2);
num_of_nodes -= 1;
root = new_node;
printf("root=%p\n", root);
printf("*root=%p\n", *root);
}
return root;
そして、ここに find_min() 関数があります:
node *find_min(node *nodes, int num, node *min_node){
double min_probab = nodes[0].probab;
*min_node= nodes[0];
int i;
for(i=0; i<num; i+=1){
if(nodes[i].probab< min_probab){
min_probab = nodes[i].probab;
*min_node = nodes[i];
}
}
return min_node;
問題はこの出力に関する何かのようです:
printf("root=%p\n", root);
printf("*root=%p\n", *root);
「root = 003A17F0」と「*root = 00000000」が出力されるので
また、プログラムがどのように実行されるかのスクリーンショットを提供しています。ここでは、任意の時点でのルート値を確認できます。
