🐾探究二叉树的意义
🎄1.为什么学二叉树？
普通二叉树的增删查改没有意义
存储数据结构复杂，不如用顺序表、链表
那我们还为什么学习它呢❓
1️⃣为了后面学习更复杂的二叉树，打基础（搜索二叉树、AVL树、红黑树、B树…）
2️⃣有很多二叉树的OJ算法题都是处在普通二叉树上
🐾二叉树链式结构的实现
🎄1.前置说明
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。
由于现在大家对二叉树结构掌握还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
下面我们来手搓一棵二叉树：
📜代码实现👇🏻：
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data;// 存放数据域 struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); assert(node); node->data = x; node->left = NULL; node->right = NULL; } BTNode* CreatBinaryTree() { 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 node1; }
📌我们用typedef来重命名，可以很好的简化代码关键词
📌注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。
再看二叉树基本操作前，再回顾下二叉树的概念💍，二叉树是
空树
非空：根节点，根节点的左子树、根节点的右子树组成的。
从概念中可以看出，二叉树定义是递归式♻️的，因此后序基本操作中基本都是按照该概念实现的✨
🎄2. 四大遍历方法
二叉树的遍历有：前序/中序/后序的递归结构遍历：
1️⃣前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2️⃣ 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）
3️⃣ 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为
根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历
除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。
4️⃣层序遍历：设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
🤏简单来说：
🎄3. 前序遍历
先序遍历结果为：A B D H I E J C F K G
1️⃣ 动画演示：👇🏻
我们可以理解为一个小人从一棵二叉树根节点为起点，沿着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就是先序遍历的结果
2️⃣遍历规律💫：👇🏻
3️⃣代码实现💡：
void PreOrder(BTNode* root) { if (root == NULL)// 递归中遇到NULL，返回上一层节点 { printf("# "); return; } printf("%d ", root->data); PreOrder(root->left);// 递归遍历左子树 PreOrder(root->right);//递归遍历右子树 }
➡️采用了分治算法：
大问题变成小问题，分成类似规模的子问题（大部分的分治都用递归进行）
举个例子：比如校长🥸要排查我们学院返校的名单，校长吩咐院长，院长吩咐辅导员…
校长——院长——辅导员——班长——学生们
❗递归展开图（以下图为例）：
🌍此处的递归结果：1 2 3 # # # 4 5 # # 6 # #
同学们不懂的地方一定要画图去理解！！
🎄3. 中序遍历
中遍历结果为：H D I B E J A F K C G
1️⃣ 动画演示：👇🏻
2️⃣代码实现💡：
void InOrder(BTNode* root) { if (root == NULL)// 递归中遇到NULL，返回上一层节点 { printf("# "); return; } InOrder(root->left);// 递归遍历左子树 printf("%d ", root->data); InOrder(root->right);// 递归遍历右子树 }
❗递归展开图（以下图为例）：
画图很重要，不理解就要去画图✅
还是刚刚的递归图，只是改变了访问顺序，中序：左子树——根——右子树
🌍此处的递归结果：# 3 # 2 # 1 # 5 # 4 # 6 #
🎄4. 后序遍历
1️⃣ 动画演示：👇🏻
2️⃣代码实现💡：
void PostOrder(BTNode* root) { if (root == NULL)// 递归中遇到NULL，返回上一层节点 { printf("# "); return; } PostOrder(root->left);// 递归遍历左子树 PostOrder(root->right);// 递归遍历右子树 printf("%d ", root->data); }
❗递归展开图（还是以下图为例）：
还是要去画递归展开图，只是改变了访问顺序，后序：左子树——右子树——根
🌍此处的递归结果：# # 3 # 2 # # 5 # # 6 4 1
ps：递归展开图多画就能理解，才方便后序更难的二叉树。
🎄5. 层序遍历
1️⃣ 演示：👇🏻
2️⃣🎇思路讲解：
借助一个队列实现：先进先出
上一层带下一层，先进去的先出，每次循环出一个
3️⃣代码实现💡：
void LevelOrder(BTNode* root) { Quene q; QueneInit(&q); if (root) { QuenePush(&q, root); } while (!QueneEmpty(&q)) { BTNode* front = QueneFront(&q); printf("%d ", front->data); QuenePop(&q); if (front->left) { QuenePush(&q, front->left); } if (front->right) { QuenePush(&q, front->right); } } printf("\n"); QueneDestroy(&q); }
完全一样
🐾探究二叉树节点个数以及高度
🎄1.二叉树节点个数
定义一个Count，计算结点的个数，那么Count是全局变量还是局部变量？
答案：全局变量！不然每次递归各自加各自的Count，无意义。
💡代码实现：遍历法
//遍历 int count = 0; void BinaryTreeSize1(BTNode* root) { if (root == NULL) { return; } ++count; BinaryTreeSize1(root->left); BinaryTreeSize1(root->right);//此处为前序，其实前中后序都是可以的 }
同一棵树在我第两次调用的时候，发现第二次的结果不同于第一次
📌很简单，第二次是在第一次调用的基础上累加的。所以最好的方式是：每次调用之前，都给count初始化为0
到这里大家是不是以为已经解决了？其实这里还有个大问题：linux中的多线程
如果这个函数被多线程去调用就会出错，也就是并发，两个线程都调用这个函数，会加在同一个count上，也就出错了。
那有没有更好的方法呢❓ 答案肯定是有的✅
💡代码实现：分治思路
//分治思想 int BinaryTreeSize2(BTNode* root) { return root == NULL ? 0 : BinaryTreeSize2(root->left) + BinaryTreeSize2(root->right) + 1; }
如果大家对这个方法不熟悉，可以画一下栈帧展开图🙌
🎄2. 二叉树叶子节点个数
int TreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return TreeLeafSize(root->left)+TreeLeafSize(root->right); }
这个理解起来还可以吧🤏拿捏~
🎄3. 二叉树第k层节点个数
大家看到k层是不是想到了层序遍历呢？
但这和层序遍历没有关系，还是要用子问题的思维去解题~转化成：
求左子树的第k-1层+求右子树的第k-1层
💡代码实现
int TreeKLevel(BTNode* root, int k) { assert(root); if (root == NULL) return 0; if (k == 1) return 1; return TreeKLevel(root->left,k-1) + TreeKLevel(root->right,k-1); }
ps：注意递归的时候只能用k-1而不是 k–
因为递归到时候，递归了左子树，之后还要递归右子树，若使用了k–，递归左树的时候k已经自减减少了，再回来求右树时候的k已经是错的k了，所以要保证k不能变
🎄4. 二叉树查找值为x的结点
第一次写：(错误写法)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root->data == x) return root; if (root == NULL) return NULL; if (BinaryTreeFind(root->left, x)) return BinaryTreeFind(root->left, x); if (BinaryTreeFind(root->right, x)) return BinaryTreeFind(root->right, x); return NULL; }
这种写法，我们发现如果我们找到了结点，返回值的时候还要再递归一次，太费劲了
好比我们写博客，写到一半，电脑死机了，还要重新写的感觉😈
💡代码实现（最好的方式💯）
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; BTNode* left = BinaryTreeFind(root->left, x); if (left) return left; BTNode* right = BinaryTreeFind(root->right, x); if (right) return right;//每一次return都是回到上一层 return NULL; }
🎄5.求二叉树的高度
二叉树的深度改怎么样求呢？
一样利用分治的思想来实现
左右分别递归，返回上一层加1，再比较左右树高度
🎇思路讲解：
💡代码实现
int TreeDepth(BTNode* root) { if (root == NULL) return 0; int leftDepth = TreeDepth(root->left); int RightDepth = TreeDepth(root->right); return leftDepth > RightDepth ? leftDepth+1 : RightDepth+1; }
🎄6.销毁二叉树
销毁用什么序列呢？
后序！
若使用前序遍历的话，删除了节点还能找到左右子树么？
可以是可以，但还要指针保存起来，比较麻烦
💡代码实现
void TreeDestroy(BTNode* root) { if (root == NULL) return; TreeDestroy(root->left); TreeDestroy(root->right); printf("%p:%d\n", root, root->data); //用于打印辅助观察 free(root); }
对应后序是3 2 5 6 4 1
📢写在最后
能看到这里的都是棒棒哒🙌！
想必二叉树也算是数据结构中比较难🔥的部分了，如果认真看完以上部分，肯定有所收获。
接下来我还会继续写关于📚《二叉树练习题目》等…
💯如有错误可以尽管指出💯
🥇想学吗？我教你啊🥇
🎉🎉觉得博主写的还不错的可以一键三连撒🎉🎉
