【AOJ ALDS1_7】C: Tree - Tree Walk

問題

Tree Walk | Aizu Online Judge

方針

• 二分木を実装する.
• 行きかけ順(Preorder Tree Walk), 通りかけ順(Inorder Tree Walk), 帰りがけ順(Postorder Tree Walk)を実装する.
• 行きかけ順は, 根（接点）→左部分木→右部分木の順で出力を行う.
• 通りかけ順は左部分木→根（節点）→右部分木の順で出力を行う.
• 帰りがけ順は, 左部分木→右部分木→根（節点）の順で出力を行う.

コード

#include<iostream>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define NIL -1
#define MAX 30
 
using namespace std;
 
struct Node{
  int parent, left, right;
};
 
Node node[MAX];
 
void preorder(int u){
  if(u == NIL) return;
 
  cout << " " << u;
  preorder(node[u].left);
  preorder(node[u].right);  
}
 
void inorder(int u){
  if(u == NIL) return;
  inorder(node[u].left);
  cout << " " << u;
  inorder(node[u].right);
}
 
void postorder(int u){
  if(u == NIL) return;
  postorder(node[u].left);
  postorder(node[u].right);
  cout << " " << u;
}
 
void init(){
  rep(i, MAX){
    node[i].left = node[i].right = node[i].parent = NIL;
  }
}
 
signed main(){
  int n;
  int id, l, r;
  cin >> n;
  init();
  rep(i, n){
    cin >> id >> l >> r;
    node[id].left = l;
    node[id].right = r;
     
    if(l != NIL) node[l].parent = id;
    if(r != NIL) node[r].parent = id;
  }
   
  int root = 0;
  rep(i, n){
    if(node[i].parent == NIL){
      root = i; 
      break;
    }
  }
  cout << "Preorder" << endl;
  preorder(root);
  cout << "\n";
  cout << "Inorder" << endl;
  inorder(root);
  cout << "\n";
  cout << "Postorder" << endl;
  postorder(root);
  cout << "\n";
 
}
``