간단한 트리의 귀속, 비귀속 생성, 앞뒤 순서 반복

4120 단어 비귀속
c 언어는 쓰기에 매우 감각적이다

#include<stdlib.h>
#define null 0
struct tree{
	struct tree* left;
	int value;
	struct tree* right;
};

typedef struct tree Tree;
Tree* root;

Tree* insert_rcs(Tree* root, int value){			
	//          
	if(root == null){	
		root = malloc(sizeof(Tree));
		root->value = value;
		root->left = null;
		root->right = null;	
		//         
		return root;
	}
	
	if(root->value > value){
		root->left = insert_rcs(root->left, value);
	}else{
		root->right = insert_rcs(root->right, value);
	}
	return root;
}

Tree* insert_no_rcs(Tree* root, int value){
	Tree* newnode = malloc(sizeof(Tree));
	newnode->value = value;
	newnode->left = null;
	newnode->right = null;
	if(root == null){
		root = newnode;
		return root;
	}
	//p      
	Tree* p = root;
	//p       ,pre            
	Tree* pre;
	while(p){
		pre = p;
		if(p->value > value){
			p = p->left;
		}else{
			p = p->right;
		}	
	}
	if(pre->value > newnode->value){
		pre->left = newnode;
	}else{
		pre->right = newnode;
	}
	return root;	
}

//     
void pre_print_rcs(Tree* root){
	if(root != null){
		printf("value: %d \t",root->value);
		pre_print_rcs(root->left);
		pre_print_rcs(root->right);
	}
}

Tree* Stack[20];
int top = -1;

//         
void pre_print_no_rcs(Tree* root){
	//top != -1          ,         
	while(root != null || top != -1){
		if(root != null){
			printf("%d \t",root->value);
			if(top+1 != 20){
				Stack[++top] = root;
				root = root->left;
			}
		}else{
			root = Stack[top--]->right;
		}	
	}
}

//    
void in_print_rcs(Tree* root){
	if(root != null){
		in_print_rcs(root->left);
		printf("value: %d \t",root->value);
		in_print_rcs(root->right);
	}
}

//         
void in_print_no_rcs(Tree* root){
	//top != -1          ,         
	while(root != null || top != -1){
		if(root != null){
			if(top+1 != 20){
				Stack[++top] = root;
				root = root->left;
			}
		}else{
			root = Stack[top--];
			printf("%d \t",root->value);
			root = root->right;
		}	
	}	
}

//    
void post_print_rcs(Tree* root){
	if(root != null){
		post_print_rcs(root->left);
		post_print_rcs(root->right);
		printf("value: %d \t",root->value);
	}
}

Tree* Q[20];
int front;
int rear;
//     
//      ,          
void level_print(Tree* root){
	front = rear = 0;
	if(root != null){
		Q[++rear] = root;
		while(rear != front){
			Tree* p = Q[++front];
			printf("%d \t",p->value);
			if(p->left != null){
				Q[++rear] = p->left;
			}
			if(p->right != null){
				Q[++rear] = p->right;
			}
		}
	}
}

Tree* create_no_rcs(int* list, int n){
	int i;
	for(i=0; i<n; i++){
		root = insert_no_rcs(root, list[i]);
	}
	return root;
}

Tree* create_rcs(int* list, int n){
	int i;
	for(i=0; i<n; i++){
		root = insert_rcs(root, list[i]);
	}
	return root;
}

int main(){
	int list[10] = {
		6,9,7,4,5,2,1,8,12,0
	};
	//root = create_no_rcs(list, 10);
 	root = create_rcs(list, 10);
	
	//pre_print_rcs(root);
	//pre_print_no_rcs(root);
	in_print_rcs(root);
	in_print_no_rcs(root);
	//post_print_rcs(root);
	
	//level_print(root);
	
	return 0;
}



좋은 웹페이지 즐겨찾기