1.cpp

二叉树抽象数据类型的实现 问题说明：数据结构来实现二叉树具体函数功能的实现； 以及相关操作。

//*****************************
#include<stdio.h>             //
#include<string.h>            //
#include<malloc.h>			  //
#include<stdlib.h>            //
#define NULL 0                //
#define OK 1                  //
#define ERROR 0               //
#define OVERFLOW 0            //
#define TElemType int         //
#define QElemType BiTree      //
//*****************************

typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild,*rchild;				 //左右孩子指针
}BiTNode,*BiTree;

InitBiTree(BiTree &T){						
//创建空树
		T=NULL;                              
		return OK;
}//InitBiTree

DestroyBiTree(BiTree &T){
//销毁二叉树
	if(T)
		delete(T);								//销毁根节点
		DestroyBiTree(T->lchild);				//销毁左子树
	    DestroyBiTree(T->rchild);				//销毁右子树
        return OK;
}//DestroyBiTree

CreatBiTree(BiTree &T,int definition){
//按先序次序输入二叉树中节点的值,空格字符表示空树

//构造二叉链表表示的二叉树T
	if(definition=1){
		TElemType nodedata;
		printf("Enter the data of the tree node:");
		scanf("%d",&nodedata);
		if(nodedata==99)T=NULL;
		else{
			if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
		    T->data=nodedata;                  //生成根节点
			CreatBiTree(T->lchild,1);		   //构造左子树
			CreatBiTree(T->rchild,1);		   //构造右子树
		}
	}
	return OK;
}//CreatBiTree

void ClearBiTree(BiTree &T){
//清空二叉树
	if(T){
		ClearBiTree(T->lchild);					//清空左子树 
		ClearBiTree(T->rchild);				    //清空右子树 
		free(T);
		T=NULL;
	}
}//ClearBiTree

BiTreeDepth(BiTree &T){
//求二叉树深度
	int LeftBiTreedepth,RightBiTreedepth;		 //设左右两个深度/层次计数器
	if(T==NULL)
		return (0);								//当前结点指针为空则立即返回
	else{
		LeftBiTreedepth=BiTreeDepth(T->lchild); //遍历当前结点左子树
        RightBiTreedepth=BiTreeDepth(T->rchild);//遍历当前结点右子树
		if(LeftBiTreedepth<=RightBiTreedepth)   //从叶子起计数
			return (RightBiTreedepth+1);
		else
			return (LeftBiTreedepth+1);
	}
}//BiTreeDepth							

BiTree Root(BiTree &T){                         
//返回根结点 
	if(T!=NULL){
		return (T);
	}
	else
		return 0;
}//Root

int EQ(BiTree &T,int e){						
//判断结点是否在树中
	return (T->data)==e?OK:ERROR;
}

int Value(BiTree &T,TElemType e){				
//e是树中的结点，返回节点值
	if(T!=NULL){
		if(!EQ(T,e)){
		    Value(T->lchild,e);
			if(!EQ(T->lchild,e))
			Value(T->rchild,e);
		}
		return (T->data);
	}else return (0);
}//Value

int Assign(BiTree &T,TElemType e,TElemType value){
//e是树中的结点，将e赋值为value
    if(T!=NULL){
		if(!EQ(T,e)){
			EQ(T->lchild,e);
			EQ(T->rchild,e);
		}else T->data=value;
		return (T->data);
	}else return (0);
}//Assign

int PrintfElement(TElemType e){
//输出e的值
	printf("%d",e);
	printf("->");
	return OK;
}

PreOrderTraverse(BiTree &T,int Visit(TElemType e)){
//采用二叉链表存储结构，visit是对应数据元素操作的函数
//先序遍历二叉树T的递规算法，对数据的每个元素都调用函数visit
	if(T!=NULL){
		if(Visit(T->data))
			if(PreOrderTraverse(T->lchild,Visit))
				if(PreOrderTraverse(T->rchild,Visit))
					return OK;
		return ERROR;
	}else return OK;
}//PreOrderTraverse

InOrderTraverse(BiTree &T,int Visit(TElemType e)){
//采用二叉链表存储结构，visit是对应数据元素操作的函数
//中序遍历二叉树T的递规算法，对数据的每个元素都调用函数visit
	if(T!=NULL){
		if(InOrderTraverse(T->lchild,Visit))
			if(Visit(T->data))
				if(InOrderTraverse(T->rchild,Visit))
					return OK;
		return ERROR;
	}else return OK;
}//InOrderTraverse

PostOrderTraverse(BiTree &T,int Visit(TElemType e)){
//采用二叉链表存储结构，visit是对应数据元素操作的函数
//后序遍历二叉树T的递规算法，对数据的每个元素都调用函数visit
	if(T!=NULL){
		if(PostOrderTraverse(T->lchild,Visit))
			if(PostOrderTraverse(T->rchild,Visit))
				if(Visit(T->data))
					return OK;
		return ERROR;
	}else return OK;
}//PostOrderTraverse

//------------------------------------------------------------------
//创建队列
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
	QueuePtr front;									//队头指针 
	QueuePtr rear;								    //对尾指针 
}LinkQueue;

InitQueue(LinkQueue&Q){
//构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));     //存储内存分配失败
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}

DestroyQueue (LinkQueue&Q){
//销毁队列Q
	while(Q.front){
		Q.rear=Q.front->next;
		free(Q.front);
		Q.front=Q.rear;
	}
	return OK;
}

EnQueue(LinkQueue&Q,QElemType e){
//插入元素e为Q的新的队尾元素
	QueuePtr p;
	p=(QueuePtr)malloc(sizeof(QNode));				//存储内存分配失败	
	if(!p) exit(OVERFLOW);
	p->data=e; p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}

QueueEmpty(LinkQueue &Q){
//判断队列是否为空
	return Q.front==Q.rear?OK:ERROR;
}

DeQueue(LinkQueue &Q,QElemType &e){
//若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK
//否则返回ERROR
if(Q.front==Q.rear) return ERROR;
QueuePtr p;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;
}

LevelOrderTraverse(BiTree &T, int Visit(TElemType e)){ 
//层序遍历二叉树 
if(T!=NULL){
	LinkQueue Q;
	InitQueue(Q);									//建一个空队（初始化队列） 
	
	QElemType p;
	EnQueue(Q,T);									//将一个结点插入队尾的函数
   while(!QueueEmpty(Q)) { 
	 DeQueue(Q, p);									//队首结点出队(送入p)
	 Visit(p->data); 
	if(p->lchild) EnQueue(Q,T->lchild);				//p的左孩子入队
    if(p->rchild) EnQueue(Q,T->rchild);				//p的右孩子入队
   } 
}
    return OK;
}//LevelOrderTraverse 

IsOrNotInTree(BiTree &T,BiTree &c){
//判断两个树是否相交
	if(T!=NULL&&c!=NULL){
		if(!EQ(T,c->data)){
			EQ(T->lchild,c->data);
			EQ(T->rchild,c->data);
		}else return 1;	
	}else return 0;
}

BiTree EQQ(BiTree &T,int e){
//返回指向结点的指针
	if(T!=NULL){
		if(!EQ(T,e)){
		    EQQ(T->lchild,e);
			  if(!EQ(T->lchild,e)) 
			   EQQ(T->rchild,e);
		}
		return (T);
	}
}

InsertChild(BiTree &T,BiTree &p,int LR,BiTree &c){
//插入c为T的子树..
	BiTree pchild;
	if(T!=NULL&&c!=NULL&&c->rchild==NULL&&!IsOrNotInTree(T,c)){
		if(LR){
			pchild=p->rchild;
			p->rchild=c;
			c->rchild=pchild;
		}
		else{
			pchild=p->lchild;
			p->lchild=c;
			c->rchild=pchild;
		}
	}
	return 0;
}//InsertChild

DeleteChild(BiTree &T,BiTree &p, int LR){
//删除T的子树..
	if(LR){
			ClearBiTree(p->rchild);
			p->rchild=NULL;
		}
	else if(LR==0){
			ClearBiTree(p->lchild);
			p->lchild=NULL;}
	else
		return ERROR;
}//DeleteChild


main()
{
	printf("\n");
	printf("********************二叉树*******************");
	printf("\n");
	printf("Build the tree:\n");
	printf("The num(99) is NULL:\n");
	
	BiTree T=NULL;
    CreatBiTree(T,1);
	printf("T tree has been built:\n");

	printf("***************************\n");
	printf("The traverse of the tree:\n");
   	printf("***************************\n");
	printf("PreOrderTraverse The BiTree:\n");
    PreOrderTraverse(T,PrintfElement);

	printf("\n");
	printf("InOrderTraverse The BiTree:\n");
	InOrderTraverse(T,PrintfElement);

	
	printf("\n");
	printf("PostOrderTraverse The BiTree:\n");
	PostOrderTraverse(T,PrintfElement);

	printf("\n");
	printf("LevelOrderTraverse The BiTree:\n");
	LevelOrderTraverse(T,PrintfElement);

	printf("\n");
	printf("*************************\n");
	printf("The depth of the tree is:\n");
	printf("**************************\n");
	int BiTreedepth;
	BiTreedepth=BiTreeDepth(T);
	printf("%d\n",BiTreedepth);

	printf("\n");
	printf("***************************\n");
	printf("the data of the tree root:\n");	
	printf("***************************\n");
	BiTree root=Root(T);
	printf("%d\n",root->data);

	printf("\n");
	printf("enter the data of the node:\n");
	int e,f;
	scanf("%d",&e);
	f=Value(T,e);
	printf("***************************\n");
	printf("the data of the node is:\n");
	printf("***************************\n");
	printf("%d\n",f);

	int m,n,g;
	printf("enter the data of the node:\n");
	scanf("%d",&m);
	printf("enter the data you want to change:\n");
    scanf("%d",&n);
	g=Assign(T,m,n);
	printf("***************************\n");
	printf("change the data of the node:\n");
	printf("***************************\n");
	printf("%d",g);

	printf("\n");
    printf("build another tree:\n");
    BiTree c;
	CreatBiTree(c,1);
	printf("T tree has been built:\n");

/*	int t;
	printf("Enter the t:\n");
	scanf("%d",&t);
	BiTree p;
	p=EQQ(T,t);*/

    InsertChild(T,T->lchild,1,c);
	printf("***************************\n");
	printf("insert the child:\n");
	printf("the T tree changed:\n");
	printf("***************************\n");
    PreOrderTraverse(T,PrintfElement);

	printf("\n");
	DeleteChild(T,T->lchild,1);
	printf("***************************\n");
	printf("delete the child:\n");
	printf("the T tree changed:\n");
	printf("***************************\n");
	PreOrderTraverse(T,PrintfElement);
    return 0;
}