tree.cpp

二叉树的实现

//树的功能实现，求树的深度
#include <stdlib.h>
#include <stdio.h>
#include "..\include\predefine.h"

typedef struct CSNode
{
	ElemType data;
	struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

Status CreateTree(CSTree &T,char *pch)
{//处理由树转换成的二叉树先序扩展序列
	static char *p=pch;
	if(*p=='.') T=NULL;
	else
	{
		if(!(T=(CSNode*)malloc(sizeof(CSNode)))) exit(OVERFLOW);
		T->data=*p;
		CreateTree(T->firstchild,++p);
		CreateTree(T->nextsibling,++p);
	}
	return OK;
}
Status PostOrderTraverse(CSTree &T,Status (*Visit)(CSTree))
{
	if(T)
	{
		if(PostOrderTraverse(T->firstchild,Visit))
			if(PostOrderTraverse(T->nextsibling,Visit))
				if(Visit(T)) return OK;
		return ERROR;
	}
	else return OK;
}
Status FreeElement(CSTree n)
{
	free(n);
	return OK;
}
Status DestroyTree(CSTree &T)
{
	PostOrderTraverse(T,FreeElement);
	return OK;
}
int TreeDepth(CSTree T) 
{
	int h1,h2;
	if(!T)  return 0;
	else 
    { 
		h1 = TreeDepth( T->firstchild );
		h2 = TreeDepth( T->nextsibling);
		if(h1+1>=h2) return h1+1;
		else return h2;
    }
}