简单的树的递归、非递归创建,前序中序后序遍历

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