【问题描述】

设计一个算法，判断一棵二叉排序树bt是否为平衡的。

【输入形式】

两行，第一行是数据个数，第二行是输入数据

【输出形式】

true或者false，如果输入数据构成的二叉树是平衡的，输出true, 否则，输出false
【样例输入】

9

5 2 3 4 1 8 6 7 9
【样例输出】

true
【样例说明】
【评分标准】

#include<iostream>
#include<queue>
using namespace std;
const int length = 10;

template<class T>
class BTree {
private:
	struct Bin {
		T elem;
		Bin* lchild, * rchild;
	};
	Bin* root;

public:
	BTree();
	void Insert(T e);
	void CrBree();
	bool exists(T e) 
	{
		Bin* p = root;
		while (p != NULL) {
			if (p->elem == e)return true;
			else if (p->elem < e)p = p->rchild;
			else {
				p = p -> lchild;
			}
		}
		return false;
	}
	bool equal_factor(Bin* q)
	{	
		//判断每个节点平衡因子是否为1||-1||0
		int i, j;
		//判断左子树深度
		i = treedepth(q->lchild);
		//判断右子树深度
		j = treedepth(q->rchild);
		if (i - j == 0 || i - j == -1 || i - j == 1)return true;
		return false;
	}
	int treedepth(Bin* p)
	{
		if (p == NULL)
			return 0;
		int left = treedepth(p->lchild);
		int right = treedepth(p->rchild);
		return (left > right) ? (left + 1) : (right + 1);
	}
};

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

template<class T>
void BTree<T>::Insert(T e)
{
	if (!exists(e)) {
		Bin* q = new Bin;
		q->elem = e;
		q->lchild = q->rchild = NULL;
		Bin* p = root;
		while (p!=NULL) {
			if (e > p->elem && p->rchild != NULL) {
				p = p->rchild;
			}
			else if (e > p->elem && p->rchild == NULL) {
				p->rchild = q;
				break;
			}
			else if (e < p->elem && p->lchild != NULL) {
				p = p->lchild;
			}
			else if (e < p->elem && p->lchild == NULL) {
				p->lchild = q;
				break;
			}
		}
		if (p == NULL) {
			root = new Bin;
			root->elem = e;
			root->rchild = root->lchild = NULL;
		}
	}
}


template<class T>
void BTree<T>::CrBree()
{
	int m,n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> m;
		Insert(m);
	}
	//层次遍历
	bool judge = true;
	queue<Bin *>que;
	que.push(root);
	while (!que.empty()) {
		auto x = que.front();
		if (!equal_factor(x)) {
			judge = false;
			break;
		}
		que.pop();
		if (x->lchild != NULL) {
			que.push(x->lchild);
		}
		if (x->rchild != NULL) {
			que.push(x->rchild);
		}
	}
	if (judge)cout << "true";
	else {
		cout << "false";
	}

}


int main() {
	BTree<int>T;
	T.CrBree();
}