数据结构 - 平衡二叉树

平衡二叉树的定义

平衡二叉树（Balanced Binary Tree）是具有以下性质的二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

判断一棵二叉树是否平衡（C++）

#include <iostream>

#define NULL 0

using namespace std;

template<class T>
struct BTNode
{
	T data;
	BTNode<T> *lChild, *rChild;
	BTNode();
	BTNode(const T &val, BTNode<T> *childL = NULL, BTNode<T> *childR = NULL)
	{
		data = val;
		lChild = childL;
		rChild = childR;
	}

	BTNode<T>* CopyTree()
	{
		BTNode<T> *nl, *nr, *nn;
		if(&data == NULL)
		{
			return NULL;
		}

		nl = lChild->CopyTree();
		nr = rChild->CopyTree();
		nn = new BTNode<T>(data, nl, nr);

		return nn;
	}
};

template<class T>
BTNode<T>::BTNode()
{
	lChild = rChild = NULL;
}

template<class T>
class BinaryTree
{
public:
	BTNode<T> *root;
	BinaryTree();
	~BinaryTree();
	void DestroyTree();
	BTNode<T>* MakeTree(const T &element, BTNode<T> *l, BTNode<T> *r)
	{
		root = new BTNode<T> (element, l, r);
		if(root == NULL)
		{
			cout << "Failure for applying storage address, system will close the process." << endl;
			exit(1);
		}

		return root;
	}

private:
	void Destroy(BTNode<T> *&r);
};

template<class T>
BinaryTree<T>::BinaryTree()
{
	root = NULL;
}

template<class T>
BinaryTree<T>::~BinaryTree()
{
	DestroyTree();
}

template<class T>
void BinaryTree<T>::DestroyTree()
{
	Destroy(root);
}

template<class T>
void BinaryTree<T>::Destroy(BTNode<T> *&r)
{
	if(r != NULL)
	{
		Destroy(r->lChild);
		Destroy(r->rChild);
		delete r;
		r = NULL;
	}
}

template<class T>
int isBalanced(BTNode<T> *r)
{
	if(!r)
	{
		return 0;
	}

	int left = isBalanced(r->lChild);
	int right = isBalanced(r->rChild);
	if((left >= 0) && (right >= 0) && ((left - right) <= 1) && ((left - right) >= -1))
	{
		return (left < right) ? (right + 1) : (left + 1);
	}
	else
	{
		return -1;
	}
}

void main()
{
	BTNode<char> *b, *c, *d, *e, *f, *g;
	BinaryTree<char> a;

	b = a.MakeTree('F', NULL, NULL);
	c = a.MakeTree('E', NULL, NULL);
	d = a.MakeTree('D', b, NULL);
	e = a.MakeTree('C', NULL, NULL);
	f = a.MakeTree('B', d, c);
	g = a.MakeTree('A', f, e);

	if(isBalanced(a.root) >= 0)
	{
		cout << "This IS a balanced binary tree." << endl;
	}
	else
	{
		cout << "This is NOT a balanced binary tree." << endl;
	}
}

// Output:
/*
This is NOT a balanced binary tree.
*/