「AOJ Problem Set from ALDS1 問20～24」の編集履歴（バックアップ）一覧はこちら

「AOJ Problem Set from ALDS1 問20～24」(2014/01/18 (土) 01:32:41) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*Tree - Tree Walk
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C&lang=jp
2分木をデータから組み立て順番に訪問した結果を出力する問題。


 #include<stdio.h>
 
 const int LIMIT=26;
 const int NIL=-1;
 struct node{
 	int p,right,left;
 };
 node Tree[LIMIT];
 
 
 void Preorder(int p){
 	if(p==-1)return;
 	printf(" %d",p);
 	Preorder(Tree[p].left);
 	Preorder(Tree[p].right);
 }
 void Inorder(int p){
 	if(p==-1)return;
 	Inorder(Tree[p].left);
 	printf(" %d",p);
 	Inorder(Tree[p].right);
 }
 void Postorder(int p){
 	if(p==-1)return;
 	Postorder(Tree[p].left);
 	Postorder(Tree[p].right);
 	printf(" %d",p);
 } 
 
 
 int main(){
 	int n,l,r,no;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)Tree[i].p=NIL;
 	for(int i=0;i<n;i++){
  		scanf("%d %d %d",&no,&l,&r);
 		Tree[no].left=l;
 		Tree[no].right=r;
 		Tree[l].p=Tree[r].p=no;
 	}
 	int p=0;
 	for(int i=0;i<n;i++)if(Tree[i].p==NIL)p=i;
 	printf("Preorder\n");
  	Preorder(p);
	printf("\nInorder\n");
  	Inorder(p);
 	printf("\nPostorder\n");
  	Postorder(p);
 	printf("\n");
 }


*Binary search trees - Binary Search Tree III
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_C
追加削除探索、要素のプリントといった２分木の最低限の機能を実装する問題。
削除のアルゴリズムがうまくいく理由があまりイメージできない。


 #include<stdio.h>
 #include<stdlib.h>
 
 struct node{
   struct node *right;
   struct node *left;
   struct node *parent;
   int key;
 };
 typedef struct node *Node;
 #define NIL NULL
 
 Node root;
  
 Node treeMinimum(Node x){
 	while(x->left != NIL)x=x->left;
 	return x;
 }
  
 Node treeSearch(Node u, int k){
 	while(u!=NIL){
 		if(u->key==k)break;
 		if(k<u->key){
  			u=u->left;
 		}else{
 			u=u->right;
 		}
 	}
 	return u;
 } 
 
 Node treeSuccessor(Node x){
 	if(x->right!=NIL){
 		return treeMinimum(x->right);
 	}
 	Node y=x->parent;
 	while(y!=NIL && x==y->right){
 		x=y;
 		y=y->parent;
 	}
 	return y;
 }
 
 void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z==NIL)return;
  if(z->left==NIL || z->right==NIL){
  	y=z;
  }else{
  	y=treeSuccessor(z);
  }
  if(y->left!=NIL){
  	x=y->left;
  }else{
  	x=y->right;
  }
  if(x!=NIL){
     x->parent=y->parent;
  }
  if(y->parent==NIL){
  	root=x;
   }else{
    	if(y==y->parent->left){
 		y->parent->left=x;
 	}else{
 		y->parent->right=x;
 	}
  }
   if(y!=z) z->key=y->key;
 }
 
 void insert(int k){
  Node y = NIL;
  Node x = root;
   Node z;
 
  z = (struct node*)malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  while(x!=NIL){
  	y=x;
 	if(z->key < x->key){
 		x=x->left;
 	}else{
 		x=x->right;
 	}
  }
  z->parent=y;
  if(y==NIL){
      root=z;
  }else{
  	if(z->key < y->key){
        	y->left=z;
        }else{
 		y->right=z;
 	}
   }
 } 
 
 void inorder(Node u){
 	if(u==NIL)return;
 	inorder(u->left);
 	printf(" %d",u->key);
 	inorder(u->right);
 } 
 void preorder(Node u){
 	if(u==NIL)return;
 	printf(" %d",u->key);
 	preorder(u->left);
 	preorder(u->right);
 } 
 
 
 int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
      }
   }
 
   return 0;
 }

*Tree - Tree Walk
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C&lang=jp
2分木をデータから組み立て順番に訪問した結果を出力する問題。


 #include<stdio.h>
 
 const int LIMIT=26;
 const int NIL=-1;
 struct node{
 	int p,right,left;
 };
 node Tree[LIMIT];
 
 
 void Preorder(int p){
 	if(p==-1)return;
 	printf(" %d",p);
 	Preorder(Tree[p].left);
 	Preorder(Tree[p].right);
 }
 void Inorder(int p){
 	if(p==-1)return;
 	Inorder(Tree[p].left);
 	printf(" %d",p);
 	Inorder(Tree[p].right);
 }
 void Postorder(int p){
 	if(p==-1)return;
 	Postorder(Tree[p].left);
 	Postorder(Tree[p].right);
 	printf(" %d",p);
 } 
 
 
 int main(){
 	int n,l,r,no;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)Tree[i].p=NIL;
 	for(int i=0;i<n;i++){
  		scanf("%d %d %d",&no,&l,&r);
 		Tree[no].left=l;
 		Tree[no].right=r;
 		Tree[l].p=Tree[r].p=no;
 	}
 	int p=0;
 	for(int i=0;i<n;i++)if(Tree[i].p==NIL)p=i;
 	printf("Preorder\n");
  	Preorder(p);
	printf("\nInorder\n");
  	Inorder(p);
 	printf("\nPostorder\n");
  	Postorder(p);
 	printf("\n");
 }


*Binary search trees - Binary Search Tree III
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_C
追加削除探索、要素のプリントといった２分木の最低限の機能を実装する問題。
削除のアルゴリズムがうまくいく理由があまりイメージできない。


 #include<stdio.h>
 #include<stdlib.h>
 
 struct node{
   struct node *right;
   struct node *left;
   struct node *parent;
   int key;
 };
 typedef struct node *Node;
 #define NIL NULL
 
 Node root;
  
 Node treeMinimum(Node x){
 	while(x->left != NIL)x=x->left;
 	return x;
 }
  
 Node treeSearch(Node u, int k){
 	while(u!=NIL){
 		if(u->key==k)break;
 		if(k<u->key){
  			u=u->left;
 		}else{
 			u=u->right;
 		}
 	}
 	return u;
 } 
 
 Node treeSuccessor(Node x){
 	if(x->right!=NIL){
 		return treeMinimum(x->right);
 	}
 	Node y=x->parent;
 	while(y!=NIL && x==y->right){
 		x=y;
 		y=y->parent;
 	}
 	return y;
 }
 
 void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z==NIL)return;
  if(z->left==NIL || z->right==NIL){
  	y=z;
  }else{
  	y=treeSuccessor(z);
  }
  if(y->left!=NIL){
  	x=y->left;
  }else{
  	x=y->right;
  }
  if(x!=NIL){
     x->parent=y->parent;
  }
  if(y->parent==NIL){
  	root=x;
   }else{
    	if(y==y->parent->left){
 		y->parent->left=x;
 	}else{
 		y->parent->right=x;
 	}
  }
   if(y!=z) z->key=y->key;
 }
 
 void insert(int k){
  Node y = NIL;
  Node x = root;
   Node z;
 
  z = (struct node*)malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  while(x!=NIL){
  	y=x;
 	if(z->key < x->key){
 		x=x->left;
 	}else{
 		x=x->right;
 	}
  }
  z->parent=y;
  if(y==NIL){
      root=z;
  }else{
  	if(z->key < y->key){
        	y->left=z;
        }else{
 		y->right=z;
 	}
   }
 } 
 
 void inorder(Node u){
 	if(u==NIL)return;
 	inorder(u->left);
 	printf(" %d",u->key);
 	inorder(u->right);
 } 
 void preorder(Node u){
 	if(u==NIL)return;
 	printf(" %d",u->key);
 	preorder(u->left);
 	preorder(u->right);
 } 
 
 
 int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
      }
   }
 
   return 0;
 }


*Heaps - Heap
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_A
とりあえず簡単なヒープを実装する問題。

 #include<stdio.h>
 
 int n,heap[1000]; 
 
 int main(){
 	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&heap[i]);
 	for(int i=1;i<=n;i++){
 		printf("node %d: key = %d, ",i,heap[i]);
  		if(i>1){
 			printf("parent key = %d, ",heap[i/2]);
 		}
 		if(2*i<=n){
 			printf("left key = %d, ",heap[i*2]);
 		}
 		if(2*i+1<=n){
 			printf("right key = %d, ",heap[2*i+1]);
  		}
 		printf("\n");
 	}
 }