数据结构C++边学边做--二叉树的遍历应用

一、二叉树遍历的应用二、Depth->求二叉树深度三、Count->求二叉树的结点个数四、CountLeaf->二叉树的叶子结点的个数五、PrintLeaf->输出二叉树的叶子结点六、测试代码

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

  二叉树的基本实现（二叉链表）见前文：二叉链表的实现。
  二叉树的一些常见的应用是以二叉树的遍历为基础的，例如求二叉树的深度（Depth）、求二叉树的结点个数（Count）、求二叉树的叶子结点的个数（CountLeaf）、输出二叉树的叶子结点（PrintLeaf）等等，此类应用一般用递归的方式实现。

  当二叉树为空时，深度为0；当二叉树不为空时，二叉树的深度为其根的左右子树的深度中较大的值再+1。算法描述如下：

template 
int BiTree::Depth(BiNode *bt)
{
	if(bt==NULL)
	{
		return 0;
	}
	else
	{
		int dep1=Depth(bt->lchild);
		int dep2=Depth(bt->rchild);
		return (dep1>dep2)?(dep1+1):(dep2+1);
	}
}

  求二叉树结点个数时，可以利用二叉树的遍历，在遍历的过程中对结点进行计数。算法描述如下：

template 
void BiTree::Count(BiNode *bt)
{
	if(bt!=NULL)
	{
		Count(bt->lchild);
		BiTreeCountNode++;
		Count(bt->rchild);
	}
}

  求二叉树的叶子结点个数与求二叉树的结点总数类似，只有结点为叶子时才计数。算法描述如下：

template 
void BiTree::CountLeaf(BiNode *bt)
{
	if(bt!=NULL)
	{
		if(bt->lchild==NULL&&bt->rchild==NULL)
		{
			BiTreeCountNode++;
		}
		CountLeaf(bt->lchild);
		CountLeaf(bt->rchild);	
	}
}

  算法描述如下：

template 
void BiTree::PrintLeaf(BiNode *bt)
{
	if(bt!=NULL)
	{
		if(bt->lchild==NULL&&bt->rchild==NULL)
		{
			std::cout<data<<" ";
		}
		PrintLeaf(bt->lchild);
		PrintLeaf(bt->rchild);	
	}
}

#include 
#include "BiTree.h"
#include "BiTree.cpp"

using namespace std;

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