1、树的概念
在数据结构中，树（Tree）是一种非线性的数据结构，它由节点（Nodes）和连接节点的边（Edges）组成，具有以下特点：
节点：树中的每个元素称为节点。树有一个特殊的节点称为根节点（Root Node），它是树的顶部，没有父节点。除根节点外的其他节点可以有零个或多个子节点（Child Nodes）。
边：节点之间的连接称为边。在树中，边是从父节点指向子节点的。
层次结构：树中的节点可以分层。根节点位于第一层，它的子节点位于第二层，子节点的子节点位于第三层，以此类推。
没有环：在树结构中，不存在任何形式的环（Cycle）。这意味着从根节点到任何一个节点的路径是唯一的，不会有重复的节点。
子树：每个节点及其后代节点形成的树称为该节点的子树（Subtree）。
树的类型有很多，包括二叉树（Binary Tree）、平衡树（Balanced Tree）、B树（B-Tree）、红黑树（Red-Black Tree）等。每种类型的树都有其特定的性质和用途。本章我们主要讲解二叉树。
2、二叉树
二叉树是一种特殊的树形数据结构，它具有以下特点：
每个节点最多有两个子节点：在二叉树中，每个节点最多只能有两个子节点，通常称为左子节点和右子节点。
有序性：二叉树的子节点具有顺序性，即不能随意交换左子节点和右子节点的位置，这种顺序性对树的遍历有重要影响。
层次结构：二叉树的节点按层次排列，根节点在第一层，其左子节点和右子节点在第二层，它们的子节点在第三层，以此类推。
子树：每个节点的子树也是二叉树。左子树和右子树是相互独立的二叉树。
二叉树可以进一步分类，例如：
满二叉树：除了最后一层外，每一层上的节点数都达到最大值，且最后一层的节点都连续集中在最左边。
完全二叉树：除了最后一层外，每一层上的节点数都达到最大值，并且最后一层的节点都尽可能地靠左排列。
二叉搜索树：每个节点的左子树只包含小于当前节点的数，右子树只包含大于当前节点的数，具有排序特性。
二叉树的遍历通常有三种方式：前序遍历（Preorder）、中序遍历（Inorder）和后序遍历（Postorder）。遍历的顺序会影响输出结果，这在算法设计和数据处理中非常重要。
二叉树在计算机科学中有广泛的应用，如堆结构、哈夫曼编码、二叉搜索树用于数据库和文件系统的索引等。通过二叉树，可以有效地组织和检索数据，实现高效的数据操作。
3、二叉树的创建和遍历
二叉树的创建
根据前序遍历构建出二叉树
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
assert(root);
root->data = a[(*pi)++];
root->left = BinaryTreeCreate(a,pi);
root->right = BinaryTreeCreate(a,pi);
return root;
}动图演示：
首先遍历a数组，遇到‘#’代表空结点，返回NULL，然后malloc一个节点的空间（二叉树结点提前定义过），然后给二叉树赋值 root->data=a[(*pi)++]; 接着递归左子树，然后递归右子树，最后返回root，
细节一：pi是数组下标的地址，因为我们是不断递归的，但是数组的下标也要往后++,所以我们要传下标的地址，才能改变数组下标，（不理解的可以复习一下函数传参的那一部分）。
细节二：为什么在函数内开辟空间，出了函数空间不会销毁？因为我们用的是malloc在栈区开辟的空间，返回了开辟空间的地址，只有我们释放掉这些空间或者整个程序结束后，这些空间才会销毁，
细节三：assert(root) 可要可不要，因为我们malloc开辟的空间可能会失败（但是在这里开辟空间失败的可能性太小了，因为开辟开辟的空间太小了），所以加个assert断言比较好，当然，去掉也是没有任何关系的。
如果让我们根据中序或者后序创建二叉树，我们只需要改一下顺序就好了。
二叉树的四种遍历方式：
前序遍历：根——左子树——右子树；
中序遍历：左子树——根——右子树；
后续遍历：左子树——右子树——根；
层序遍历：按层遍历，从左到右，需要借助队列来实现；
前序遍历
代码实现
// 二叉树前序遍历
//ABD##E#H##CF##G##
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
printf("%c ", root->data);
BinaryTreeInOrder(root->left);
BinaryTreeInOrder(root->right);
}这是用一个递归的思想，先打印根节点，遇到空结点也就是‘#’ 打印‘#’，直接return ，要是不为空，打印节点的值，再遍历左子树，最后遍历右子树，递归是从根节点开始，最后还是回到了根节点
中序遍历
代码实现：
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
BinaryTreePrevOrder(root->left);
printf("%c ", root->data);
BinaryTreePrevOrder(root->right);
}思想和前序遍历一样的，只是换了一下顺序，这里不再讲解了。
后序遍历
代码实现：
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}层序遍历：
层序遍历需要借助队列
代码实现：
// 层序遍历 借助队列
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c", front->data);
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
printf("\n");
QueueDestroy(&q);
}由于我用的C语言写，只能自己手搓一个队列，
思想是先初始化队列，如果根结点不为空，入队列，然后判断队列不为空，取出队头元素并且Pop掉队头元素，打印，然后将二叉树的左子树带入，然后带入右子树，由于队列具有先进先出的性质，可以打印出来层序遍历的二叉树,理解起来比较难，建议画图理解，（实在是想做动图，奈何实力不够，我能画出来，但是不会制作，等我学会了，再补回来）。
4、二叉树的销毁
二叉树的销毁也是用递归实现的，有两种方法，传一级指针和二级指针，
传一级指针:
//传一级指针
void BinaryTreeDestory(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);
}这里我们可以释放掉每一层递归开辟的空间，但是无法把root置空，因为我们传的是一级指针，对形参置空 ，对形参没有影响，所以我们可以在函数外面对root置空，也是比较方便
传二级指针:
//传二级指针
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
return;
BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));
free(*root);
*root = NULL;
}这里我们传root的地址，解引用可以直接作用到函数外部的root，注意递归调用的时候传地址不要弄错；
5、总结
二叉树的创建，销毁和遍历都了解了，但这些还差得很多，我们还无法熟练的用二叉树解决问题，主要是理解递归问题，还有很多性质还没有讲，敬请期待下期
二叉树的性质和OJ练习
