ODOA(2) 求二叉树中两个节点的最大距离(C语言实现)

/* 
  Name: main.c 
  Author: suzhou 
  Date:   2014.02.18
  Num.    2
 */  


#include "btree.h"

int main()
{
	BTree mytree = NULL;
	int choice;
	
	while (1) {
		printf("\n请选择您想要进行的操作:\n");
		printf("  [ 1 ] 先序次序建立二叉树\n");
		printf("  [ 2 ] 先序打印二叉树节点\n");
		printf("  [ 3 ] 求树的深度\n");
		printf("  [ 4 ] 求树中相距最远的两个节点的距离\n");
		printf("  [ 0 ] 退出\n");

		scanf("%d", &choice);

		switch(choice)
		{
		case 0:
			printf("%s\n", "谢谢使用");
			exit(0);
		case 1:
			printf("%s",
				   "请以先序遍历次序输入各个节点的数值:\n");
			createBTree(&mytree);
			continue;
		case 2:
			preOrderVisit(mytree);
			continue;
		case 3:
			printf("树的深度为: %d\n",
				   depth(mytree));
			continue;
		case 4:
			printf("最大距离为： %d\n",
				   maxDistance(mytree)
				);
			continue;
		default:
			printf("%s\n",
				   "请输入正确的选择");
			continue;
		}
	}
	
	printf("Congratulations! It works!\n");
	return 0;
}

/* 
  Name: btree.h
  Author: suzhou 
  Date:   2014.02.18
  Num.    2
 */  




#ifndef BTREE
#define BTREE

#include "stdio.h"
#include "stdlib.h"

typedef struct BTNode
{
	int val;
	struct BTNode* pLeft;
	struct BTNode* pRight;
}BTNode, *BTree;


/*
  建立二叉树
 */
void createBTree (
	BTree* tree
	);

/*
  先序遍历二叉树
 */
void preOrderVisit (
	BTree tree
	);

/*
  按树状打印节点
 */
void printTree (
	BTree tree,
	int depth
	);


/*
 * 求树的深度
 */
int depth(
	BTree tree
	);

/*
 * 求树的两个节点的最远距离
 */
int maxDistance(
	BTree tree
	);

#endif

/* 
  Name: btree.c 
  Author: suzhou 
  Date:   2014.02.18
  Num.    2
 */  



#include "btree.h"


/*
  建立二叉树
 */
void createBTree (
	BTree* tree
	)
{
	int val;
	
	scanf("%d", &val);

	if ( val == 0 )
	{
		*tree = NULL;
	}
	else
	{
		*tree = (BTNode*) malloc (sizeof(BTNode));
		(*tree)->val = val;
		createBTree(&((*tree)->pLeft));
		createBTree(&((*tree)->pRight));
	}
}


/*
  先序遍历二叉树
 */
void preOrderVisit (
	BTree tree
	)
{
	if ( tree != NULL )
	{
		printf("%d\n", tree->val);
		preOrderVisit(tree->pLeft);
		preOrderVisit(tree->pRight);
	}
}


/*
  按树状打印节点
 */
void printTree (
	BTree tree,
	int depth
	)
{
	int i;
	
	if ( tree == NULL )
		return;
	for ( i=depth; i>=0; i-- )
		printf("%c", ‘ ‘);
	printf("%d\n" , tree->val);

	printTree(tree->pLeft, depth+1);
	printTree(tree->pRight, depth+1);
	
}


/*
 * 求树的深度
 */
int depth(
	BTree tree
	)
{
	if (tree == NULL)
		return 0;
	else
		return 1 + 
			(depth(tree->pLeft) >= depth(tree->pRight)
			? depth(tree->pLeft) : depth(tree->pRight));
}


/*
 * 求树的两个节点的最远距离
 */
int maxDistance(
	BTree tree
	)
{
	if (tree->pLeft == NULL
		|| tree->pRight == NULL)
		return depth(tree);
	else
		return depth(tree->pLeft) + depth(tree->pRight);
}