一、树的概念

树首先在逻辑结构上不是线性的。

我们将上图中的数据结构称为树。
树中，子树之间不能相交。
一棵N节点的树有N-1条边。

树的一些概念：

根节点：5是这个树的根节点，除了根节点以外，其他所有节点都有前驱节点。
父（双亲）节点：5是7的父节点，7是10的父节点。
子节点：7，9，6都是5的子节点。
兄弟节点：在同一层的节点。
节点的度：一个节点有几个子节点，就称它的度为几。5节点的度为3.
树的度：一个树的度等于它节点中最大的度。
叶子节点：没有子节点的节点成为叶子节点。
分支节点：除叶子节点外都是分支节点。
节点的层次：从根节点开始，根节点是第一层，其子节点是第二层。
树的高（深）度：树中层数最大值。
子节点的祖先：从根节点，到该节点之间的所有节点都是它的祖先。

二、树的定义

1.左孩子右兄弟表示法

//一个大佬的定义
typedef int TreeNodeDataType;
typedef struct TreeNode{
	TreeNodeDataType data;
	struct TreeNode* leftchi;
	struct TreeNode* rightbro;	
};

上面的方法叫做左孩子右兄弟表示法，大佬非常牛逼。
我们每次都能找到一个节点的第一个孩子，也能通过它找到所有的兄弟。

2.双亲表示法

双亲表示法：
我们也可以用一个结构体数组，结构体中存储自己的值和父节点的下标。
这样我们可以从叶子节点向根输出。

3.树的应用

我们实际生活中，电脑的磁盘很显然就是一棵树，它有许多孩子（盘），然后孩子又有自己的孩子（文件夹）。总之树是非常重要的。

三、二叉树

1.二叉树的概念

二叉树就是一棵树中，每个节点的度都不超过2.

2.特殊的二叉树

满二叉树：树中每一层，节点都是满的。

完全二叉树：树中只有最后一层节点不是慢的，且最后一层节点从左往右存在，不能跳跃。

实际上，满二叉树就是一种特殊的完全二叉树。
假设满二叉树和完全二叉树都有K层。
则满二叉树节点为：n=2^K-1
完全二叉树节点为： 2^（K-1） <n<=2^K - 1

3.二叉树的定义及性质

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

对于性质3：
每当我们增加一个度为2的节点，同时也就增加了一个度为0的节点，而一开始有一个度为2和2个度为0的节点。

4.二叉树的函数及实现思想

1.遍历函数

对于二叉树来说，遍历是它最重要的函数。其解决思想，对于二叉树来说至关重要。

其遍历方法分为：

非层序遍历：
前序遍历,中序遍历，后序遍历
层序遍历

对于非层序遍历，其区别在于根节点的访问次序（它们都是使用递归函数来实现的）

对于上面的二叉树,我们来解释一下前序遍历：：

前序遍历的访问顺序是:根节点，左孩子，右孩子

先访问：12
然后：22
关键在于，访问左孩子时，22作为12的左孩子，又是231的根。
所以下一个访问对象：231（22的左孩子）
然后：1（231的左孩子）
然后：1的左孩子（NULL）
然后：1的右孩子（NULL）
此时，1的左右孩子都访问结束了，那么对于231来说，它的左孩子就访问结束了
所以下一个访问对象：5（231的右孩子）
然后：5的左孩子（NULL）
然后：5的右孩子（NULL）
此时，231的左右孩子都访问结束了，那么对于22来说，它的左孩子就访问结束了
然后：22的右孩子（NULL）
此时，22的左右孩子都访问结束了，那么对于1来说，它的左孩子就访问结束了
右子树访问同理

这个树的前序遍历为：
12 22 231 1 NULL NULL 5 NULL NULL NULL 55 21 NULL 7 NULL NULL NULL

中序遍历访问顺序为：左孩子 根节点 右孩子
后序遍历访问顺序为：左孩子 右孩子 根节点

我们发现在解决遍历过程中，我们其实将遍历所有节点划分为子问题：

我们需要遍历所有节点，只需要访问自己（根）+左孩子+右孩子，
而访问左孩子时，又变成了：访问自己+它的左孩子+它的右孩子。

这种划分子问题的思想将帮助我们解决很多树函数的问题。

而对于前中后序的遍历函数，实际上非常简单。

void PreOrder(BTNode* root)//前序遍历
{
	if(root==NULL)
	return ;
	printf("%d\n",root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}
void InOrder(BTNode* root)//中序遍历
{
	if(root==NULL)
	return ;
	InOrder(root->left);
	printf("%d\n",root->data);
	InOrder(root->right);
}
void PostOrder(BTNode* root)//后序遍历
{
	if(root==NULL)
	return ;
	PostOrder(root->left);
	PostOrder(root->right);	
	printf("%d",root->data);
}

层序遍历：其特点在于不使用递归函数，访问时分层进行。

对于上树：
层序遍历从12开始访问
然后是 22与55
然后是 231 NULL 21 NULL
然后是 1 5 NULL 7
然后是 NULL NULL NULL NULL NULL NULL
对于它的函数实现要使用队列来解决这个问题。

void TreeLevelOrder(BTNode* root)//层序遍历 
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);

		// 下一层，入队列
		if (front->left)
			QueuePush(&q, front->left);

		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");

	QueueDestroy(&q);
}

每当一个节点出队列，都将它的两个子节点入队列，当扫描到NULL，则不入队列

2.树的高度（深度）

先看函数的实现：

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

函数很简短，我们来挖掘一下它的思路：

我们来划分一下子问题：
一个树的高度==它左子树，右子树高度高的那一个+1，
那么怎么知道它左右子树的高度呢，不就又 == 它左子树，右子树高度高的那一个+1，以此递归
中止条件其实就是，root ==NULL
当它不断找自己的左右子树，直至到叶子节点，而叶子节点的左右子树为NULL

3.树节点查找

先看函数的实现：

BTNode* TreeFind(BTNode* root, BTDataType x)//返回节点 
{
	if(root==NULL)
	return NULL;
	if(root->data==x)
	return root;
	BTNode* left=TreeFind(root->left,x);
	if(left)
	return left;
	BTNode* right=TreeFind(root->right,x);
	if(right)
	return right;
	return NULL;
}

函数同样简短，我们来挖掘一下它的思路：

划分一下子问题：
在树中查找一个节点，我们应该分为：查看自己是不是，左孩子是不是，右孩子是不是
那么查看它左右孩子，不就又 ==查看自己是不是，左孩子是不是，右孩子是不是，以此递归
只要找到，直接return
中止条件：
1.首先当root ==NULL时，则返回NULL
2.若前几个判断都没进，则意味着自己属于分支节点，左子树，右子树都没找到，那么它这个分支就要返回NULL

4.树第K层节点个数

先看函数的实现：

int TreeKLevel(BTNode*root, int k)//树第K层节点个数
{
	if(K==1&&root)
	return 1;
	if(!root)
	return 0;
	return TreeKLevel(root->left,K-1)+TreeKLevel(root->right,K-1);
}

函数同样简短，我们来挖掘一下它的思路：

划分一下子问题：
在树中计算第K层节点，我们应该分为：自己的第K层节点个数==左子树第K-1层节点个数+右子树第K-1层节点个数
那么查看它左右孩子，不就又 ==左子树第K-1层节点个数+右子树第K-1层节点个数
中止条件：
1.首先当root ==NULL时，则返回我们应直接返回0
2.当K ==1时，就意味着已经到这层了，不用再往下了，此时再看一下自己是不是NULL即可。

总结

树这一节尤为重要，而划分子问题大部分情况下都是解决树问题的关键所在。
望诸君都能熟练掌握。