上海珍岛网站建设,哪些网站可以做养殖的广告,云平台网站建设方案,物联网应用技术学什么#x1f407; #x1f525;博客主页#xff1a; 云曦 #x1f4cb;系列专栏#xff1a;数据结构 #x1f4a8;吾生也有涯#xff0c;而知也无涯 #x1f49b; 感谢大家#x1f44d;点赞 #x1f60b;关注#x1f4dd;评论 文章目录 前言一、树的概念及结构#x… 博客主页 云曦 系列专栏数据结构 吾生也有涯而知也无涯 感谢大家点赞 关注评论 文章目录 前言一、树的概念及结构1.1 树的概念1.4 树和非树1.3 树的表示1.4 树在实际中的运用 二、二叉树的概念及结构2.1 二叉树的概念2.2 现实中的二叉树2.3 特殊的二叉树2.4 二叉树的性质2.5 二叉树的存储结构☘️2.5.1 顺序存储☘️2.5.2 链式存储 三、二叉树链式结构及实现3.1 二叉树的遍历☘️3.1.1 二叉树前序、中序、后序遍历的规则☘️3.1.2 前序遍历☘️3.1.3 中序遍历☘️3.1.4 后序遍历☘️3.1.5 层序遍历 3.2 二叉树节点个数的统计☘️3.2.1 节点的个数☘️3.2.2 叶子节点的个数 3.3 二叉树的创建和销毁☘️3.3.2二叉树的创建☘️3.3.2 二叉树的销毁 3.3 二叉树接口测试 四、完整代码font colorRed**4.1 BinaryTree.h**font colorRed**4.2 BinaryTree.c**font colorRed**4.3 test.c** 前言 在上期讲解完栈和队列的实现后本期迎来了新的知识名为二叉树希望大家能坚持的学习下去。 一、树的概念及结构
1.1 树的概念 树跟之前所学的顺序表、链表等不相同树是一种非线性 的数据结构它由n(n0)个有序节点组成一个具有层次关系的集合。把它叫作树是因为它看起来像一颗倒挂的树也就是根朝上而叶子朝下。 有一个特殊的节点称作根节点根节点没有前驱节点。除根节点外其余结点被分成M(M0)个互不相交的集T1T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是由递归定义的 树的相关概念 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点树的度一棵树中最大的节点的度称为树的度 如上图树的度为6节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推树的高度或深度树中节点的最大层次 如上图树的高度为4堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙森林由mm0棵互不相交的树的集合称为森林 1.4 树和非树 注意树形结构中子树之间是没有交集的否则就不是树形结构了。 1.3 树的表示 孩子兄弟表示法 typedef int DataType;typedef struct TreeNode
{struct TreeNode* firstchild;//第一个孩子节点struct TreeNode* nextbrother;//指向下一个兄弟节点DataType data;//节点的数据域
}TNode;1.4 树在实际中的运用 用于表示文件系统的目录数结构 二、二叉树的概念及结构
2.1 二叉树的概念 每一颗二叉树是节点的一个有序的集合该集合的特点是 由一个根和左子树、右子树的组成的二叉树。该树也有可能为空。 从上图可以看出 二叉树不存在大于2的节点。二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树。 注意对于任何一颗二叉树都有可能由以下几种复合而成的 2.2 现实中的二叉树 2.3 特殊的二叉树 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是 则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 2.4 二叉树的性质 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有 个结点.若规定根节点的层数为1则深度为h的二叉树的最大结点数是 .对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有 1若规定根节点的层数为1具有n个结点的满二叉树的深度h . (ps 是log以2为底n1为对数)对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点若2i1n左孩子序号2i12i1n否则无左孩子若2i2n右孩子序号2i22i2n否则无右孩子 2.5 二叉树的存储结构
☘️2.5.1 顺序存储 顺序结果存储就是用数组来存储的一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而在使用时只有堆才会用数组来存储所以本期暂时不讲解顺序存储。 ☘️2.5.2 链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们使用的都是二叉链三叉链会在讲解红黑树时使用。 typedef char BTDataType;
//二叉链
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;//指向当前节点左孩子struct BinaryTreeNode* right;//指向当前节点右孩子BTDataType data;//当前节点值域
}BTNode;//三叉链
typedef struct BinaryTreeNode
{struct BinaryTreeNode* parents;//指向当前节点的双亲struct BinaryTreeNode* left;//指向当前节点左孩子struct BinaryTreeNode* right;//指向当前节点右孩子BTDataType data;//当前节点值域
}BTNode;三、二叉树链式结构及实现 结构的创建 typedef char BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;//左子树struct BinaryTreeNode* right;//右子树BTDataType data;//节点的数据域
}BTNode;3.1 二叉树的遍历 学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。 ☘️3.1.1 二叉树前序、中序、后序遍历的规则 前序遍历先访问根节点其次是左子树最后是右子树(根 - 左子树 - 右子树)中序遍历先访问左子树其次是根最后是右子树(左子树 - 根 - 右子树)后序遍历先访问左子树其次是右子树最后是根(左子树 - 右子树 - 根)举例 由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 // 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);☘️3.1.2 前序遍历
//二叉树前序遍历
void PrevOrder(BTNode* root)
{//根为空就返回if (root NULL){printf(NULL );return;}//根 - 左子树 - 右子树printf(%c , root-data);//打印根PrevOrder(root-left);//递归左子树PrevOrder(root-right);//递归右子树
}☘️3.1.3 中序遍历
//二叉树中序遍历
void InOrder(BTNode* root)
{//根为空就返回if (root NULL){printf(NULL );return;}//左子树 - 根 - 右子树InOrder(root-left);//递归左子树printf(%c , root-data);//打印根InOrder(root-right);//递归右子树
}☘️3.1.4 后序遍历
void PostOrder(BTNode* root)
{//根为空就返回if (root NULL){printf(NULL );return;}//左子树 - 右子树 - 根PostOrder(root-left);//递归左子树PostOrder(root-right);//递归右子树printf(%c , root-data);//打印根
}☘️3.1.5 层序遍历 前序中序后序其实也叫深度优先遍历而层序遍历也叫作广度优先遍历层序的核心思路就是上层取出的时候带下一层进层序遍历需要用到队列来实现而在C语言中没有队列的库那么还要实现一个队列。但其实不需要实现因为上一起已经实现过了我们直接将源文件和头文件复制粘贴到实现二叉树的目录下即可。(实现栈和队列的链接)实现思路 注意引用队列的源文件和头文件后要在队列的头文件里声明树的结构体然后将队列结构data的类型改为树的结构体指针类型 且在二叉树的头文件里声明队列的头文件时要在树的结构体后面声明因为在编译是头文件是张开向上找结构体的。 void LevelOrder(BTNode* root)
{//创建及初始化队列Que q;QueueInit(q);//空树就不需要入队列了//不是空树就把根节点入队列if (root){QueuePush(q, root);}while (!QueueEmpty(q)){//根节点出队列BTNode* front QueueFront(q);QueuePop(q);printf(%c , front-data);//左子树入队列if (front-left){QueuePush(q, front-left);}//右子树入队列if (front-right){QueuePush(q, front-right);}}printf(\n);QueueDestroy(q);
}3.2 二叉树节点个数的统计
☘️3.2.1 节点的个数
int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}看递归很绕的时候教大家一个方法画递归展开图 ☘️3.2.2 叶子节点的个数
int LeafSize(BTNode* root)
{//根为空就返回0if (root NULL){return 0;}//左右子树为空则返回1if (root-left NULL root-right NULL){return 1;}//递归左子树的叶子个数加递归右子树的叶子个数return LeafSize(root-left) LeafSize(root-right);
}相当于节点个数功能的思路延伸根为空返回0左子树与右子树都为空返回1最后递归左右子树相加就得到了叶子节点的个数。 3.3 二叉树的创建和销毁
☘️3.3.2二叉树的创建 二叉树的创建思路是通过前序遍历的数组ABD##E##C##构建二叉树只有前序是不可能构建出二叉树的但是在数组里用’#表示NULL这样构建二叉树就很容易了。 BTNode* BinaryTreeCreate(BTDataType* s, int* pi)
{//遇到#,加加pi然后返回NULLif (s[*pi] #){(*pi);return NULL;}//malloc出来新的根节点BTNode* root (BTNode*)malloc(sizeof(BTNode));if (root NULL){perror(malloc fail);exit(-1);}root-data s[*pi];(*pi);//递归构建左子树root-left BinaryTreeCreate(s, pi);//递归构建右子树root-right BinaryTreeCreate(s, pi);return root;
}☘️3.3.2 二叉树的销毁 销毁的含义依然是把空间还给操作系统。 销毁二叉树很简单用后序遍历的思路把打印数据改成free(释放)节点即可。 //思路就是使用后序遍历思路销毁
void TreeDestroy(BTNode* root)
{//根为空时直接返回if (root NULL){return;}TreeDestroy(root-left);//递归左子树TreeDestroy(root-right);//递归右子树free(root);//释放根节点root NULL;
}3.3 二叉树接口测试
int main()
{//构建树char str[] ABD##E##C##;int i 0;BTNode* root BinaryTreeCreate(str, i);//测试功能PrevOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);printf(\n);int ATree TreeSize(root);printf(%d\n, ATree);//5int BTree TreeSize(root-left);printf(%d\n, BTree);//3int ALeaf LeafSize(root);printf(%d\n, ALeaf);//3LevelOrder(root);//A B C D ETreeDestroy(root);return 0;
}四、完整代码
4.1 BinaryTree.h
#pragma once#includestdio.h
#includestdlib.h//二叉树
typedef char BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;//左子树struct BinaryTreeNode* right;//右子树BTDataType data;//当前节点值域
}BTNode;#include Queue.h//二叉树前序遍历
void PrevOrder(BTNode* root);
//二叉树中序遍历
void InOrder(BTNode* root);
//二叉树后序遍历
void PostOrder(BTNode* root);
//二叉树的层次
//核心思路上层取出的时候带下一层进
void LevelOrder(BTNode* root);
//二叉树节点的个数
int TreeSize(BTNode* root);
//二叉树叶子的个数
int LeafSize(BTNode* root);
//二叉树的销毁
void TreeDestroy(BTNode* root);
//通过前序遍历的数组ABD##E##C##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* s, int* pi);
4.2 BinaryTree.c
#include BinaryTree.hvoid PrevOrder(BTNode* root)
{//根为空就返回if (root NULL){printf(NULL );return;}//根 - 左子树 - 右子树printf(%c , root-data);//打印根PrevOrder(root-left);//递归左子树PrevOrder(root-right);//递归右子树
}void InOrder(BTNode* root)
{//根为空就返回if (root NULL){printf(NULL );return;}//左子树 - 根 - 右子树InOrder(root-left);//递归左子树printf(%c , root-data);//打印根InOrder(root-right);//递归右子树
}void PostOrder(BTNode* root)
{//根为空就返回if (root NULL){printf(NULL );return;}//左子树 - 右子树 - 根PostOrder(root-left);//递归左子树PostOrder(root-right);//递归右子树printf(%c , root-data);//打印根
}int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}int LeafSize(BTNode* root)
{//根为空就返回0if (root NULL){return 0;}//左右子树为空则返回1if (root-left NULL root-right NULL){return 1;}//递归左子树的叶子个数加递归右子树的叶子个数return LeafSize(root-left) LeafSize(root-right);
}//核心思路上层取出的时候带下一层进
void LevelOrder(BTNode* root)
{//创建及初始化队列Que q;QueueInit(q);//空树就不需要入队列了//不是空树就把根节点入队列if (root){QueuePush(q, root);}while (!QueueEmpty(q)){//根节点出队列BTNode* front QueueFront(q);QueuePop(q);printf(%c , front-data);//左子树入队列if (front-left){QueuePush(q, front-left);}//右子树入队列if (front-right){QueuePush(q, front-right);}}printf(\n);QueueDestroy(q);
}//思路就是使用后序遍历思路销毁
void TreeDestroy(BTNode* root)
{//根为空时直接返回if (root NULL){return;}TreeDestroy(root-left);//递归左子树TreeDestroy(root-right);//递归右子树free(root);//释放根节点root NULL;
}BTNode* BinaryTreeCreate(BTDataType* s, int* pi)
{//遇到#,加加pi然后返回NULLif (s[*pi] #){(*pi);return NULL;}//malloc出来新的根节点BTNode* root (BTNode*)malloc(sizeof(BTNode));if (root NULL){perror(malloc fail);exit(-1);}root-data s[*pi];(*pi);//递归构建左子树root-left BinaryTreeCreate(s, pi);//递归构建右子树root-right BinaryTreeCreate(s, pi);return root;
}4.3 test.c
#include BinaryTree.hint main()
{//构建树char str[] ABD##E##C##;int i 0;BTNode* root BinaryTreeCreate(str, i);//测试功能PrevOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);printf(\n);int ATree TreeSize(root);printf(%d\n, ATree);//5int BTree TreeSize(root-left);printf(%d\n, BTree);//3int ALeaf LeafSize(root);printf(%d\n, ALeaf);//3LevelOrder(root);TreeDestroy(root);return 0;
}
