二叉树2.cpp

自己写的数据结构代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define OK 1
#define ERROR 0
#define MIN 1e-6

typedef int Status;
typedef int ElemType;

#define maxsize 100000
#define STACK_INIT_SIZE 100000
#define STACKINCREMENT 2

typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

struct SqStack
{
	BiTree *base;
	BiTree *top;
	int stacksize;
};

Status InitStack(SqStack &S)
{
	S.base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree));
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}

Status Push(SqStack &S,BiTree e)
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(BiTree *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree));
		S.top=S.base+S.stacksize;
		S.stacksize=S.stacksize+STACKINCREMENT;
	}
	*S.top++=e;
	
	return OK;
}

Status Pop(SqStack &S,BiTree &e)
{
	if(S.top==S.base) return ERROR;
	
	e=* --S.top;
	return OK;
}


Status StackEmpty(SqStack S)
{
	if(S.top==S.base) return OK;
	return ERROR;
}



Status InsertBiTree(BiTree &T,int e)
{
	if(!T) 
	{
		T=(BiTNode *)malloc(sizeof(BiTNode));
		T->data=e;
		T->lchild=NULL;
		T->rchild=NULL;
		return OK;
	}
	if(e<=T->data)
	{
		InsertBiTree(T->lchild,e);
		return OK;
	}
	else
	{
		InsertBiTree(T->rchild,e);
		return OK;
	}
	return OK;
}

Status PrintElement(ElemType e)
{
	printf("%d ",e);
	return OK;
}

Status PreOrderTraverse(BiTree T,Status(*Visit)(ElemType))
{
	if(T)
	{
		if(Visit(T->data))
			if(PreOrderTraverse(T->lchild,Visit)) 
				if(PreOrderTraverse(T->rchild,Visit))   return OK;
				return ERROR;
	}
	else return OK;
}

Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType))
{
	if(T)
	{
		if(InOrderTraverse(T->lchild,Visit))
			if(Visit(T->data)) 
				if(InOrderTraverse(T->rchild,Visit))   return OK;
				return ERROR;
	}
	else return OK;
}

Status PostOrderTraverse(BiTree T,Status(*Visit)(ElemType))
{
	if(T)
	{
		if(PostOrderTraverse(T->lchild,Visit))
			if(PostOrderTraverse(T->rchild,Visit)) 
				if(Visit(T->data))   return OK;
				return ERROR;
	}
	else return OK;
}

Status SearchBiTree(BiTree &T,int e)
{
	if(!T) return ERROR;
	else if(e==T->data) return OK;
	else if(e<T->data)
	{
		return SearchBiTree(T->lchild,e);
	}
	else
	{
		return SearchBiTree(T->rchild,e);
	}
}


Status InOrder(BiTree T,Status(*Visit)(ElemType))
{
	SqStack s;
	BiTree p;
	InitStack(s);
	p=T;
	while(p || !StackEmpty(s))
	{
		if(p)  
		{
			Push(s,p);
			p=p->lchild;
		}
		else
		{
			Pop(s,p);
			if(!Visit(p->data))  return ERROR;
			p=p->rchild;
		}
	}
	return OK;
}
	
Status Travel(BiTree T,Status(*Visit)(ElemType))                         /*层次遍历二叉树*/
{
    BiTree qu[maxsize];
    int front,rear;
    front=rear=0;
    if(T!=NULL)
		if(!Visit(T->data))  return ERROR;
    rear++;
    qu[rear]=T;
    while(rear!=front)
    { 
		front=(front+1)%maxsize;
        T=qu[front];
        if(T->lchild!=NULL)
        { 
			if(!Visit(T->lchild->data))  return ERROR;
            rear=(rear+1)%maxsize;
            qu[rear]=T->lchild;
        }
        if(T->rchild!=NULL)
        {  
			if(!Visit(T->rchild->data))  return ERROR;
            rear=(rear+1)%maxsize;
            qu[rear]=T->rchild;
        }
    }
	return OK;
}  

Status Change(BiTree &T)
{
	BiTree t;
	if(!T)  return ERROR;
	
	else if(!T->lchild && T->rchild)
	{
		Change(T->rchild);
		t=T->lchild;
		T->lchild=T->rchild;
		T->rchild=t;
		
		return OK;
	}
	else if(T->lchild && !T->rchild)
	{
		Change(T->lchild);
		t=T->rchild;
		T->rchild=T->lchild;
		T->lchild=t;		
		return OK;
	}
	else if(T->lchild && T->rchild) 
	{
		Change(T->lchild);
		Change(T->rchild);
		t=T->lchild;
		T->lchild=T->rchild;
		T->rchild=t;
		return OK;
	}
	else return OK;
}

Status Deepth(BiTree T)                        
{
    if(!T)  return 0;
	return Deepth(T->lchild)>Deepth(T->rchild)?Deepth(T->lchild)+1:Deepth(T->rchild)+1;
}  

Status Leaf(BiTree T)
{
	if(!T)  return 0;
	if(!T->lchild && !T->rchild)  return 1;
	return Leaf(T->lchild)+Leaf(T->rchild);
}

int main()
{
	int a[100000];
	int n,i;
	int e;
	int count;
	int s;

	BiTree T;
	
	scanf("%d",&n);

	for(i=0;i<=n-1;i++)
	{
		scanf("%d",&a[i]);
	}
	T=NULL;
	for(i=0;i<=n-1;i++)
	{
		InsertBiTree(T,a[i]);
	}
	
	PreOrderTraverse(T,PrintElement);
	printf("\n");
	InOrderTraverse(T,PrintElement);
	printf("\n");
	PostOrderTraverse(T,PrintElement);
	printf("\n");
	
	for(i=1;i<=2;i++)
	{
		scanf("%d",&e);
		printf("%d\n",SearchBiTree(T,e));
	}

	scanf("%d",&e);
	InsertBiTree(T,e);
	
	PreOrderTraverse(T,PrintElement);
	printf("\n");
	InOrderTraverse(T,PrintElement);
	printf("\n");
	PostOrderTraverse(T,PrintElement);
	printf("\n");

	InOrder(T,PrintElement);
	printf("\n");

	Travel(T,PrintElement);
	printf("\n");

	Change(T);
	PreOrderTraverse(T,PrintElement);
	printf("\n");
	InOrderTraverse(T,PrintElement);
	printf("\n");
	PostOrderTraverse(T,PrintElement);
	printf("\n");
	
	Change(T);
	PreOrderTraverse(T,PrintElement);
	printf("\n");
	InOrderTraverse(T,PrintElement);
	printf("\n");
	PostOrderTraverse(T,PrintElement);
	printf("\n");

	count=Deepth(T);
	printf("%d\n",count);

	s=Leaf(T);
	printf("%d\n",s);

	return 0;
}