数据结构——二叉树的链式结构

一颗二叉树的结点数我们可以看作是根结点+左子树结点数+右子树结点数，那左右子树的结点数又是多少呢？按照相同的方法继续拆分，层层递归直到左右子树为空树，返回空树的结点数0即可。递归代码如下：

// 二叉树节点个数
int TreeSize(TreeNode* root)
{
	return root == NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

3.2 二叉树的叶子结点数

左右子树都为空的结点即是叶子结点。这里分为两种情况：左右子树都为空和左右子树不都为空。

（1）当左右子树都为空时，则这颗树的叶子结点数为1(根节点)。

（2）当左右子树不都为空，即根结点不是叶子结点时，这棵树的叶子结点数就为左子树叶子结点数+右子树叶子结点数（空树没有叶子结点）。
 

// 二叉树叶子节点个数
int  TreeLeafSize(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

3.3 二叉树第k层结点数

一颗树第k层的结点数我们可以拆分为其左子树第k-1层结点+右子树第k-1层结点。（注：当前节点为第一层）

（1）若为空树，无论哪层节点数都是0

（2）若不是空树且k==1,则只有一个节点（根节点）

// 二叉树第k层节点个数
int TreeLevelKSize(TreeNode* root, int k)
{
	assert(k > 0);
	if (root!=NULL&&k == 1)
	{
		return 1;
	}
	if (root == NULL)
	{
		return 0;
	}
	if (k > 1)
	{
		return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
	}
}

// 判断二叉树是否是完全二叉树
bool TreeComplete(TreeNode* root)
{
	Queue pq;
	QueueInit(&pq);
	if (root == NULL)
	{
		QueueDestroy(&pq);
		return;
	}
	QueuePush(&pq, root);
	
	while (!QueueEmpty(&pq))
	{
		
			TreeNode* front = QueueFront(&pq);
			
			QueuePop(&pq);
			if (front == NULL)
			{
				break;
			}
				QueuePush(&pq, front->left);

			
				QueuePush(&pq, front->right);
			
	}
	while (!QueueEmpty(&pq))
	{
		TreeNode* front = QueueFront(&pq);

		QueuePop(&pq);
		if (front != NULL)
		{
			return false;
		}
	}
	QueueDestroy(&pq);
	return true;
}

四、二叉树的查找

二叉树的查找本质上就是一种遍历，只不过是将之前的打印操作换为查找操作而已。我们可以使用前序遍历来进行查找：

（1）先比较根结点是否为我们要查找的结点，如果是，返回根节点地址

（2）如果不是，遍历左子树，如果左子树是，直接返回节点地址；不是则遍历右子树，如果右子树是，直接返回节点地址，不是返回空，说明左右子树都没找到。

// 二叉树查找值为x的节点
TreeNode* TreeFind(TreeNode* root, DataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	TreeNode* node1 = TreeFind(root->left, x);
	if (node1)
	{
		return node1;
	}
	TreeNode* node2 = TreeFind(root->right, x);
	if (node2)
	{
		return node2;
	}
	return NULL;
}

五、二叉树的高度/深度

树中结点的最大层次称为二叉树的高度。因此，一颗二叉树的高度我们可以看作是

1(根结点)+左右子树高度的较大值。层层递归下去直到遇到空树返回0即可，

这里值得注意的是：不要写成

return TreeHeight(root->left)>TreeHeight(root->right) ? 
		TreeHeight(root->left)+1:TreeHeight(root->right)+1;
}

这里比较好左右子树较大的一颗后，又会从新递归较大那颗子树高度，会造成重复计算，时间复杂度增高。

我们要保存好左右子树层数，避免重复计算，代码如下：

//二叉树的高度
int TreeHeight(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);
	return  left>right ? 
		left+1:right+1;
}

六、完全二叉树的判断

这里的思路利用了层序遍历，不同的是，将空节点指针也入队列，当我们遇到第一个空节点指针则退出循环，然后对队列进行检测，若第一个空节点指针以后全都是空，则为完全二叉树，反之，不为完全二叉树。

注：当在队列遇到第一个空节点指针时，二叉树中空节点指针之后所有非空节点指针全部进队列

思路解析图如下：