关于完全二叉树的一些算法

首先明确一下完全二叉树的定义:

在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）.

完全二叉树是由完美二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的完美二叉树中编号从1至n的结点一一对应时称之为完全二叉树.满二叉树是

关于满二叉树的定义我迷惑了好久,最后才得知原来国内外对于满二叉树的定义并不一样,国内满二叉树的定义是一棵深度为k,具有2^k - 1个节点的二叉树;而国外对于二叉树的定义则是树中除了叶子节点，每个节点都有两个子节点的二叉树.为了避免歧义,这里采用浙大数据结构中的说法「完美二叉树」来表示国内版的满二叉树.

根据定义,我来证明一下如何计算二叉树左子树的规模.

假设有一棵深度为h的完美二叉树,那么它的第k层的节点个数是2^(k - 1),那么总节点数是2^h - 1,最后一层节点数是2^(h - 1),除去最后一层的节点个数是2^(h -1) - 1. 如果又一棵总节点数为N的完全二叉树,设高度为H,到第H层的完美二叉树一共有2^H - 1个节点.设最底层有x个节点,那么有以下方程

2^H - 1 + x = N
H = (int)log2(N + 1)

因为已知了节点总数N,所以算出H后就可以算出最底层一共有多少个节点.

然后,我们需要在算一下左子树的节点数,H层的总节点数是2^H - 1那么左节点也就是少了一层,2^(H-1) - 1.这时候就有一个问题,x个节点并不一定全是位于左子树,所以需要进行比较,x最大数目是2 ^ (H - 1) ,所以最后要做一个判断,x = min(x,2^(H-1)),左子树的个数应该是2^(H-1)-1 + x.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int mod = 1000000007;

long long qpow(long long A,long long n) {
	long long ans = 1;
	while (n) {
		if (n & 1) {
			ans = (ans * A) % mod;
		}
		n >>= 1;
		A = (A * A) % mod;
	}
	return ans;
}

long getLeftLength(int n) {
	int h = (int)log2(n + 1);
	return qpow(2, h - 1) - 1 + 
			min(n - qpow(2, h) + 1,
				qpow(2, h - 1));
}

int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	cout << getLeftLength(n);
}

然后再写一个判断完全二叉树的算法.同样根据二叉树的性质,显然所有的完全二叉树和满二叉树都可以补成一个完美二叉树.那么就当他们的叶子结点是存在的(地址为NULL),如果是完全二叉树,那么在层序遍历时只有最后才会遇到这些空节点,而算法的思路就是判断这些空节点的位置,如果不在末尾,那么便可以证明不是完全二叉树.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isCompleteTree(Node* root) {
	if (root == NULL) {
		return true;
	}
	Node* tmp = NULL;
	queue<Node*> q;
	q.push(root);
	while (tmp = q.front() != NULL) {
		q.pop();
		q.push(tmp -> Left);
		q.push(tmp -> Right);
	}
	while (!q.empty()) {
		tmp = q.front();
		q.pop();
		if (tmp != NULL) {
			return false;
		}
	}
	return true;
}
script>