btree.txt

这是我用VC编写的一些数据结构程序

/*  2005-03-04   -----------------------------------------------
    给定一棵二叉树，求出二叉树的深度。 测试如下的二叉数：
                           A
			  / \
			 B   D
			/ \
		       E   C
		        \ 
			 F
			/ \
		       G   H     该二叉树应该这样输入 ABE##C#FG##H##D##
---------------------------------------------------------------*/


#include <stdio.h>
#include <stdlib.h>
#include<conio.h>

#define MAX 20
#define NULL 0


typedef struct BiTNode   //二叉树的二叉链表存储表示
{
    char data;	
    struct BiTNode *lchild,*rchild;	
}BiTNode,*BiTree;

void CreateBiTree(BiTree *T)   //建立二叉树
{	
	char ch;	
	ch=getchar();
	
	if (ch=='#') (*T)=NULL;                    // #代表空指针	
	else 
	{
		
		(*T)=(BiTree) malloc(sizeof(BiTNode));//申请结点   		
		(*T)->data=ch;                        //生成根结点  		
		CreateBiTree(&(*T)->lchild) ;         //构造左子树  		
		CreateBiTree(&(*T)->rchild) ;         //构造右子树  		
	}
}

void PreOrder(BiTree T)    // 先序遍历二叉树递归算法
{
	if (T)
	{
		printf("%2c",T->data);    //访问根结点，此处简化为输出根结点的数据值
		PreOrder(T->lchild);      //先序遍历左子树
		PreOrder(T->rchild);      //先序遍历右子树
	}
}


int depth(BiTree T  )			//求二叉树的深度 
{  
	int dep1,dep2;	

	if (T==NULL)
		return 0;	
	else 
	{
		dep1=depth(T->lchild);	
		dep2=depth(T->rchild);	
		return dep1 > dep2? dep1+1 : dep2+1;	
	}
}

void main()
{	
	BiTree T=NULL;	
	printf("\n请输入数据来建立一棵二叉树：\n");
	printf("\n输入规则：\n");
	printf("    如果二叉树为空，则直接输入#回车。否则，按先序顺序输入各个结点的值，如果结点的左子树或右子树为空，则输入#。(如：ABE##C#FG##H##D##)\n");
	
	CreateBiTree(&T);  

	printf("\n该二叉树的先序遍历顺序为:\n");	
	PreOrder(T);   
    
	printf("\n该二叉树的深度为：%d", depth(T));

	_getch();
}