解析木

質問

ノードの中身を表示しながらトラバースする関数
void preorder(NodePointer node);
void inorder(NodePointer node);
void postorder(NodePointer node);
を再帰を使って書きなさい。

という問題がとけません。どなたかアドバイスをください。
ちなみに、この関数以外は下のように作りました。

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

struct node {
struct node *right;
char key;
struct node *left;
};
typedef struct node * NodePointer;

void treeinitialize(void);
NodePointer makenode(char c);
void preorder(NodePointer node);
void inorder(NodePointer node);
void postorder(NodePointer node);

NodePointer head, tail;

int main(){
treeinitialize();

//テスト用の木を作成
head->right=makenode('+');
head->right->left=makenode('1');
head->right->right=makenode('*');
head->right->right->left=makenode('2');
head->right->right->right=makenode('3');

//トラバース
printf("preorder: ");
preorder(head->right);
printf("\n");

printf("inorder: ");
inorder(head->right);
printf("\n");

printf("postorder: ");
postorder(head->right);
printf("\n");

return 0;
}

void treeinitialize(void){
head=makenode(-1);
tail=makenode(-1);
head->right=tail;
head->left=tail;
}

//ノードを作成し、そのノードへのポインタを返す。
NodePointer makenode(char c){
NodePointer x;

x=malloc(sizeof(struct node));
x->key=c;
x->right=tail;
x->left=tail;

return x;
}

void preorder(NodePointer node){

}

void inorder(NodePointer node){

}

void postorder(NodePointer node){

}

回答No.2

Tasuke22

印刷は自分で考えてください。

ノードが分岐したら、それぞれ分岐先のノードで
自分を呼びます。つまり2つ呼ぶということです。

回答No.1

Tasuke22

再帰が分からないということですか？

コツは最初に終了のチェックを行い、終了して
たら-ノードが切れてたら-リターンすることで
終了ですね。
終了していなければ、印刷して、次のノードで
自分を呼び出します。呼び出した後にリターン
します。

各関数はノードのリンクのたどり方が違うだけ
ですね。

流石に後は自分で考えてください。

お礼

再帰は最初に終了チェックだったんですかぁ。
勉強になります！

あともう少し質問があるんですが、ノードを印刷するときは、
%cで大丈夫でしょうか？

あと、この問題は解析木を使う問題なんですが、枝が分岐するところの辿り方がわからないので教えてもらえないでしょうか？
（わかりにくい質問ですいません。。）