AOJ Problem Set from ALDS1 問20～24 - c21coterie @ ウィキ

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");
	}
}