🍔前言
🥰我们学习完二叉树的“堆”以及堆的应用以后还有一个在平时面试题目中出现频率也非常高的结构等着我们呢，那就是—二叉树的链式结构（二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系）链式结构又分为二叉链和三叉链，当前我们使用的都是二叉链，后面的博客（红黑树等会用到三叉链）各位客官老爷，关注一下后续会更新呦！！！🥰🥰
🍔二叉树链式结构的实现
🍟基本构架
🥝在看二叉树基本操作前，再回顾下二叉树的概念
🔴二叉树是：
⭕ 空树
⭕ 非空：根节点，根节点的左子树、根节点的右子树组成的。
✅从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
😍代码：
typedef int BTDataType; //记录树内数据类型，方便后面修改 typedef struct BinaryTreeNode { BTDataType data; //记录节点 struct BinaryTreeNode* left; //指针指向左子树 struct BinaryTreeNode* right;//指针指向右子树 }BTNode; //结构体的名字
💧运用上面的这些代码，可以记录一颗二叉树的所有节点，所有推论也从这个地方出来了。后面也会有很多的结构跟这个有关。
🍔二叉树的遍历
🍪学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
🍟前序遍历
🚩前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。（根——左子树——右子树）
https://ucc.alicdn.com/images/user-upload-01/202012091634524.gif#pic_center
// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } printf("%d ", root->data); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); }
🍟中序遍历
🚩中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。（左子树——根——右子树）
// 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } BinaryTreeInOrder(root->left); printf("%d ", root->data); BinaryTreeInOrder(root->right); }
🍟后序遍历
🚩 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。（左子树——右子树——根）
// 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } BinaryTreePostOrder(root->left); BinaryTreePostOrder(root->right); printf("%d ", root->data); }
🍟层序遍历
🚩 层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
🔴层序遍历的思路及代码
⭕层序遍历需要用到队列的一些知大家可以先去了解一下队列的特点队列的概念及结构（内有成型代码可供CV工程师参考）_硕硕C语言的博客-CSDN博客如下图：
🚨需要注意的是进入队列的不是节点的值，而是节点的地址，这样做可以方便的把后面的左右子树的节点带出来，也方便了后面的判断。
// 层序遍历 void BinaryTreeLevelOrder(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);//队列的销毁 }
🥰 这个思想后面的判断二叉树是否是完全二叉树也要用到
