©2020-2024 ioDraw All rights reserved,
Privacy Policy
前言：
普通二叉树的增删查改没有意义？那我们为什么要先学习普通二叉树呢？
给出以下两点理由：
1.为后面学习更加复杂的二叉树打基础。（搜索二叉树、ALV树、红黑树、B树系列—多叉平衡搜索树）
2.有很多二叉树的OJ算法题目都是出在普通二叉树的基础上
让我们开始数据结构链式二叉树之旅吧！！！
1. 链式二叉树的遍历
1.1 前序、中序以及后序遍历概念
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历
1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 访问顺序—— 根
—> 左子树—>右子树
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
访问顺序—— 左子树—>根 —>右子树
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
访问顺序—— 左子树—>右子树—>根
举例
1.2 前序、中序以及后序遍历代码实现
1.2.1创建二叉树节点
typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode*
left; //左子树 struct BinaryTreeNode* right;//右子树 BTDataType data;//数据 }BTNode;
1.2.2 手动搓出一颗二叉树
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h>
#include <assert.h> typedef int BTDataType; typedef struct BinaryTreeNode {
struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data;
}BTNode; BTNode* BuyNode(BTDataType x) { BTNode* node =
(BTNode*)malloc(sizeof(BTNode)); assert(node); node->data = x; node->left =
NULL; node->right = NULL; return node; } 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; } void
PreOrder(BTNode* root) //前序遍历 { if (root == NULL) { printf("# "); return; }
printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); } void
InOrder(BTNode* root)//中序遍历 { if (root == NULL) { printf("# "); return; }
InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } void
PostOrder(BTNode* root)//后序遍历 { if (root == NULL) { printf("# "); return; }
PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); } int
main() { BTNode* root = CreatBinaryTree(); PreOrder(root);//前序遍历 printf("\n");
InOrder(root);//中序遍历 printf("\n"); PostOrder(root);//后序遍历 printf("\n"); return
0; }
1.2.3 代码结果
1.2.4 递归展开图
（学习二叉树的链式结构，一定要学会画递归展开图）
注意：访问到空树的时候，return的时候不是结束递归，是返回到函数被调用的地方
下面是前序遍历的左子树的递归展开图（右子树原理同理） 》》》
2. 求二叉树节点的个数
2.1 全局count的方式（不推荐）
在写代码的过程中要尽量少使用全局变量，这里也是一样的，采用全局变量会有下面的问题：
我们在调用两次的情况下，count会加倍
代码实现
int count = 0; void TreeSize1(BTNode* root) { if (root == NULL) { return; }
++count; TreeSize1(root->left); TreeSize1(root->right); }
2.2 采用分治的思路
将一颗二叉树分解为3个部分——根节点、左子树、右子树
代码实现：
int TreeSize2(BTNode* root) { return root == NULL ? 0 : TreeSize2(root->left)
+ TreeSize2(root->right) + 1; }
递归展开图
注意：这里的二叉树和上面的不一样（但是计算方式的大致一样的）
蓝色的数字是递归的次序
红色的数字1，表示返回节点的个数——最后是左子树返回3、右子树返回3、+1，一共是7个节点（可以看出，+1都是递归返回的时候加）
3. 求二叉树叶子节点的个数
思路分析
什么是叶子节点呢 ——> 左右孩子都是空的节点 像上面的二叉树节点个数就是3
怎么控制呢 ——> 1. 二叉树是空树的
2. 二叉树就一个根节点（也就是左右子树为空）
3. 到了第三点，那就直接递归到空，递归到空，就进入第二点，返回1
代码实现
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); }
4. 求二叉树第k层的节点数量
思路分析
方法：转换成最小规模的子问题
思路：求第k层的节点，转换成左子树的第k-1层+右子树的第k-1层
每递归一次，k都会-1，当k=1时，就会返回1（也可以看出k不可能减到0）
注意点1：这里的k不能写成k--的形式，递归左子树的时候就k--的话，会改变k，到递归右子树的时候就会出问题
注意点2：重要的事情说三遍！！！ return是返回函数被调用的地方，不是结束整个递归
代码实现
int TreeKLevel(BTNode* root, int k) { assert(k >= 1); if (root == NULL) return
0; if (k == 1) return 1; return TreeKLevel(root->left, k - 1) +
TreeKLevel(root->right, k - 1); }
递归展开图（部分）
链式二叉树的知识点比较多，小余在这里分成两部分来写，感兴趣的可以等我的下一期哦！！！
如果觉得文章不错，期待你的一键三连哦，你个鼓励是我创作的动力之源，让我们一起加油，顶峰相见！！！