二叉树

#include<stdio.h>#include<stdlib.h>typedef struct Node{//结点类型	int data;	struct Node* left;	struct Node* right;}Node;typedef struct Tree{//二叉树的类型	Node*root;//指向根结点的指针	int count;//记录结点个数}Tree;//1 创建结点Node*CreateNode(int data){	Node*pn = (Node*)malloc(sizeof(Node));	pn->data = data;	pn->left = NULL;	pn->right = NULL;	return pn;}//2 插入新结点void Insert(Node**PRoot,Node*pNew);void InsertData(Tree*pt,int data){	Insert(&pt->root,CreateNode(data));//根结点需要指向新的插入结点，根结点指针发生变化 需要二级指针	pt->count++;}void Insert(Node**pRoot,Node*pNew){//递归插入	if(NULL==*pRoot)	{//空树  结束条件 		*pRoot = pNew;	}	else if(pNew->data<(*pRoot)->data)	{//与根结点比较选择正确的位置继续递归插入		Insert(&(*pRoot)->left,pNew);	}	else	{		Insert(&(*pRoot)->right,pNew);	}}//3 遍历void Travel(Node*root);void TravelData(Tree*pt){	Travel(pt->root);	printf("/n");}void Travel(Node*root){	if(NULL!=root)	{		Travel(root->left);//左		printf("%d ",root->data);//中 直接打印		Travel(root->right);//右	}}// 4 清空二叉树void Clear(Node**pRoot);void ClearData(Tree*pt){	Clear(&pt->root);	pt->count = 0;}void Clear(Node**pRoot){	if(NULL!=*pRoot)	{		Clear(&(*pRoot)->left);		Clear(&(*pRoot)->right);		free(*pRoot);		*pRoot = NULL;	}}// 5 查找Node**Find(Node**pRoot,int data);Node**FindData(Tree*pt,int data){//返回的是结点指针的地址	return Find(&pt->root,data);}Node**Find(Node**pRoot,int data){	if(NULL==*pRoot)	{//空树		return pRoot;	}	else if(data==(*pRoot)->data)	{		return pRoot;	}	else if(data<(*pRoot)->data)	{//左树中查找 		return Find(&(*pRoot)->left,data);	}	else		return Find(&(*pRoot)->right,data);}// 6 删除void Delete(Tree*pt,int data){	Node** pn = FindData(pt,data);	if(NULL==*pn)	{		printf("%d not exist/n",data);		return ;	}	if((*pn)->left!=NULL)	{//空树不用插入		Insert(&(*pn)->right,(*pn)->left);//把左子树插入到右子树中	}	Node*q = *pn; // 保存	*pn = (*pn)->right;//把 连接好的小二叉树    插入到上一个根结点上	free(q);	q = NULL;	pt->count--;}// 7 修改 void Modify(Tree*pt,int data,int newData){	Delete(pt,data);	InsertData(pt,newData);}// 8 判空int Isempty(Tree*pt){	return NULL == pt->root;}// 9 大小int Size(Tree*pt){	return pt->count;}// 10 取得根结点的值int GetRoot(Tree*pt){	if(!Isempty(pt))		return pt->root->data;	return -1;}int main(){	Tree tree;	tree.root = NULL;	tree.count = 0;	InsertData(&tree,10);	TravelData(&tree);	InsertData(&tree,20);	TravelData(&tree);	InsertData(&tree,8);	TravelData(&tree);	InsertData(&tree,25);	TravelData(&tree);	printf("---------------/n");	//ClearData(&tree);//	Delete(&tree,15);//	Delete(&tree,20);	Modify(&tree,20,5);	TravelData(&tree);	printf("the root is %d/n",GetRoot(&tree));	printf("count = %d/n",Size(&tree));	printf("%s/n",(Isempty(&tree))?"empty":"not empty");	ClearData(&tree);	printf("%s/n",(Isempty(&tree))?"empty":"not empty");	return 0;}