treepremidpost.c

C语言实现的数操作

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#define TREE_TYPE int

typedef struct TREE_NODE{
	TREE_TYPE value;
	struct TREE_NODE *left;
	struct TREE_NODE *right;
}TreeNode;

static TreeNode  *tree;

void insert(TREE_TYPE value)
{
	TreeNode *current;
	TreeNode **link;

	link = &tree;

	while(( current =*link)!=NULL)
	{
		if(value < current->value)
			link =&current->left;
		else
		{
			assert(value !=current->value);
			link=&current->right;
		}
	}

	current = malloc(sizeof(TreeNode));
	assert(current !=NULL);
	current->value = value;
	current->left =NULL;
	current->right = NULL;
	*link = current;
}

TreeNode *find(TREE_TYPE value)
{
	TreeNode *current;
	current = tree;
	while(current !=NULL && current->value != value)
	{
		if(value < current->value)
		{
			current = current->left;
		}
		else
		{
			current = current->right;
		}
	}
	if(current != NULL)
		return current;
	else
		return NULL;
}
TreeNode *find_parent(TREE_TYPE value)
{
	TreeNode *current;
	TreeNode *parent;
	current = tree;
	while(current !=NULL && current->value != value)
	{
		if(value < current->value)
		{
			parent=current;
			current = current->left;
		}
		else
		{
			parent=current;
			current = current->right;
		}
	}
	if(current != NULL)
		return parent;
	else
		return NULL;
}

void delete(TreeNode *current,TreeNode *parent,TreeNode *delNode)
{
	TreeNode *s,*q;
	int fag	= 0;
	if(delNode->left == NULL)
		s = delNode->right;
	else if(delNode->right == NULL)
		s = delNode->left;
	else 
	{
		q=delNode;
		s=delNode->left;
		while(s->right != NULL)
		{
			q=s;
			s=s->right;
		}
		if(q=delNode)
		{
			q->left=s->left;
		}
		else 
			q->right=s->left;
		delNode->value = s->value;
		free(s);
		fag=1;
	}
	if(fag==0)
	{
		if(parent==NULL)
			current=s;
		else if(parent->left==delNode)
			parent->left=s;
		else
			parent->right=s;
		free(delNode);
	}
}

void print(TREE_TYPE value)
{
	printf("value is %d\n",value);
}

static void do_pre_order_traverse(TreeNode *current,void (*callback)(TREE_TYPE value))
{
	if(current != NULL)
	{
		callback(current->value);
		do_pre_order_traverse(current->left,callback);
		do_pre_order_traverse(current->right,callback);
	}
}

static void do_mid_order_traverse(TreeNode *current,void (*callback)(TREE_TYPE value))
{
	if(current != NULL)
	{
		do_mid_order_traverse(current->left,callback);
		callback(current->value);
		do_mid_order_traverse(current->right,callback);
	}
}

static void do_post_order_traverse(TreeNode *current,void (*callback)(TREE_TYPE value))
{
	if(current != NULL)
	{
		do_post_order_traverse(current->left,callback);
		do_post_order_traverse(current->right,callback);
		callback(current->value);
	}
}

static void do_level_order_traverse(TreeNode *current,void (*callback)(TREE_TYPE value))
{
	TreeNode q[30];
	int front=0;
	int rear=0;
	if(current != NULL)
	{
		rear++;
		q[rear]=*current;
	}
	while(front!=rear)
	{
		front++;
		current=&q[front];
		callback(current->value);
		if(current->left != NULL)
		{
			rear++;
			q[rear]=*current->left;
		}
		if(current->right!=NULL)
		{
			rear++;
			q[rear]=*current->right;
		}
	}
}

static do_mid_order_count(TreeNode *current,void (*callback)(TREE_TYPE value))
{
	static countnode;
	static countleaf;
	if(current != NULL)
	{
		do_mid_order_count(current->left,callback);
		countnode++;
		print(current->value);
		printf("countnode=%d\n",countnode);
		if((current->left == NULL) && (current->right == NULL))
		{
			countleaf++;
			printf("countleaf=%d\n",countleaf);
			do_mid_order_count(current->right,callback);
		}
	}
}

static do_pre_order_deep(TreeNode *current,int j,void (*callback)(TREE_TYPE value))
{
	static int k;
	if(current != NULL)
	{
		print(current->value);
		j++;
		if(k<j)
			k=j;
		printf("deep=%d\n",k);
		do_pre_order_deep(current->left,j,callback);
		do_pre_order_deep(current->right,j,callback);
	}
}

void pre_order_traverse(void (*callback)(TREE_TYPE value))
{
	do_pre_order_traverse(tree,callback);
}

void mid_order_traverse(void (*callback)(TREE_TYPE value))
{
	do_mid_order_traverse(tree,callback);
}

void post_order_traverse(void (*callback)(TREE_TYPE value))
{
	do_post_order_traverse(tree,callback);
}

void level_order_traverse(void (*callback)(TREE_TYPE value))
{
	do_level_order_traverse(tree,callback);
}

void mid_order_count(void (*callback)(TREE_TYPE value))
{
	do_mid_order_count(tree,callback);
}

void pre_order_deep(int j,void (*callback)(TREE_TYPE value))
{
	do_pre_order_deep(tree,j,callback);
}

void tree_delete(TREE_TYPE value)
{
	TreeNode *delNode;
	TreeNode *parNode;
	delNode=find(value);
	parNode=find_parent(value);
	if(delNode != NULL)
	{
		delete(tree,parNode,delNode);
		printf("delete sucessfull!\n");
	}else
		printf("delete faile!\n");

}
int main()
{
	int i;
	for(i=30;i<40;i++)
		insert(i);
	for(i=29;i>10;i--)
		insert(i);

	pre_order_traverse(print);

	printf("middle\n");
	mid_order_traverse(print);

	printf("post\n");
	post_order_traverse(print);

	printf("level\n");
	level_order_traverse(print);

	printf("mid count\n");
	mid_order_count(print);

	printf("deep count\n");
	pre_order_deep(0,print);
	
	printf("tree delete\n");
	tree_delete(23);
	tree_delete(21);
	tree_delete(15);
	tree_delete(13);
	tree_delete(16);
	tree_delete(17);
	mid_order_traverse(print);
	
	return 0;
}