网站前端怎么做方法,做网站比较好的公司有哪些,扬中网站推广,商城app开发费用多少钱前言
Hello,小伙伴们。你们的作者菌又回来了#xff0c;前些时间我们刚学习完二叉树的顺序结构#xff0c;今天我们就趁热打铁#xff0c;继续我们二叉树链式结构的学习。我们上期有提到#xff0c;二叉树的的底层结构可以选为数组和链表#xff0c;顺序结构我们选用的数…前言
Hello,小伙伴们。你们的作者菌又回来了前些时间我们刚学习完二叉树的顺序结构今天我们就趁热打铁继续我们二叉树链式结构的学习。我们上期有提到二叉树的的底层结构可以选为数组和链表顺序结构我们选用的数组那我们就不难知道二叉树的链式结构采用链表为底层结构。 1.实现链式二叉树
用链表来表示一颗二叉树即用链表来表示元素之间的逻辑关系。通常的方法就是链表中的每一个节点有三个域组成数据域和左右指针左右指针分别用来给出该节点左右孩子所在的链接点的存储地址数据结构的定义如下
typedef int BTDataType;
// ⼆叉链
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left; // 指向当前结点左孩⼦
struct BinaryTreeNode* right; // 指向当前结点右孩⼦
BTDataType val; // 当前结点值域
}BTNode;
不要忘记我们在实现数据结构时都要先创建三个文件来使测试代码变得更加的方便
为了更好的演示效果我们就在Test.c文件中手动的创建几个节点
BTNode* BuyBTNode(int val)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);return NULL;} newnode-val val;newnode-left NULL;newnode-right NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* n1 BuyBTNode(1);BTNode* n2 BuyBTNode(2);BTNode* n3 BuyBTNode(3);BTNode* n4 BuyBTNode(4);BTNode* n5 BuyBTNode(5);BTNode* n6 BuyBTNode(6);BTNode* n7 BuyBTNode(7);n1-left n2;n1-right n4;n2-left n3;n4-left n5;n4-right n6;n5-left n7;return n1;}int main()
{BTNode* boot CreateTree();return 0;
}
我们已经学习了链表所以这里创建节点的操作我们就不再过多的赘述因此boot就是我们创建的这颗树的根节点。
接下来我们来回顾一下二叉树的概念二叉树分为空树和非空树 根节点的左子树和右子树分别有是有子树节点、子树节点的左子树和右子树组成因此二叉树定义是递归式的后续链式二叉树的操作中基本都是按照该概念实现的
1.1前中后序遍历
二叉树的操作离不开树的遍历我们先来看看二叉树的遍历有哪些方式 1.1.1遍历的规则
按照规则二叉树有前中后续遍历的规则的递归结构遍历
前序遍历访问根节点的操作发生在遍历其左右子树之前。
访问顺序根节点、左子树、右子树。
中序遍历访问根节点的操作发生在遍历其左右节点子树之间间
访问顺序左子树、根节点、右子树
后序遍历访问根节点的操作发生在遍历其左右子树的遍历之后
访问顺序左子树、右子树、根节点
1.1.2 代码的实现
1.1.2.1 前序遍历PreOrder
void PreOrder(BTNode* root)
{
if (root NULL)
{
printf(N );
return;
} p
rintf(%d , root-val);
PreOrder(root-left);
PreOrder(root-right);
}
这里我们就涉及到了之前学习函数栈帧的知识我们可以通过图来理解 函数递归栈帧图 最终我们测试可得 可知这符合我们前序遍历的规则因此我们就成功实现了前序遍历。
实现了前序遍历其他的两个遍历就简单了几乎和前序遍历一样中后序遍历也沿用了递归的思想
后面大家能否根据上面前序遍历的代码实现中序遍历和后序遍历呢
大家不妨一试。
1.1.2.2中序遍历InOrder
void InOrder(BTNode* root)
{
if (root NULL)
{
printf(N );
return;
}
InOrder(root-left);
printf(%d , root-val);
InOrder(root-right);
} 1.1.2.3后序遍历PostOredr
v
oid PostOrder(BTNode* root)
{
if (root NULL)
{
printf(N );
return;
} I
nOrder(root-left);
InOrder(root-right);
printf(%d , root-val);
} 有序他们之间的相似性在代码上的差异也就只是不同行的代码顺序不一样但是转化为后面的函数栈帧却又不小的差别。但在本质上却还是大差不差
1.2节点个数以及高度等
1.2.1节点计数
// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);
我们来想一想怎样才能达到我们的目的呢
假设我们现在有这样的二叉树 所以从上所述我们就能够得出计数代码
int BinaryNodeCount(BTNode* root)
{if (root NULL)return 0;return 1 BinaryNodeCount(root-left) BinaryNodeCount(root-right);} 代码测试
这里我们创建的是这样的二叉树。 可知这样我们就实现了二叉树节点的计数 1.2.2二叉树叶子结点个数
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode*root)
有了前面写求所有节点个数的经验其实这个不就不难了
叶子结点就是没有子节点的节点。即root-left root-right NULL.
所以在这里我们就有两种返回情况当遍历到NULL时我们返回0 当递归到叶子结点时我们就返回1。借助函数栈帧就可以进行计数
接下来我们来实现一下这个代码
//求二叉树叶子节点的个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
}
我们可以先提前看看这颗二叉树有多少个叶子结点 上面我们可以看出一共有3个没有子节点的节点所以叶子结点的个数就是3 1.2.3 二叉树第K层的节点个数
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
我们要得到二叉树第K层节点的个数其实也并不难我们还是通过画图的方式来解析过程。
假设我们要求的是第三层的节点数 代码实现
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root NULL){return 0;}if (k 1)return 1;return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}
测试一下 1.2.4二叉树的深度/高度
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);
在这里我们可以想出怎样的思路呢
我们还是要先画图求证
int BinaryTreeDepth(BTNode* root)
{if (root NULL)return 0;int leftDepth BinaryTreeDepth(root-left);int rightDepth BinaryTreeDepth(root-right);return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;
} 代码测试 从上面我们事先创建的那棵树一样树的深度为4.所以我们实现了我们的目的。
1.2.5二叉树查找置位x的节点
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
这个操作也十分的简单我们只需要遍历二叉树找到与目标值相等的节点我们就将其返回。
我们先看看实现代码
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-val x)return root;BTNode* left BinaryTreeFind(root-left, x);if (left)return left;BTNode* right BinaryTreeFind(root-right, x);if (right)return right;return NULL;
}
在这里我们还是要进行二叉树的左右子树遍历但是我们为了提高效率只要在一边找到了符合目标的节点我们就直接返回该节点
小伙伴们可以根据上面的知识自行画出递归栈帧图。
我们来测试以下代码 可知其成功的找到了值为6的节点
1.2.6 二叉树的销毁
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);
销毁的逻辑也十分的简单了通过了递归的操作我们遍历所有不为NULL的节点并销毁这里我们就直接写出代码大家可以自己进行递归栈帧的推理
void BinaryTreeDestory(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);*root NULL;
}
代码测试 进行销毁操作 2.代码展示
2.1Test.c
#define _CRT_SECURE_NO_WARNINGS 1#includeTree.h
BTNode* BuyBTNode(int val)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);return NULL;} newnode-val val;newnode-left NULL;newnode-right NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* n1 BuyBTNode(1);BTNode* n2 BuyBTNode(2);BTNode* n3 BuyBTNode(3);BTNode* n4 BuyBTNode(4);BTNode* n5 BuyBTNode(5);BTNode* n6 BuyBTNode(6);BTNode* n7 BuyBTNode(7);n1-left n2;n1-right n4;n2-left n3;n4-left n5;n4-right n6;n5-left n7;return n1;}int main()
{BTNode* root CreateTree();PreOrder(root);printf(\n);InOredr(root);printf(\n);PostOrder( root);printf(\n);printf(TreeNodeCount: %d\n, BinaryNodeCount(root));printf(leafSize: %d\n, BinaryTreeLeafSize(root));printf(TreeLevelKSize: %d\n, BinaryTreeLevelKSize(root, 3));printf(TreeLevelDepth: %d\n, BinaryTreeDepth(root));BTNode* find BinaryTreeFind(root, 6);printf(%s , find NULL ? 没找到 : 找到了);printf(返回节点的值为%d\n, find-val);BinaryTreeDestory(root);PostOrder(root);return 0;
}2.2Tree.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includetime.h
#includestdbool.h
typedef int BTDataType;
// ⼆叉链
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left; // 指向当前结点左孩⼦struct BinaryTreeNode* right; // 指向当前结点右孩⼦BTDataType val; // 当前结点值域
}BTNode;
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOredr(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//计数二叉树的节点
int BinaryNodeCount(BTNode* root);
//求二叉树叶子节点的个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);
2.3Tree.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeTree.h
void PreOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}
void InOredr(BTNode* root)
{if (root NULL)return;InOredr(root-left);printf(%d , root-val);InOredr(root-right);
}
void PostOrder(BTNode* root)
{if (root NULL){return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}
int BinaryNodeCount(BTNode* root)
{if (root NULL)return 0;return 1 BinaryNodeCount(root-left) BinaryNodeCount(root-right);}
//求二叉树叶子节点的个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
}
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root NULL){return 0;}if (k 1)return 1;return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}
int BinaryTreeDepth(BTNode* root)
{if (root NULL)return 0;int leftDepth BinaryTreeDepth(root-left);int rightDepth BinaryTreeDepth(root-right);return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;
}
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-val x)return root;BTNode* left BinaryTreeFind(root-left, x);if (left)return left;BTNode* right BinaryTreeFind(root-right, x);if (right)return right;return NULL;
}
void BinaryTreeDestory(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);*root NULL;
}
好今天的学习就到这里我们下期再见拜拜
