数据结构C++边学边做--二叉树的应用--求二叉树的最小深度

一、求二叉树的最小深度二、求二叉树最小深度实现

1.SmallestDepth类文件2.SmallestDepth类方法 三、求二叉树最小深度代码测试

1.主函数2.输出结果 四、源代码获取（免积分）

  在前文二叉链表的实现的基础上添加一个求二叉树的最小深度的方法：SmallestDepth。二叉树的最小深度指的是从根节点到最近的叶子结点的距离。
  当二叉树为空时，返回0；
  当二叉树的左子树为空时返回右子树的最小深度+1；
  当二叉树的右子树为空时返回左子树的深度+1；
  当二叉树的左右子树都不为空时返回左右子树最小深度较小的值+1；

template 
struct BiNode{
	ElemType data;
	BiNode *lchild,*rchild;
}; 

template 
class BiTree{
	public:
		BiTree() {root=Create(root);}//构造函数，建立一颗二叉树
		~BiTree() {Release(root);}//析构函数，释放各个节点
		int SmallestDepth(){return SmallestDepth(root);} ;
	private:
		int BiTreeCountNode;
		BiNode* root;
		BiNode* Create(BiNode* bt) ;
		void Release(BiNode* bt);
		int SmallestDepth(BiNode * bt);		
}; 

template 
int BiTree::SmallestDepth(BiNode * bt)
{
	if(bt==NULL)
		return 0;	
	if(bt->lchild==NULL)
		return SmallestDepth(bt->rchild)+1;
	if(bt->rchild==NULL)
		return SmallestDepth(bt->lchild)+1;	
	int m =	SmallestDepth(bt->lchild)+1;
	int n =	SmallestDepth(bt->rchild)+1;
	return m 
三、求二叉树最小深度代码测试 
1.主函数 
#include 
#include "BiTree.h"
#include "BiTree.cpp"

using namespace std;

int  main() {
	BiTree T;
	cout<<"二叉树最小深度："< 
2.输出结果 
  按照下面这个扩展二叉树的顺序，依次输入：A B # # C D # # #。
 
 
请输入创建一颗二叉树的结点数：
A
请输入创建一颗二叉树的结点数：
B
请输入创建一颗二叉树的结点数：
#
请输入创建一颗二叉树的结点数：
#
请输入创建一颗二叉树的结点数：
C
请输入创建一颗二叉树的结点数：
D
请输入创建一颗二叉树的结点数：
#
请输入创建一颗二叉树的结点数：
#
请输入创建一颗二叉树的结点数：
#
二叉树最小深度：2
 
四、源代码获取（免积分） 
源代码地址