数据结构与算法：树和二叉树的概念详解
数据结构与算法：树和二叉树的概念详解
树和二叉树是数据结构中非常重要的概念，它们在计算机科学的许多领域都有广泛的应用。本文将从树的基本概念开始，逐步深入讲解树的专业名词、表示方法、应用场景，以及二叉树的概念、特殊类型和性质。
树和二叉树的概念讲解
一、树
1.1树的概念
树是一种由n个有限个节点组成的一个具有层次关系的集合，其中n是大于等于0的，并且树同样也是一种非线性的数据结构
我们可以将现实中真实的树的每一个分支和叶子看作一个节点，那么这一个树就可以从根处开始被划分为n个节点并且在不同层级，树的根在下，n个节点在上位列不同层级
在我们学习的数据结构与算法中的树却与上述真实的树是相反的，如下图根在上，n个节点在下位列不同的层级
树的节点只能被一个节点指向，不存在两个及多个节点指向同一个节点的情况，下图是不能构成树的，B节点被A和C指向，在树种不存在这种结构，所以下图的构成树的结构是错误的
1.2树结构的专业名词
- 节点的度。一个节点含有（链接）的子树（第一层级的节点）的个数。例如A下方的链接有B，C，D，E，所以A节点的度为4
- 叶节点或终端节点。度为0的节点称为叶节点。例如F，C，G，E皆为叶节点
- 分支节点或非终端节点。度不为0的节点称为分支节点。例如A，B，D为分支节点
- 父节点或双亲节点。若一个节点具有子节点那么这个节点就为子节点的父节点。例如B节点就为父节点
- 子节点或孩子节点。一个节点含有子树的根节点称为该节点的子节点。例如A节点的子节点有B，C，D，E
- 兄弟节点。具有相同父节点的节点互为兄弟节点。例如B，C的父亲节点都为A，那么B，C互为兄弟节点
- 树的度。在一个树中所有节点的度的最大值称为树的度。例如上述图中的节点的度最大为A的度为4，那么树的度就为4
- 节点的层次。根节点的层次为1，从根节点的那一层开始算，到当前节点的层数为当前节点的层。例如B的层次为2
- 树的高度或深度。树中所有节点的层次的最大层次为树的高度或深度。例如F和G节点的层次最大为3，所以树的高度为3
- 堂兄弟节点。双亲在同一层的节点互为堂兄弟。例如，F和G的双亲节点都在第二层同一层，那么F和G互为堂兄弟节点
- 节点的祖先。从根到该节点路径上所有的节点称为该节点的祖先。例如在F到根A的路径上有B和A，那么F的祖先就为B和A
- 子孙。以某节点为根的子树的任意节点都为该节点的子孙。例如所有节点都为A的子孙
- 森林。由n棵互不相交的树构成的集合称为森林，这里的n大于0
1.3树的表示
对于树的表示小编采用最简单的左孩子右兄弟方法来进行保存，这种建议方式可以存储并表示树中的全部节点
typedef int DataType;
struct Node
{
struct Node* firstchild;//第一个孩子节点
struct Node* childbrother;//第一个孩子节点的下一个兄弟节点
DataType data;//节点中存储的数据
};
1.4树的应用
我们电脑上的文件管理中进行存储的文件就是利用了树的结构进行存储
二、二叉树
2.1二叉树的概念
一颗二叉树是节点的有限集合
- 该集合可能为空
- 该集合由一个根节点加上两颗别称为左子树和右子树的二叉树构成
观察可得
- 二叉树的度不超过2
- 二叉树为有序树，其的子树有左右之分，次序不可以颠倒
2.2特殊的二叉树
- 满二叉树，如果说一个二叉树的每一层的节点数都达到该层的最大值，那么我们就称该树为满二叉树
- 完全二叉树，完全二叉树的最后一层的节点数个有1个或则可以达到该层的最大值，除了最后一层有可能达不到该层的最大值，其余层的节点数必定都达到该层的最大值
- 所以说满二叉树是完全二叉树的一种特殊形式
2.3二叉树的性质
根节点为第一层，第n层的节点的最大值的个数为2^(n-1)个
根节点的层数为1，满二叉树，那么经过计算由第一层到第n层的所有节点的个数的和为2^n-1,即深度为n的的最大节点(满二叉树)个数为2^n-1
对于一颗二叉树，度为0的节点个数n0和度为2的节点个数n2永远满足：n0=n2+1
根的层数为1，那么节点总数为x个节点的满二叉树的层次n即为log2(x+1)
将树的节点按层以0进行开始逐个标号，那么对于下标关系有：父节点可由子节点i求得(i-1)/2，左子节点可由父节点i求得i2+1，右子节点可由父节点求得i2+2
深度为n的完全二叉树个数最小为2^(n-1),个数最大的时候就为满二叉树，此时计算个数与满二叉树的公式相同为2^n-1
节点个数为n的满二叉树和完全二叉树的深度（层数）近似为log2N
总结
以上就是今天的博客内容啦,希望对读者朋友们有帮助
水滴石穿，坚持就是胜利，读者朋友们可以点个关注
点赞收藏加关注，找到小编不迷路！