二叉树基本运算

【核心代码】

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
	ElemType data;
	struct node* lchild;
	struct node* rchild;
}BTNode;


void CreateBTree(BTNode*& b,char *str)     //创建二叉树 
{
	BTNode* St[MaxSize],*p;
	int k,top = -1,j = 0;
	char ch = str[j];
	while(str[j] != '\0')
	{
		switch(ch)
		{
			case '(':top  ;k = 1;St[top] = p;break;
			case ')':top--;break;
			case ',':k = 2;break;
			default :p = (BTNode*)malloc(sizeof(BTNode));
			         p->data = ch;
			         p->lchild = NULL;p->rchild = NULL;
			         if(b == NULL)
			             b = p;
			      	 else
			      	 {
			      	 	switch(k)
			      	 	{
			      	 		case 1:St[top]->lchild = p;break;
			      	 		case 2:St[top]->rchild = p;break;
						}
					}	          
		}
		j  ;ch = str[j];
	}
}


void DestroyBTree(BTNode*& b)	//销毁二叉树 
{
	if(b != NULL)
	{
		DestroyBTree(b->lchild);
		DestroyBTree(b->rchild);
		free(b);
	}
}


BTNode* FindNode(BTNode* b,ElemType x)    //查找值为x的结点 
{
	BTNode* p;
	if(b == NULL)
		return NULL;
	else if(b->data == x)
		return b;
	else
	{
		p = FindNode(b->lchild,x);
		if(p != NULL)
			return p;
		else
			return FindNode(b->rchild,x);
	}
}


BTNode* LchildNode(BTNode *p)          //返回p节点的左孩子节点指针 
{
	return p->lchild;
}


BTNode* RchildNode(BTNode* p)        //返回p节点的右孩子结点指针 
{
	return p->rchild;
}


int BTHeight(BTNode* b)              //求二叉树b的高度 
{
	int lchildh,rchildh;
	if(b == NULL) 
		return(0);
	else
	{
		lchildh = BTHeight(b->lchild);
		rchildh = BTHeight(b->rchild);
		return(lchildh > rchildh)?(lchildh 1):(rchildh 1);
	}
}


void DispBTree(BTNode* b)        //以括号表示法输出二叉树 
{
	if(b != NULL)
	{
		printf("%c",b->data);
		if(b->lchild != NULL || b->rchild != NULL)
		{
			printf("(");
			DispBTree(b->lchild);
			if(b->rchild != NULL)printf(",");
			DispBTree(b->rchild);
			printf(")");
		}
	}
}


int main()
{
	BTNode* b,*p,*lp,*rp;
	printf("二叉树基本运算：");
	printf("	创建二叉树\n:");
	CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
	printf("	(2)输出二叉树:");DispBTree(b);printf("\n");
	printf("	(3)H节点：");
	p = FindNode(b,'H');
	if(p != NULL)
	{
		lp = LchildNode(p);
		if(lp != NULL) printf("左孩子为%c",lp->data);
		else printf("无左孩子");
		rp = RchildNode(p);
		if(lp != NULL) printf("右孩子为%c",rp->data);
		else printf("无右孩子");
	 } 
	 printf("\n");
	 printf("	(4)二叉树b的高度：%d\n",BTHeight(b));
	 printf("	(5)释放二叉树b\n");
	 DestroyBTree(b);
	 return 1; 
 }