目录
树的概念
二叉树
二叉树性质
二叉树的遍历
前序遍历
中序遍历
后序遍历
层序遍历
二叉树节点个数
二叉树叶子节点个数
二叉树高度
二叉树第k层节点个数
二叉树查找值为x的节点
判断二叉树是否是完全二叉树
二叉树销毁
树的概念
树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。把它叫做“树”是因为它常看起来像一棵倒挂的树，也就是说它常是根朝上，而叶朝下的。
树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用，如在操作系统中,可用树来表示文件系统的结构。又如在数据库系统中，树形结构也是信息的重要组织形式之一 。
树在不同领域也有不同的定义。
1、在数学中，树是一种无向图，其中不存在环路（即无回路），且任意两个结点之间有且仅有一条简单路径相连 [2]。这种定义主要用于图论和离散数学中，用于研究树的性质和特征。
2、在操作系统中，树是一种用于表示文件系统的结构，其中根目录位于树的顶部，子目录和文件位于根目录下 [3]。这种定义主要用于操作系统设计和文件管理。
3、在数据库中，树是一种用于表示层次关系的数据结构，树结构常用于实现数据库的索引、表示层次数据关系（如组织结构、分类目录）以及优化查询操作。这种定义主要用于数据库设计和数据管理，以提高数据检索效率和结构化数据的存储。
基本术语：
- 1.结点：包含一个数据元素及若干指向其子树的分支；
- 2.结点的度：一个结点拥有的子树的数目；
- 3.叶子或终端结点：度为0的结点；
- 4.非终端结点或分支结点：度不为0的结点；
- 5.树的度：树内各结点的度的最大值；
- 6.孩子结点或子结点：结点的子树的根称为该结点的孩子结点或子结点；
- 7.双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的双亲结点或父结点；
- 8.兄弟结点：同一个双亲的孩子之间互称兄弟；
- 9.祖先结点：从根到该结点所经分支上的所有结点；
- 10.子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；
- 11.结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第 L 层．则其子树的根就在第 L + 1层；
- 12.堂兄弟结点：其双亲在同一层的结点互为堂兄弟；
- 13.树的深度或高度：树中结点的最大层次；
- 14.森林：由m（m > 0）棵互不相交的树的集合称为森林;
- 15.有序树和无序树：树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树；
- 16.路径和路径长度：路径是由树中的两个结点之间的结点序列构成的。而路径长度是路径上所经过的边的个数
二叉树
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
二叉树性质
1.若规定根节点的层数为1，则一棵非空二叉树上的第 i 层最多有个节点
2.若规定根节点的层数为1，则深度为 h 的二叉树的最大节点数是
3.对任何一棵二叉树，如果度为0其叶节点个数为，度为2的分支结点个数为
,则有
4.若规定根节点的层数为1，具有 n 个节点的满二叉树的深度，
5.对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所以结点从0开始编号，则对于序号为 i 的结点有：
- 若 i > 0, i 位置结点的双亲序号：(i - 1) / 2; i = 0, i 为根节点编号，无双亲结点。
- 若 2i+ 1 < n ，左孩子序号 2i+ 1， 2i+ 1 >= n 则为左孩子
- 若 2i+ 2 < n，右孩子序号：2i+ 2，2i+ 1 >= n 则无右孩子
二叉树的遍历
前序遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
//前序
void Preorder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->data);
Preorder(root->left);
Preorder(root->right);
}中序遍历
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
//中序
void Inorder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
Inorder(root->left);
printf("%d ", root->data);
Inorder(root->right);
}
后序遍历
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
//后序
void Posorder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
Posorder(root->left);
Posorder(root->right);
printf("%d ", root->data);
}层序遍历
层序遍历（也称为广度优先遍历）是二叉树遍历的一种方法，其基本思想是从根节点开始，按照从上到下、从左到右的顺序访问二叉树的每一层节点。
层序遍历通常使用队列来实现：
- 将根节点放入队列中。
- 当队列不为空时，循环执行以下操作：
- 从队列中弹出一个节点，访问该节点。
- 如果该节点有左子节点，将左子节点加入队列。
- 如果该节点有右子节点，将右子节点加入队列。
- 继续执行步骤2，直到队列为空。
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);
}
QueueDestory(&q);
}二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
static int size = 0;
if (root == NULL)
return 0;
else
++size;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return size;
}不能这样写，这样写每次调用这个函数都会累加
可以这样写
int size = 0;
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
else
++size;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return size;
}但是每次调用这个函数的时候，都要重置一下size。
最好的方法 分治递归
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 :
BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}二叉树叶子节点个数
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);
}什么是叶子结点呢？通常来讲在一棵树里面，如果一个结点没有左子树和右子树，那么它就是叶子。左子树和右子树为空，那么叶子结点个数加1，返回给上一层。
二叉树高度
int BinaryTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
return BinaryTreeHeight(root->left) > BinaryTreeHeight(root->right) ?
BinaryTreeHeight(root->left) + 1 : BinaryTreeHeight(root->right) + 1;
}上面这种方法存在效率问题，原因是递归返回后函数栈帧会销毁，没有记录，
int BinaryTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int left = BinaryTreeHeight(root->left);
int right = BinaryTreeHeight(root->right);
return left > right ? left + 1 : right + 1;
}
//int BinaryTreeHeight(BTNode* root)
//{
// if (root == NULL)
// return 0;
// return fmax(BinaryTreeHeight(root->left), BinaryTreeHeight(root->right)) + 1;
//}二叉树第k层节点个数
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);
}
求第k层结点个数，需要转化成当前问题和子问题。比如说，求第3层结点的个数，那么对这棵树的第一层来说，从它开始，求它向下的3层。然后k减1。对于第二层来说，求从它开始向下的第2层，k减1。对于第三层来说，就是求从它开始向下的第1层，为第1层时，返回1给上一层。
二叉树查找值为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;
}如果走到叶子节点的下一个，即root为空，就返回空。如果在左子树找到了，那么在右子树就没必要找了，就直接返回这个节点。但是一定要记录这个节点，因为递归返回会销毁函数栈帧，你不返回给上层这个找到的节点的记录，上层不知道你找到没有，就认为没有找到。继续返回给它的上层。 如果左子树没有找到，右子树也没有找到，就返回空。
判断二叉树是否是完全二叉树
需要用到层序遍历
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//遇到第一个空，就可以开始判断，如果队列中还有非空，那就不是完全二叉树
if (front == NULL)
break; // 跳出循环，不再进行层序遍历
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
//开始判断队列中已有的数据
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//遇到非空,不是完全二叉树
if (front)
{
QueueDestory(&q);
return false;
}
}
QueueDestory(&q);
return true;
}首先定义一个队列，初始化队列，如果树不为空，那么让树的根结点入队列。通过一个while循环，可以把二叉树的所有节点全部遍历一遍，让它的节点入队列和出队列。这个while循环结束后吗，二叉树中的所有结点全部过了一遍，就算有 没有入队列的结点，也没有关系，因为这时只需要判断现在的队列中，是否还存在数据，如果存在，则说明不是完全二叉树，返回false。反之，说明为完全二叉树，返回true。这一层判断通过一个while循环完成。
二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
return;
BinaryTreeDestory((*root)->left);
BinaryTreeDestory((*root)->right);
free(*root);
}二叉树的销毁可以看成一个后序遍历，先左子树销毁，然后右子树销毁，最后根节点销毁。
