判斷二叉樹是不是平衡二叉樹、完全二叉樹、滿二叉樹||C++實作

目錄

1 判斷二叉樹是不是平衡二叉樹

2 判斷二叉樹是不是完全二叉樹

3 判斷二叉樹是不是滿二叉樹

在這之前，我們假設二叉樹節點的結構如下：

typedef struct binaryTreeNode
{
	int mData;
	binaryTreeNode * mLeft;
	binaryTreeNode * mRight;
};
           

1 判斷二叉樹是不是平衡二叉樹

首先來科普一下什麼是平衡二叉樹，學過資料結構的應該都知道，這畢竟不是什麼新鮮的問題。

首先大家對二叉查找樹（二叉排序樹）有所了解。 首先平衡二叉樹是一棵二叉查找樹，另外，以平衡二叉樹中所有節點為根的樹的左右子樹高度之差的絕對值不超過1。

是以在判斷二叉樹是不是平衡二叉樹之前，我們先應該去判斷這顆樹滿足不滿足平衡二叉樹的基本條件，即這顆樹是不是二叉查找樹，對于二叉查找樹，我們知道由于它滿足左小右大的規則，是以二叉查找樹的中序周遊序列是從小到大有序的。我們可以根據這個特點去判斷一個二叉樹是不是二叉查找樹

見下面代碼:

int predit = INF;//假設INF為已定義的常量，它小于樹中的任何值，用predit記錄目前通路節點的前驅的值
bool JustBST(binaryTreeNode* root)
{
	if (root == NULL)//空樹也是二叉查找樹
		return true;
	bool b1 = JustBST(root->mLeft);//遞歸的判斷左子樹是否是二叉排序樹
	if (b1 == false || predit > root->mData)//左子樹不是二叉排序樹或者predit的值大于目前根節點的值，則該樹不是二叉排序樹
		return false;
	predit = root->mData;//将要通路右子樹的時候，predit記錄下目前根節點的值
	bool b2 = JustBST(root->mRigjt);//遞歸去判斷右子樹是否為二叉排序樹
	return b2;
}
           

判斷完了二叉樹是不是二叉排序樹之後，我們再來判斷這棵樹滿足不滿足二叉平衡樹的性質。

可以遞歸的去判斷左子樹是否是平衡的，右子樹是否是平衡的，然後再通過比較高度差，判斷自身是否是平衡的。見如下代

bool isBalanced(binaryTreeNode* root)
 {
        if(root==NULL)
            return true;
        //判斷左右子樹是否平衡，并且判斷高度差
        if(isBalanced(root->mLeft)&&isBalanced(root->mRight)&&abs(height(root->mLeft)-height(root->mRight))<=1)
            return true;
        return false;
    }
    //得到深度
    int height(binaryTreeNode*root)
    {
        if(root==NULL) return 0;
        int l =  height(root->mLeft)+1;
        int r = height(root->mRight)+1;
        return l>r?l:r;
    }
           

2 判斷二叉樹是不是完全二叉樹

首先我們知道，如果一個二叉樹的深度為k,且1~k-1層的節點數都達到了最大個數，且第k層的節點都集中在左邊，那麼這樣的二叉樹就是一個完全二叉樹，如下圖所示，是一個完全二叉樹：

可以看出一顆完全二叉樹隻可能最後一層的節點不是滿的。是以我們可以采用層次周遊的方法來進行判斷，在周遊的時候我們隻去判斷目前節點為不為空，不管子節點為不為空都入隊。

如上圖所示，當周遊完10這個元素的時候，對列裡面全是為NULL的元素，這個時侯我們周遊到一個空元素，這時候不再入隊，隻需判斷隊中元素有沒有不為空的元素，如果有，那麼這個樹就不是完全二叉樹。

bool IsComTree(binaryTreeNode* t)
{
	if (t == NULL)
		return true;
	//對列
	queue<binaryTreeNode*> que;
	que.push(t);
	while (t=que.front())
	{
		//無論子節點為不為空，都入隊
		que.push(t->mLeft);
		que.push(t->mRight);
		que.pop();
	}
	while (!que.empty())
	{
		if (que.front())
			return false;
		que.pop();
	}
	return true;
}
           

3 判斷二叉樹是不是滿二叉樹

在一棵二叉樹中，如果所有的分支節點都有左右孩子，并且葉子節點都集中在最後一層，那麼這二樣的二叉樹稱為滿二叉樹，如下圖所示：

由于滿二叉樹的特性，我們可以得滿二叉樹的一些特性：

1. 一個層數為k的滿二叉樹的節點總數為2的k次方j減1，一定是奇數個。
2. 第i層節點數為2的i減1次方。

是以在判斷一顆二叉樹是不是滿二叉樹的時候，可以用上述的兩個性質來判斷。

int Count(binaryTreeNode* t)
{
	if (t == NULL)
		return 0;
	return 1 + Count(t->mLeft) + Count(t->mRight);
}

int TreeDeep(binaryTreeNode* t)
{
	if (t == NULL)return 0;
	int left = TreeDeep(t->mLeft) + 1, right = TreeDeep(t->mRight) + 1;
	return left > right ? left : right;
}
bool IsFullTree(binaryTreeNode* t)
{
	if (t == NULL)
		return true;
	//節點數
	int num = Count(t);
	//層數
	int deep = TreeDeep(t);
	if (num == pow(2, deep) - 1)
		return true;
	return false;
}