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练习
