5.txt

本例题将介绍一种建立二叉树的算法。同时介绍对“遍历算法”灵活应用：将二叉树中每个结点的左右子树进行交换。介绍求二叉树深度的算法。 二叉树的建立是一个递归方法

#define max 30
#define NULL 0
#include<stdlib.h>
#include<stdio.h>
int countnode;
int countleaf;
typedef int ElemType;
typedef struct btnode
{
	ElemType data;
	struct btnode *lchild,*rchild;
}bttree;
// 爱悠游  www.aiyoy.com  bbs.aiyoy.com
//有问题？ 来 爱悠游计算机技术讨论区：http://www.aiyoy.com/bbs/forumdisplay.php?fid=39
/*构造二叉树*/
bttree *cre_tree()
{
	bttree *p;
	ElemType x;
	printf("输入数据：\n");
	scanf("%d",&x);
	if(x==0)
		p=NULL;
	else
	{
		p=(bttree *)malloc(sizeof(bttree));
		p->data=x;
	    p->lchild=cre_tree();
	    p->rchild=cre_tree();
	}
	return p;
}
/*先序遍历二叉树*/
void preorder(bttree *t)
{			   //程序填空①
	if(t!=NULL)
	{
		printf("%d\n",t->data);
		preorder(t->lchild);
		preorder(t->rchild);
	}
}
/*交换二叉树左右子树*/
bttree *swap(bttree *p)
{
	bttree *stack[max];
	int k;
	k=0;
	stack[k]=NULL;
	if(p!=NULL)
	{
		stack[++k]=p->lchild;
		p->lchild=p->rchild;
		p->rchild=stack[k];
		p->lchild=swap(p->lchild);
		p->rchild=swap(p->rchild);
	}
	return p;
}
/*求二叉树的结点数和叶结节点数*/
void inordercount(bttree *p)
{                  //程序填空②
	if(p!=NULL)
	{
		if(p->lchild==NULL&&p->rchild==NULL)
			countleaf++;
		countnode++;
		inordercount(p->lchild);
		inordercount(p->rchild);
	}
}
/*求二叉树深度*/
int treedeep(bttree *p)
{              //程序填空3
	int   hl,hr;
	if(p)
	{

		hl=treedeep(p->lchild);
		hr=treedeep(p->rchild);
		if(hl>hr)
		    return hl+1;
		else
		    return hr+1;
	}
	else
		return   0;
}
/*主函数*/
void main()
{
	bttree *root;
	printf("\n\n");
	root=cre_tree();
	printf("二叉树已建立成功！\n");
	printf("\n\n");
	printf("先序遍历二叉树为:");
	preorder(root);
	printf("\n\n");
	root=swap(root);
	printf("交换左右子树后的先序遍历二叉树为:");
	preorder(root);
	printf("\n\n");
	inordercount(root);
	printf("结点数为：%d \n叶结点数为：%d\n",countnode,countleaf);
	printf("二叉树深度为：%d\n",treedeep(root));
	int f ;
	scanf("%d",&f);

}