二叉树的基本操作

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

#define TRUE 1
#define FALSE 0


typedef int datatype;
typedef struct node
{
	datatype data;
	struct node *lchild, *rchild;
}btree;

void creat_btree(btree **bt);
void preorder_btree(btree *bt);
void inorder_btree(btree *bt);
void postorder_btree(btree *bt);
int depth_btree(btree *bt);
void free_btree(btree **bt);
int find_btree(btree *bt, datatype x);
void exchange_btree(btree *bt);
void travel_btree(btree *bt);

int main (int argc, char *argv[])
{
	btree *bt = NULL;
	creat_btree(&bt);
	preorder_btree(bt);
	putchar(‘\n‘);
	/*
	inorder_btree(bt);
	putchar(‘\n‘);
	printf("%d\n",depth_btree(bt));
	free_btree(&bt);
	preorder_btree(bt);
	putchar(‘\n‘);
	*/
	exchange_btree(bt);
	preorder_btree(bt);
	putchar(‘\n‘);
	travel_btree(bt);
	putchar(‘\n‘);
	//printf("%d\n",find_btree(bt,8));
	return 0;
}

void creat_btree(btree **bt)
{
	int n;
	scanf("%d",&n);
	if(n == 0){
		return;
	}
	else{
		*bt = (btree*)malloc(sizeof(btree));
		(*bt)->data = n;
		(*bt)->lchild = NULL;
		(*bt)->rchild = NULL;
		
		creat_btree(&(*bt)->lchild);
		creat_btree(&(*bt)->rchild);
	}
}

void preorder_btree(btree *bt)//前序遍历
{
	if(bt != NULL){
		printf("%d,",bt->data);
		preorder_btree(bt->lchild);
		preorder_btree(bt->rchild);
	}
}

void inorder_btree(btree *bt)//中序遍历
{
	if(bt != NULL){
		inorder_btree(bt->lchild);
		printf("%d,",bt->data);
		inorder_btree(bt->rchild);
	}
}

void postorder_btree(btree *bt)//后序遍历
{
	if(bt != NULL){
		postorder_btree(bt->lchild);
		postorder_btree(bt->rchild);
		printf("%d,",bt->data);
	}
}

//树的先序遍历非递归算法
/*
	if(跟不空){
		根入栈;
	}
	while(栈不空){
		出栈；
		访问出栈节点；
		右子树入栈；
		左子树入栈；
	}
*/

void travel_btree(btree *bt)//栈实现二叉数的遍历
{
	btree* stack[50];
	btree* temp;
	int top = 0;
	if(bt){
		stack[top] = bt;
		top++;
	}
	while(top > 0){
		top--;
		temp = stack[top];
		printf("%d,",stack[top]->data);
		
		if(temp->rchild != NULL){
			stack[top] = temp->rchild;
			top++;
		}
		
		if(temp->lchild != NULL){
			stack[top] = temp->lchild;
			top++;
		}
	}
}
int depth_btree(btree *bt)//二叉树深度
{
	int ldepth = 0, rdepth = 0;
	if(bt == NULL)
		return 0;
	ldepth = depth_btree(bt->lchild)+1;
	rdepth = depth_btree(bt->rchild)+1;
	return ldepth >= rdepth ? ldepth : rdepth;
}

void free_btree(btree **bt)//释放二叉树
{
	if(*bt != NULL){
		free_btree(&(*bt)->lchild);
		free_btree(&(*bt)->rchild);
		free(*bt);
		*bt = NULL;
	}
}

int find_btree(btree *bt, datatype x)//查找二叉树中是否有某个节点
{	
	if(bt != NULL){	
		if(x == bt->data){
			return TRUE;
		}
		else{ 	
			if(find_btree(bt->lchild,x) || find_btree(bt->rchild,x))
				return TRUE;
			return FALSE;	
		}	
	}	
}

void exchange_btree(btree *bt)//交换二叉数
{
	btree* temp;
	if(bt != NULL){
		exchange_btree(bt->lchild);
		exchange_btree(bt->rchild);
		temp = bt->lchild;
		bt->lchild = bt->rchild;
		bt->rchild = temp;
	}	
}

二叉树的基本操作

原文：http://blog.csdn.net/a987860319/article/details/19046763