太原微信网站开发,谷歌外贸平台有哪些,怎么做微信上的网站吗,广州 骏域网站建设在探索栈和队列之后#xff08;大家可以移步至我的数据结构专栏#xff09;#xff1a;T-rLN的数据结构专栏
我们转向了更为复杂而有趣的数据结构——二叉树。本文将引领我们进入二叉树的世界#xff0c;从最基本的概念和结构开始#xff0c;逐步深入了解二叉树的顺序结构…在探索栈和队列之后大家可以移步至我的数据结构专栏T-rLN的数据结构专栏
我们转向了更为复杂而有趣的数据结构——二叉树。本文将引领我们进入二叉树的世界从最基本的概念和结构开始逐步深入了解二叉树的顺序结构和链式结构 文章目录 1.树概念和结构1.1树的概念1.2树的相关概念1.3树的表示1.4树的实际应用 2.二叉树概念和结构2.1二叉树的概念2.2两种特殊二叉树2.3二叉树的性质2.5二叉树的储存结构 1.树概念和结构
1.1树的概念 树是一种抽象数据类型ADT非线性的数据结构它由节点组成的集合构成节点间通过边连接。 它的命名灵感来源于现实生活中的树木结构。类似于自然界中树木的结构树这一数据结构的视觉表示也呈现出分支延伸的形态由根部向外延伸出分支这种分支的结构特点赋予了数据结构树这一名称一个倒挂的树 树中有一个特殊的节点称为根节点它位于树的顶部没有父节点前驱节点树中除根节点外其他节点都被分成了若干个互不相交的集合每个集合又形成了一棵类似于树的子树。这里的每个子树都类似于整体的树结构它们都有一个根节点这个根节点在当前子树中有且只有一个前驱节点即父节点但可以有零个或多个后继节点子节点这种定义描述了树这种数据结构的递归性质 但是要注意树形结构中子树之间不能有交集否则就不是树形结构 这些都不是树。 树的要求 子树不能相交除了根节点以外其余节点只有一个父节点一个有哦X个节点的树边的数量是X-1梦回离散数学 1.2树的相关概念 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为4 叶节点或终端节点度为0的节点称为叶节点 如上图B、D、H、I…等节点为叶节点 非终端节点/分支节点度不为0的节点 如上图C、E、G…等节点为分支节点 双亲节点/父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点 孩子节点/子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为4 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推(也有把跟视为第0层的) 树的高度或深度树中节点的最大层次 如上图树的高度为4 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林多棵互不相交的树的集合称为森林 1.3树的表示 树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值也要保存结点和结点之间的关系。实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等 双亲表示法在每个节点中存储一个指向其父节点的指针或索引 typedef struct {int data; // 节点数据PTNode* parent; // 指向父节点的指针或索引
} PTNode;typedef struct {PTNode* nodes; // 存储所有节点的数组要动态的int n; // 树中当前节点数
} PTree;孩子表示法每个节点保存一个指向其第一个子节点的指针孩子兄弟表示法也叫作左孩子右兄弟表示法每个节点有指向其第一个孩子的指针和指向其右兄弟的指针 typedef struct CSNode {int data; // 节点数据struct CSNode* firstChild; // 指向第一个子节点的指针struct CSNode* nextSibling; // 指向右兄弟节点的指针
} CSNode;1.4树的实际应用 在 Linux 文件系统中树形结构是文件和目录组织的基础。文件系统以树的形式组织文件和目录根目录是整个文件系统的顶层所有的文件和目录都从根目录开始分支。每个目录包括根目录都可以包含文件和其他目录 2.二叉树概念和结构
2.1二叉树的概念 二叉树是一种重要的树形数据结构它由节点构成每个节点最多有两个子节点(不是必须两个)分别称为左子节点和右子节点。这两个子节点通常称为左子树和右子树 从上图可看出 二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 2.2两种特殊二叉树 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。换句话说在满二叉树中每个节点都有两个子节点完全二叉树是一种特殊的二叉树在一棵二叉树中如果除了最底层其他层的节点都是满的并且最底层的节点都从左至右依次填满这样的树被称为完全二叉树 满二叉树是一种特殊的完全二叉树 2.3二叉树的性质 若规定根节点的层数为1则一棵非空二叉树的第n层上最多有 2 n − 1 2^{n-1} 2n−1个结点(第一层 2 0 2^0 20第二层 2 1 2^1 21);若规定根节点的层数为1则**深度为h的二叉树的最大结点数节点总数**是 2 h − 1 2^h-1 2h−1 第一层根节点层有 1 个节点。第二层有最多 2 个节点。第三层有最多 4 个节点。…第 ℎ 层有最多 2 h − 1 2^{h-1} 2h−1个节点。 所以前 ℎh 层的节点数之和为 124… 2 h − 1 2^{h-1} 2h−1 2 h − 1 2^{h}-1 2h−1 若规定根节点的层数为1具有n个结点的满二叉树的深度(h): l o g 2 ( n 1 ) log_2(n1) log2(n1) 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 若i0i位置节点的双亲序号(i-1)/2 i0i为根节点编号无双亲节点若2i1n,则左孩子坐标2i12i1n否则无左孩子若2i2n右孩子序号2i22i2n否则无右孩子 2.5二叉树的储存结构
顺序储存数组顺序结构存储就是使用数组来存储一般数组只适合表示完全二叉树因为不是完全二叉树空间的浪费比较大。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组在逻辑上把它想象成把它看作是是一颗二叉树链式储存链表二叉树的链式存储结构是指用链表来表示一棵二叉树。通常的方法是链表中每个结点由三个域组成数据域、左指针域和右指针域。左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址数据域就存储数据 这次就到这里啦下一次大概率是二叉树的顺序结构和堆的相关内容感谢大家的支持
