前言:

普通二叉树的增删查改没有意义?那我们为什么要先学习普通二叉树呢?

给出以下两点理由:

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); }

递归展开图(部分)

   链式二叉树的知识点比较多,小余在这里分成两部分来写,感兴趣的可以等我的下一期哦!!!

如果觉得文章不错,期待你的一键三连哦,你个鼓励是我创作的动力之源,让我们一起加油,顶峰相见!!!

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信