読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

1001 : Binary Tree Intersection And Union

問題リンク:Binary Tree Intersection And Union | Aizu Online Judge

解法:
実際に2つ木を作って指定された処理を行った
配列で2分木を実装するとノードが最大100個なので配列内に収まらない
なのでポインタを使って実装した

struct Tree
{
  bool child[2];//child[0] -> 左の子が存在するか, child[1] -> 右の子が存在するか
  Tree *next[2];//next[0] -> 左の子のポインタ, next[1] -> 右の子のポインタ 
};

久しぶりにポインタ使ったけど案外思い通りに動いてくれて楽しかった

コード:

struct Tree
{
  bool root;
  bool child[2];
  Tree *next[2];//left -> false, right -> true
  Tree()
  {
    child[0] = child[1] = false;
    root=false;
  }
};

string s[2];
Tree tree[2];

void ddfs(Tree *t)
{
  if(!t->child[0] && !t->child[1])return;
    
  if(t->child[0])
    {
      ddfs(t->next[0]);
      t->child[0] = false;
      delete t->next[0];
    }

  if(t->child[1])
    {
      ddfs(t->next[1]);
      t->child[1] = false;
      delete t->next[1];
    }
}

void init()
{
  tree[0].root = tree[1].root = true;
  rep(i,2)ddfs(&tree[i]);
}

void parse(int index,int &pos,Tree *t,int depth)
{
  if(pos >= s[index].size())return;
  bool LR = false;

  ++pos;
  while(pos < s[index].size() && !(LR && s[index][pos] == ')'))
    {

      if(s[index][pos] == '(')
	{
	  t->next[LR] = new Tree;
	  t->next[LR]->root = false;
	  t->next[LR]->child[0] = t->next[LR]->child[1] = false;
	  t->child[LR] = true;
	  parse(index,pos,t->next[LR],depth+1);
	  if(pos < s[index].size() && LR && s[index][pos] == ')')break;
	}
      if(s[index][pos] == ',') LR = true;
	
      ++pos;
    }
  ++pos;
}

void tree_walk(Tree *t,int depth)
{
  cout << '(';
  if(t->child[0])tree_walk(t->next[0],depth+1);
  cout << ',';
  if(t->child[1])tree_walk(t->next[1],depth+1);
  cout << ')';
}

void dfs_i(Tree *t1,Tree *t2,Tree *ans)
{
  if(t1->child[0] && t2->child[0])
    {
      ans->next[0] = new Tree;
      ans->child[0] = true;
      ans->next[0]->child[0] = ans->next[0]->child[1] = false;
      dfs_i(t1->next[0],t2->next[0],ans->next[0]);
    }

  if(t1->child[1] && t2->child[1])
    {
      ans->next[1] = new Tree;
      ans->child[1] = true;
      ans->next[1]->child[0] = ans->next[1]->child[1] = false;
      dfs_i(t1->next[1],t2->next[1],ans->next[1]);
    }

}

void dfs_u(Tree *t,Tree *ans)
{
  if(t->child[0])
    {
      if(ans->child[0])
	{//already exists
	  dfs_u(t->next[0],ans->next[0]);
	}
      else
	{//not yet
	  ans->next[0] = new Tree;
	  ans->child[0] = true;
	  ans->next[0]->child[0] = ans->next[0]->child[1] = false;
	  dfs_u(t->next[0],ans->next[0]);
	}
    }

  if(t->child[1])
    {
      if(ans->child[1])
	{//already exists
	  dfs_u(t->next[1],ans->next[1]);
	}
      else
	{//not yet
	  ans->next[1] = new Tree;
	  ans->child[1] = true;
	  ans->next[1]->child[0] = ans->next[1]->child[1] = false;
	  dfs_u(t->next[1],ans->next[1]);
	}
    }

}

void compute(char c)
{
  Tree ans;
  ans.root = true;
  ans.child[0] = ans.child[1] = false;
  if(c == 'i')
    {
      dfs_i(&tree[0],&tree[1],&ans);
      tree_walk(&ans,0);
      cout << endl;
    }
  else if(c == 'u')
    {
      dfs_u(&tree[0],&ans);
      dfs_u(&tree[1],&ans);
      tree_walk(&ans,0);
      cout << endl;
    }

  ddfs(&ans);
}


int main()
{
  char c;
  while(cin >> c)
    {
      cin >> s[0] >> s[1];
      init();

      int pos;
      rep(i,2)
	{
	  pos = 0;
	  parse(i,pos,&tree[i],0);
	}

      compute(c);
   
    }
  return 0;
}