/*----------------------------------------
２分木の走査プログラム
-----------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
// NODE型の自己参照構造体の定義
typedef struct node {
struct node *left, *right; // 左右部分木へのポインタ
int key; // データ部
} NODE;
// ツリーのルートを保持するポインタ変数
NODE *root = NULL;
// 関数のプロトタイプ宣言
void GenerateTree(); // 木の生成
NODE *CreateNewNode( int ); // 新ノードの作成
void ShowTreeState(); // 木の表示
void Traverse( int, NODE* ); // 走査関数
// メイン関数
int main(void)
{
//(1) ツリーの作成
GenerateTree();
//(2) ツリーの状態表示
ShowTreeState();
//(3-1) 先行順走査の結果表示
printf("先行順： ");
Traverse( 1, root );
printf("\n");
//(3-2) 中間順走査の結果表示
printf("中間順： ");
Traverse( 2, root );
printf("\n");
//(3-3) 後行順走査の結果表示
printf("後行順： ");
Traverse( 3, root );
printf("\n");
return 0;
}
// ツリーの生成（高さ２の完全２分木を生成する）
void GenerateTree()
{
// ルートノードを作成
root = CreateNewNode(1);
// ルートの左右の子を作成
root->left = CreateNewNode(2);
root->right = CreateNewNode(3);
// ルートの左部分木の孫を作成
(root->left)->left = CreateNewNode(4);
(root->left)->right = CreateNewNode(5);
// ルートの右部分木の孫を作成
(root->right)->left = CreateNewNode(6);
(root->right)->right = CreateNewNode(7);
}
// 新規ノードの作成
NODE *CreateNewNode( int value )
{
NODE *newNode;
newNode = malloc( sizeof(NODE) );
newNode->key = value; // キー値を設定
newNode->left = NULL;
newNode->right = NULL;
return newNode; // 新規ノードのポインタを返す
}
// ツリーの状態を表現
void ShowTreeState()
{
// レベル０の表示
printf("%4d\n", root->key );
// レベル１の表示
printf("%2d%4d\n", (root->left)->key, (root->right)->key );
// レベル２の表示
NODE *leftChild = root->left, *rightChild = root->right;
printf("%d%2d%2d%2d\n",
(leftChild->left)->key, (leftChild->right)->key,
(rightChild->left)->key, (rightChild->right)->key );
}
// 走査関数
void Traverse( int type, NODE *n )
{
if (n == NULL) {
return;
}
switch (type) {
case 1:
printf("%2d", n->key);
Traverse(type, n->left);
Traverse(type, n->right);
break;
case 2:
Traverse(type, n->left);
printf("%2d", n->key);
Traverse(type, n->right);
break;
case 3:
Traverse(type, n->left);
Traverse(type, n->right);
printf("%2d", n->key);
break;
}
}