前言:
普通二叉树的增删查改没有意义?那我们为什么要先学习普通二叉树呢?
给出以下两点理由:
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);
}
递归展开图(部分)
链式二叉树的知识点比较多,小余在这里分成两部分来写,感兴趣的可以等我的下一期哦!!!文章来源:https://www.toymoban.com/news/detail-461087.html
如果觉得文章不错,期待你的一键三连哦,你个鼓励是我创作的动力之源,让我们一起加油,顶峰相见!!!文章来源地址https://www.toymoban.com/news/detail-461087.html
到了这里,关于带你手撕链式二叉树—【C语言】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!