什么是树

树是一种非线性结构。树有一个特殊的节点，叫做根节点。根节点是一个树的起点，除根节点外，它下面的节点被分为很多的分支。以每个分支节点为起点又可以构成一个树，称为子树。由根节点及子树构成的结构称为树

树的相关概念

节点的度：该节点直接相连了几个节点，就是几度。
叶子节点：度为0的节点
分支节点：度不为0的节点
父亲节点：该节点有连接下一层的节点，该节点即为父节点
子节点：父节点连的节点为子节点
兄弟节点：有共同父节点的节点，互称为兄弟节点。
树的度：节点中度最大的，就是树的度。
节点的层次：如果定义根节点为第 1层，那么根的子节点为第二层，依次类推。
树的的高度（深度）：节点的最大层数为树的深度。
堂兄弟节点：处于同一层的节点。
节点的祖先：从根到该节点所经分支的全部节点。
子孙：以某节点为根的子树中任意一个节点都称为该节点的子孙
森林：多颗树构成的集合称为森林。

什么是二叉树

一个二叉树是节点的集合，该集合可以为空，也可以由根节点连接左右子树构成。
二叉树的特点：
1.每个节点的度最大为2。
2.二叉树有左右子树，因此是有序的，左右不能颠倒

特殊的二叉树

满二叉树：每一层的节点数都达到最大。
完全二叉树：除最后一层外，每一层的节点数都达到最大，且最后一层的节点都位于左部。

二叉树的性质

若根节点为第一层，那么二叉树的第i层最多有2^(i-1)个节点，总节点数最多有2^h-1。
对于任意一个二叉树，如果度为0的节点有n0,那么度为2的节点n2=n0-1。
对一个完全二叉树进行编号，编号的规则：自上而下，自左而右。
那么，第i个节点对应的左节点为2i+1，右节点为2i+2，对应的父节点为(i-1)/2。

链式二叉树

二叉树类型的创建

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

二叉树的遍历

前序遍历：

先访问根节点，再访问左子树，最后访问右子树；每个子树又可以分为根，左树，右树。不断的递归，直到每个子树的根为空。

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
		
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);

}

中序遍历：

先访问左子树，再访问根节点，最后访问右子树

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->data);
	
	BinaryTreeInOrder(root->right);
	
	
}

后序遍历：

先访问右子树，再访问左子树，最后访问根节点

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}

二叉树节点的个数

先访问根，不为空就加1，然后访问左右子树。为空就返回0

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
		return 1+ BinaryTreeSize(root->left)+ BinaryTreeSize(root->right);

}

查找数据为X的节点

先查找根节点，然后再分别查找左右子树，当为空的时候返回空，当节点的数据为x时，则返回该节点的地址。然后把左右子树按上面的方式继续查找。

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{

	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* ret1=BinaryTreeFind(root->left,x);

	if (ret1)
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);

	if (ret2)
		return ret2;

	return NULL;
}

查找叶子节点的个数

出度为0的节点为叶子节点，那我们就查找左右孩子为空的节点。

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

第k层节点的个数

我们把根看成第k层，那么实际上的第k层就是第一层。
如果节点为空就返回0，如果k为1就是到了第k层了，返回1。
上述是归的条件。递就是按这个逻辑继续查找左，右子树。

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return BinaryTreeLevelKSize(root->left, k - 1)+ BinaryTreeLevelKSize(root->right, k - 1);

}

二叉树的高度

要求树的高度就是求路径最大的。
我们可以先比较左右子树的高度，然后最大的子树的高度加1就是树的高度。这个就是不断递归的过程。

int TreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	int ret1 = TreeDepth(root->left);
	int ret2 = TreeDepth(root->right);

	if (ret1 > ret2)
		return ret1+1;
	else
		return ret2+1;

}

二叉树的层序遍历

用一个队列储存节点，当一个节点出队时，它的孩子节点入队。这样就实现了层序遍历。

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur == NULL)
			printf("# ");
		else
		{
			printf("%d ", cur->data);
			QueuePush(&q, cur->left);
			QueuePush(&q, cur->right);
		}
	}
	QueueDestroy(&q);
	printf("\n");
}

判断二叉树是不是完全二叉树

按照层序遍历，如果是完全二叉树，当出队列的节点为空的时候，后面所有的节点都是空，反之不是完全二叉树。

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur == NULL)
			break;
		else
		{
			QueuePush(&q, cur->left);
			QueuePush(&q, cur->right);
		}
	}
	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}