計算二叉樹的高度（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;
}
           

結果如下：

讀者可以改變二叉樹節點之間的關系（比如：新增多個節點），來改變二叉樹的高度，進而驗證不同的結果。

謝謝閱讀