统计叶子结点 21一、题目描述二、解题思路三、完整代码

一、题目描述

Description

给出一棵二叉树的前序遍历和中序遍历，统计对应的二叉树共有多少个叶子结点。本题要求使用二叉链表实现，否则即使通过也将酌情扣分。

Input

输入有两行仅由大写字母组成的字符串，分别表示二叉树的前序遍历和中序遍历。

Output

输出一行一个数，表示这棵树叶子结点的数量。

example：

input：

ABCD
ABCD

output：

1

二、解题思路

1、建立树

已知先序与中序可以建立唯一一棵二叉树。

整体实现思路是通过递归划分，

具体思路：

（1）先序可以确定根节点

（2）中序中找到根节点，便可划分左右子树（左边是左子树，右边是右子树）

（3）将左右子树看做是一棵新的树，再次递归调用

（4）若输入的子串 起始下标>终止下标， 则子串为空，返回NUL

函数实现：

//创建树
//pre为先序 prea先序的起始下标 preb先序的结束下标  mid中序  mida中序起始  midb中序结束
TreeNode* BuildTree(string pre, string mid, int prea, int preb, int mida, int midb)
{
	if (prea > preb)//该子串为空
	{
		return NULL;
	}
	else
	{
		TreeNode* root = new TreeNode;//设置根节点
		root->data = pre[prea];//先序排列第一个是根节点
		int tag = mida;//找到中序排列中根节点的位置
		while (mid[tag] != root->data)
		{
			tag++;
		}
		int llength;//计算左子串的长度
		llength = tag - mida;
		
		root->lchild = BuildTree(pre, mid, prea + 1, prea + llength, mida, tag - 1);
		root->rchild = BuildTree(pre, mid, prea + llength + 1, preb, tag + 1, midb);
		
		return root;
	}
}

（为了看起来更加直观，与最后贴出的完整代码相比我删去了debug的输出语句）

几点解释：

（1）函数的参数

pre为先序 prea先序的起始下标 preb先序的结束下标  mid中序  mida中序起始  midb中序结束

（2）递归调用时的参数

左子串：

前序 始=旧prea+1（第一个被划为根节点）   末=旧prea+llength（左子串长）

（“末”可以理解为“始+左子串长-1”）

中序 始=旧mida  末=tag（根）-1

右子串：

前序 始=旧prea+llength（左子串长）+1  末=旧preb

中序 始=tag（根）+1  末=旧midb

如果还不太理解动手画一画，很容易就明白了。

2、计算叶子结点数量

思路：

先序遍历的递归实现，其中加入对叶子结点的判断。

函数实现：

int CountLeaf(TreeNode* root)//计算叶子结点数量  尾递归节省空间
{
	if (root == NULL)
		return 0;
	else if (root->lchild == NULL && root->rchild == NULL)
	{
		cout << root->data << "  ";
		return 1;
	}
	else
	{
		cout << root->data << "  ";
		return CountLeaf(root->lchild) + CountLeaf(root->rchild);
	}
}

思路很简单，但有一个比较需要注意的点是这个函数使用了尾递归，

而一开始我并不是这么做的，结果导致结果超时。 

int CountLeaf(TreeNode* root,int& count)
{
	if (root == NULL)
		return 0;
	else
	{
		if (root->lchild != NULL)
			CountLeaf(root->lchild, count);
		if(root->rchild!=NULL)
			CountLeaf(root->rchild, count);
		else if (root->lchild == NULL && root->rchild == NULL)
			count++;
	}
}

三、完整代码

#include<iostream>
#include<string>

using namespace std;

//结点定义
struct TreeNode
{
	char data;
	TreeNode* lchild,* rchild;
};

//创建树
TreeNode* BuildTree(string pre, string mid, int prea, int preb, int mida, int midb)
{
	if (prea > preb)//该子串为空
	{
		cout << "该子串为空" << endl;
		return NULL;
	}
	else
	{
		TreeNode* root = new TreeNode;//设置根节点
		root->data = pre[prea];//先序排列第一个是根节点
		int tag = mida;//找到中序排列中根节点的位置
		while (mid[tag] != root->data)
		{
			tag++;
		}
		int llength;//计算左子串的长度
		llength = tag - mida;
		printf("现在在%c结点，左子串长度为%dn", root->data, llength);//为了debug方便
		printf("创建%c的左子树：n", root->data);
		printf("prea=%d,preb=%d,mida=%d,midb=%dn", prea + 1, prea + llength, mida, tag - 1);
		
		root->lchild = BuildTree(pre, mid, prea + 1, prea + llength, mida, tag - 1);
		
		printf("创建%c的右子树：n", root->data);
		printf("prea=%d,preb=%d,mida=%d,midb=%dn", prea + llength + 1, preb, tag + 1, midb);
		
		root->rchild = BuildTree(pre, mid, prea + llength + 1, preb, tag + 1, midb);
		
		return root;
	}
}

int CountLeaf(TreeNode* root)//计算叶子结点 尾递归节省空间
{
	if (root == NULL)
		return 0;
	else if (root->lchild == NULL && root->rchild == NULL)
	{
		cout << root->data << "  ";
		return 1;
	}
	else
	{
		cout << root->data << "  ";
		return CountLeaf(root->lchild) + CountLeaf(root->rchild);
	}
}

int main()
{
	string pre,mid;
	cin >> pre;//先序
	cin >> mid;//中序
	printf("pre.length()=%d,mid.length()=%d", pre.length(), mid.length());
	TreeNode* root= BuildTree(pre, mid, 0, pre.length()-1, 0, mid.length()-1);
	cout << CountLeaf(root);
	return 0;
}

其实main函数还有一个需要注意的点，就是在调用BuildTree函数的时候，

BuildTree(pre, mid, 0, pre.length()-1, 0, mid.length()-1);

一定要记得-1，虽然是很小的一个点，但当时我找了很久才找到问题orz

完整代码里我cin，cout和printf混用，非常不建议！！！！大家不要这样！！！

（但我懒得改了。。。主要是scanf用的非常不好）

最后

以上就是大胆故事为你收集整理的统计叶子结点 21一、题目描述二、解题思路三、完整代码的全部内容，希望文章能够帮你解决统计叶子结点 21一、题目描述二、解题思路三、完整代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。