网站备案icp备案,wordpress 播放器右键,网站域名 空间,南通模板网建站谈到二叉树#xff0c;先来谈谈树的概念。
1、树的概念及结构 树是一种非线性的数据结构#xff0c;它的逻辑关系看起来像是一棵倒着的树#xff0c;也就是说它是根在上#xff0c;而叶子在下的#xff0c; 在树这种数据结构中#xff0c;最顶端的结点称为根结点。在树的… 谈到二叉树先来谈谈树的概念。
1、树的概念及结构 树是一种非线性的数据结构它的逻辑关系看起来像是一棵倒着的树也就是说它是根在上而叶子在下的 在树这种数据结构中最顶端的结点称为根结点。在树的使用过程中由于树的逻辑关系很像人的遗传关系图谱所以一般将上一级的结点称为下一级结点的父结点某一层级结点往上的结点称为该层结点的祖先。这里要注意的一点是树形结构中子树之间不能有交集否则就不是树形结构。
1.1、树的相关概念 结点的度 一个结点含有的子树的个数就称为该结点的度如上图A的度为6
叶结点度为0的结点称为叶结点 如上图B、C、H、I...等结点为叶结点
分支结点度不为0的结点称为分支结点 如上图D、E、F、G...等结点为分支结点
父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点
子结点若有一个结点有父结点则这个结点称为其父结点的子节点如上图B是A的子结点
兄弟结点处于同一层级的结点称为兄弟节点
树的度一棵树中最大结点的度称为树的度如上图树的度为6
结点的层次从根开始定义根为第1层根的子结点为第2层以此类推
树的高度树中结点的最大层次如上图树的高度为4
堂兄弟结点双亲结点在同一层级的结点称为堂兄弟结点如上图H、I互为堂兄弟结点
结点的祖先 从根到该结点所经分支上的所有结点如上图A是所有结点的祖先
子孙 以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙
森林由mm0棵互不相交的树的集合称为森林
1.2、树的表示 树的表示就比较复杂了既要保存结点中要存储的数据也要保存结点之间的相互关系。众多树的表示方法中左孩子右兄弟表示法是最常用的方法。它的逻辑关系可以表示成下面的形式 typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};
2、二叉树
2.1、概念 一棵二叉树是结点的有限集合该集合1.或者为空2.由一个根节点加上两颗别称为左子树和右子树的二叉树组成 从上图可以看出 1.二叉树不存在度大于2的结点 2.二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树。
对于任意的二叉树都是由以下几种情况符合而成的 2.2、特殊的二叉树 1、满二叉树一个二叉树如果每一层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为h且结点数总是2^(h-1)那么它就是满二叉树。 2、完全二叉树完全二叉树是效率很高的数据结构对于高度为h的二叉树它的h-1层的结点全满第h层的结点是连续的情况下称为完全二叉树。要注意满二叉树也是一种特殊的完全二叉树。 2.3、二叉树的性质
1、若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
2、若规定根节点的层数为1则深度为h的二叉树的最大结点树最大的结点数为2^h-1。
3、对于任何一颗二叉树如果度为0其结点个数为n0度为2的分支结点个数为n2,则有n0n21。
4、若规定根结点的层数为1具有n个节点的满二叉树的深度hlog(n1),以2为底。
5、对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组对所有结点从0开始编号则对于序号为i的结点有 若i0i位置结点的双亲序号(i-1)/2i0i为根结点编号无双亲结点 若2i1n左孩子序号2i12i1n否则无左孩子 若2i2n右孩子序号2i22i2n否则无右孩子 3、二叉树的顺序结构及实现
3.1、二叉树的顺序结构 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 3.2、堆 在二叉树的概念上限制一些条件就是堆。堆有两条性质1.堆中某个结点的值总是大于或者不小于其父结点的值。2.堆总是一棵完全二叉树。 堆的实现我将单独写一篇博客来实现。
