欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(二叉树)4. 二叉树的各类计算问题(总结点个数、[叶子|度数为1|度数为2]结点个数以及二叉树深度计算)

程序员文章站 2022-05-16 18:35:23
...

一、前言

本程序的存储结构用的是二叉排序树,相关文章可看:
(二叉树)1. 二叉排序树的创建、[先序、中序、后序](递归和非递归六种操作)遍历讲解及代码

二、内容

说明:
本文所有计算方法均采用递归计算方法。

2.1 计算二叉树深度

2.1.1 代码

//计算二叉树的深度
int depth(BiTree* root) {
	if (!root)
		return 0;
	else {
		int left_depth = depth(root->left);
		int right_depth = depth(root->right);
		return left_depth > right_depth ? (left_depth + 1) : (right_depth + 1);
	}
}

2.1.2 简单说明

令深度为depth

depth = left_depth + right_depth + 1
这个加一的意思是 算完左右两边的深度后得加上当前这一层

2.2 计算二叉树叶子、度数为1、度数为2、总节点个数

2.2.1 代码

//计算总结点个数
int nodeNums(BiTree* root) {
	if (!root)
		return 0;
	else
		return nodeNums(root->left) + nodeNums(root->right) + 1;
}
//计算度数为2的结点总数
int twoChildNodes(BiTree* root) {
	if (!root)
		return 0;
	if (root->left && root->right)
		return twoChildNodes(root->left) + twoChildNodes(root->right) + 1;
	else
		return twoChildNodes(root->left) + twoChildNodes(root->right);
}
//计算度数为1的结点总数
int oneChildNodes(BiTree* root) {
	if (!root)
		return 0;
	bool only_left = root->left && !root->right;
	bool only_right = root->right && !root->left;
	if (only_left)
		return 1 + oneChildNodes(root->left);
	else if (only_right)
		return 1 + oneChildNodes(root->right);
	else
		return oneChildNodes(root->left) + oneChildNodes(root->right);
}
//计算叶子结点个数
int leaves(BiTree* root) {
	if (!root)
		return 0;
	if (!root->left && !root->right)
		return 1;
	return leaves(root->left) + leaves(root->right);
}

三、简单小结

因为这类计算问题比较简单,主要是要对递归有很熟的了解。
至于程序如何进行递归搜索的,自己画一颗简单的二叉树然后跟着程序走一遍就懂了
其实每个人对一个算法的理解都会有细小的不同,关键是要自己实践一遍才能形成自己的理解

下面是测试代码:

所用到的函数:

//测试工具
void swap(int& a, int& b);
void Perm(vector<int> vec, int b, int e);
BiTree* createBiNodeTest(int value);
int factorial(int n);
void testCal();

实现:

//测试工具函数
void swap(int& c1, int& c2)
{
	char temp;
	temp = c1;
	c1 = c2;
	c2 = temp;
}
BiTree* createBiNodeTest(int value) {
	BiTree* node = new BiTree;
	node->left = node->right = node->parent = NULL;
	node->key = value;
	return node;
}
void Perm(vector<int> p, int b, int e)
{
	static int num = 1;
	if (b == e) {
		BiTree* testRoot = NULL;
		for (int i = 0; i <= e; i++) {
			BiTree* temp = createBiNodeTest(p[i]);
			Insert(testRoot, temp);
		}
		cout << "--- 测试组" << num++ << "---" << endl;
		cout << "插入顺序:";
		for (int i = 0; i <= e; i++)
			cout << p[i] << " ";
		cout << endl << endl;

		int two = twoChildNodes(testRoot);
		int one = oneChildNodes(testRoot);
		int leaf = leaves(testRoot);
		int all = nodeNums(testRoot);
		cout << "度数为0:" << leaf << endl;
		cout << "度数为1:" << one << endl;
		cout << "度数为2:" << two << endl;
		cout << "总结点数:" << all << endl;
		if ((all == one + two + leaf) && leaf == two + 1)
			cout << "测试通过!" << endl;
		else {
			cout << "程序逻辑出现错误" << endl;
			_getch();
			exit(-1);
		}

		cout << "--- 测试组 ---" << endl << endl;
		//Sleep(100);
	}
	else
	{
		for (int i = b; i <= e; i++)
		{
			swap(p[b], p[i]);
			Perm(p, b + 1, e);
			swap(p[b], p[i]);
		}
	}
}
int factorial(int n) {
	if (n == 1)
		return 1;
	return n * factorial(n - 1);
}
void testCal() {
	//测试删除:
	int n;
	cout << "接下来生成由[0, n - 1)中整数构成的测试用例,将这n个数的全排列中每一种排列数都作为生成二叉排序树的新方式,总测试数应为n!。" << endl << endl;
	cout << "【注意】本测试程序没有测试计算二叉树的深度。" << endl;
	cout << "输入n:";
	cin >> n;
	cout << "--------------------------------------------------------------" << endl;
	cout << "\t\t\t" << "下面测试删除结点正确性" << endl;
	vector<int> p;
	for (int i = 0; i < n; i++)
		p.push_back(i);
	Perm(p, 0, n - 1);
	cout << "共有 " << n << "! = " << factorial(n) << " 组测试数据进行测试,总测试通过组数为 " <<  n << "! = " << factorial(n) << " 组。" << endl;
	cout << "--- 测试通过!---" << endl;
	cout << "--------------------------------------------------------------" << endl;
}

完整代码链接:
二叉树计算问题完整代码