计算二叉树的高度（C++实现）

问题：求二叉树的高度

思路：遍历二叉树，统计当前左子树和右子树的高度，取最大高度，直到节点遍历完毕。本文章中使用的是层序遍历的方式，来统计左右子树的最大高度，最后综合输出结果。

具体代码实现如下：

读者可以改变二叉树节点之间的关系，来改变二叉树的高度，从而验证不同的结果。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdlib.h>
#include <memory>
#include <queue>
using namespace std;

// 二叉树的节点
struct BinaryTree
{
	char data;
	std::shared_ptr<BinaryTree> left;
	std::shared_ptr<BinaryTree>  right;
	BinaryTree(char val) :data(val)
	{
		this->left = NULL;
		this->right = NULL;
	}
};

// 二叉树的层序遍历：队列实现
void LayerOrderTraversal(shared_ptr<BinaryTree> bt)
{
	// 如果是空树，直接返回
	if (!bt) return;

	// 计算左右子树的最大高度
	int hl = 0;
	int hr = 0;

	// 声明一个队列，存储二叉树的节点
	queue<shared_ptr<BinaryTree>> q;

	// 声明一个二叉树节点的指针，用于访问节点
	shared_ptr<BinaryTree> look;			

	// 头结点先入队
	q.push(bt);	

	while (!q.empty())
	{
		// 访问队列的头部，并将其出队
		look = q.front();
		//cout << look->data << " ";
		q.pop();

		// 如果出队的节点存在左孩子，将左孩子入队
		if (look->left)
		{
			q.push(look->left);
			hl++;
		}

		// 如果出队的节点存在右孩子，将右孩子入队
		if (look->right)
		{
			q.push(look->right);
			hr++;
		}

		// 更新左右子树的高度，都取目前的最大的值，然后继续下一轮的计算
		hl > hr ? (hr = hl) : (hl = hr);
	}

	// 输出树的高度：此时hr和hl的值都是当前树的高度，输出那一个变量都可以
	cout << hl << endl;
}

int main()
{
	// 创建一系列树节点：使用智能指针
	shared_ptr<BinaryTree> a = make_shared<BinaryTree>('a');
	shared_ptr<BinaryTree> b = make_shared<BinaryTree>('b');
	shared_ptr<BinaryTree> c = make_shared<BinaryTree>('c');
	shared_ptr<BinaryTree> d = make_shared<BinaryTree>('d');
	shared_ptr<BinaryTree> e = make_shared<BinaryTree>('e');
	shared_ptr<BinaryTree> f = make_shared<BinaryTree>('f');
	shared_ptr<BinaryTree> g = make_shared<BinaryTree>('g');

	// 创建二叉树节点之间的关系
	a->left = f;
	a->right = d;
	f->left = e;
	f->right = c;
	d->left = b;
	b->right = g;

	// 层序遍历
	LayerOrderTraversal(a);
	
	system("pause");
	return 0;
}
           

结果如下：

读者可以改变二叉树节点之间的关系（比如：新增多个节点），来改变二叉树的高度，从而验证不同的结果。

谢谢阅读