数据结构——链式二叉树
目录
🍁一、二叉树的遍历
🌕（一）、前序遍历(Preorder Traversal 亦称先序遍历)
🌕（二）、中序遍历(Inorder Traversal)
🌕（三）、后序遍历(Postorder Traversal)
（四）、层序遍历
🍁二、学习链式二叉树的意义
🍁三、二叉树遍历的代码实现
🌕（一）、前序遍历的代码实现
🌕（二）、中序遍历的代码实现
🌕（三）、后序遍历的代码实现
🌕（四）、求节点个数
🌕（五）、求叶子节点的个数
🌕（六）、求第K层的节点个数
🍁一、二叉树的遍历
在此之前我们先了解一下二叉树的四种遍历方式。
二叉树遍历 (Traversal) 是按照某种特定的规则，依次对二叉 树中的节点进行相应的操作，并且每个节点只操作一次 。
🌕（一）、前序遍历(Preorder Traversal 亦称先序遍历)
即先访问根节点，再访问左子树，最后访问右子树，如下图：
🌕（二）、中序遍历(Inorder Traversal)
即先访问左子树，再访问根节点，最后访问右子树，如下图：
🌕（三）、后序遍历(Postorder Traversal)
即先访问左子树，再访问右子树，最后访问根节点，如下图：
（四）、层序遍历
即一层一层的访问完毕，如下图：
🍁二、学习链式二叉树的意义
（一）、首先我们学习这部分知识要知道的是：普通的二叉树是没有意义的，你说用来存储数据，我直接用顺序表和链表等等不是更方便吗？
（二）、我们在这里学习链式二叉树有两个意义：
①：为后续学习更复杂的二叉树搜索树（如AVL、红黑树）打基础；
②：很多OJ题就喜欢考这一块；
（三）、在这里增删查改不是重点，我们重点学习二叉树的结构（递归结构）
🍁三、二叉树遍历的代码实现
在实现遍历算法之前，为我们首先得有一棵二叉树，因为我们只需要测试某一个功能，所以不需要完整的二叉树结构，这时我们就可以手动的快速建立一个二叉树，如下：
#include<stdio.h> #include<stdlib.h>//二叉树结构体 typedef struct BinaryTreeNode {struct BinaryTreeNode* right;struct BinaryTreeNode* left;int val; }BTNode;//创建一个结点 BTNode* BuyNode(int x) {BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){printf("malloc fail");return;}node->val = x;node->right = NULL;node->left = NULL;return node; }int main() {//手动构建一颗二叉树//获得6个结点BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);//手动连接一个二叉树node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return 0; }如上就是该二叉树的代码结构：
🌕（一）、前序遍历的代码实现
//前序遍历 void PrevOrder(BTNode* node1) {if (node1 == NULL)return;printf("%d ", node1->val);PrevOrder(node1->left);PrevOrder(node1->right); }上面就是前序遍历的代码部分，根据规则先访问根节点（即打印），再访问左子树，最后访问右子树（递归），代码部分很简洁，但最重要的是要理解其递归栈帧展开结构：
、
蓝色字体是该位置表示的结点；
红色箭头是代码走向；
红色带圈数字是代码执行顺序；
🌕（二）、中序遍历的代码实现
这三种遍历方法无非就是访问顺序不一样，所以只需要改变相应顺序即可：
//中序遍历 void InOrder(BTNode* node1) {if (node1 == NULL)return;PrevOrder(node1->left);printf("%d ", node1->val);PrevOrder(node1->right); }先访问左子树，再访问根节点（打印），最后访问右子树；
递归栈帧开辟与前序类似，可参考前序遍历自行思考；
🌕（三）、后序遍历的代码实现
//后序遍历 void EndOrder(BTNode* node1) {if (node1 == NULL)return;PrevOrder(node1->left);PrevOrder(node1->right);printf("%d ", node1->val); }
🌕（四）、求节点个数
//求结点个数 int TreeSixe(BTNode* root) {return (root == NULL) ? 0 : (TreeSixe(root->left) + TreeSixe(root->right)+1); }求一颗二叉树有多少个节点，我们很容易想到和遍历的思路有关，这样我们就可以写出上述代码：
具体我们可以结合递归栈帧展开图来读代码，由上述所示，我们先计算的是左子树的节点个数，再计算右子树的节点个数，最后再加上当前根节点数，然后返回值，所以这类似于一种后序遍历。
🌕（五）、求叶子节点的个数
//求叶子结点个数 int TreeLeafSize(BTNode* root) {//度为1的节点就可能访问到NULL，所以需要此判断if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return TreeLeafSize(root->left) + TreeLeafSize(root->right);}三种情况：
①：该节点为空，返回0；
②：该节点的左孩子和右孩子都为NULL，即该节点为叶子节点，此时返回1；
③：该节点即不为NULL，也不为叶子节点，即该节点为非叶子节点，此时将任务抛给它的左右子树（左右孩子），所以返回递归和。
注意：
这里有一点容易混淆，就是很多人觉得最多就到叶子节点，不会到空节点，所以第一个if是不是可以不要？答案肯定是要的，因为这种想法是忽略了度为1的非叶子节点的情况，这种节点只有一个孩子，所以当该孩子访问完后就会访问另一个孩子，即访问到NULL；
🌕（六）、求第K层的节点个数
//求第k层的结点数 int TreeKLevel(BTNode* root,int k) {if (root == NULL){return 0;}if (k == 1)return 1;return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1); }如求第三层，即为求第一层的第三层==求第二层的第二层==求第一层的第一层，利用k--1，每递归依次，就进行一次k-1表示到达下一层，当k==1时，即当前层数为要求节点数的层数，若root为NULL，即没有该节点，返回0；若k!=1,root不等于NULL，即还没有到达要求层数，则继续向下层递归。
本次知识到此结束，希望对你有所帮助！