郑州的做网站公司有哪些,营销型网站建设多少钱,绛县做网站,搏彩网站开发建设1.树的概念和结构
树#xff0c;顾名思义#xff0c;它看起来像一棵树#xff0c;是由n个结点组成的非线性的数据结构。 下面就是一颗树#xff1a; 树的一些基本概念#xff1a;
结点的度#xff1a;一个结点含有的子树的个数称为该结点的度#xff1b; 如上图#…1.树的概念和结构
树顾名思义它看起来像一棵树是由n个结点组成的非线性的数据结构。 下面就是一颗树 树的一些基本概念
结点的度一个结点含有的子树的个数称为该结点的度 如上图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棵互不相交的树的集合称为森林
2.树的表示
树的表示比线性表复杂它不仅要存储数据还要存储和其他结点的关系。
树有很多的表示方法下面是最为常见的一种孩子兄弟表示法
typedef int DataType;
struct Node
{
struct Node* firstChild1; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
如图每一个结点都有自己孩子结点和兄弟结点如果没有就存NULL这样就可以表示每一个结点了。 3.二叉树的概念和结构
先看下面图 每一个树干都有两个树枝这就是我们生活中的二叉树而数据结构中的二叉树有两种常见又特殊的
完全二叉树 满二叉树 4.二叉树的存储
二叉树的存储有顺序存储和链式存储
顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树 链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链
二叉链
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}
三叉链
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* parent; // 指向当前结点的双亲
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}
普通二叉树一般不用顺序结构存储因为会有空间的浪费只要完全二叉树才适合顺序存储也就是堆 5.堆的概念和结构
堆是一种完全二叉树堆又分为大堆和小堆。
大堆每一个父结点都比它的子结点大 小堆每一个父结点都比子结点小
