金融门户网站建设,wordpress许愿墙,海淘网站建设,苏宁易购网站建设的目的前言: #x1f4a5;#x1f388;个人主页:Dream_Chaser#xff5e; #x1f388;#x1f4a5; ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--树以及二叉树的概念与结构 目录
一.树概念及结构
1.树的概念
1.1树与非树
树的特点#xff1…前言: 个人主页:Dream_Chaser ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--树以及二叉树的概念与结构 目录
一.树概念及结构
1.树的概念
1.1树与非树
树的特点
非树(图)的特点
1.2 关于树的细致概念
1.3树的表示
1.4树在实际中的运用表示文件系统的目录树结构
二.二叉树概念及结构
1.概念
2.现实中的二叉树 2.3特殊的二叉树
2.4 二叉树的性质
证明性质2和1
习题练习 一.树概念及结构
1.树的概念 树是一种 非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 1.1树与非树 树的特点 空树 -- 结点数为0的树 非空树: 有一个特殊的结点称为根结点根节点没有前驱结点(没有父节点) 下面的两点一起理解: 除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是递归定义的。 可以理解为: 由根节点指向了各子树子树的双亲节点又可以作为根节点指向它们的孩子节点 非树(图)的特点 1.除了根结点外每个结点有且仅有一个父结点; 2.子树是不相交的 以下的这个结构是图(允许相交)不是树 注意树形结构中子树之间不能有交集否则就不是树形结构 3.一棵N个结点的树有N-1条边 1.2 关于树的细致概念 下面有个✅的是比较重要的知识点 ✅节点的度一个节点含有的子树的个数称为该节点的度 如上图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棵互不相交的树的集合称为森林 对各知识点的进一步画图解析:
节点的度:与该节点直接相连的边的数量 叶节点(终端节点)度为0的节点 分支节点(非终端节点):度不为0的节点 父节点(双亲节点)一个节点的直接前驱就是它的父节点 子节点(孩子节点):一个节点的直接后继就是它的子节点 兄弟节点由同一个父节点生出来的都是互为兄弟节点 树的度:一棵树中最大的节点的度称为树的度节点的层次从上往下数从根开始定义起根为第1层根的子节点为第2层以此类推;(默认是从1开始)树的高度(深度)树中节点的最大层次下图的高度就是4 节点的高度从下往上数 堂兄弟节点双亲在同一层的节点互为堂兄弟 节点的祖先指从该节点向上追溯到根节点的路径上的所有节点包括该节点的父节点、父节点的父节点以此类推直到达到根节点为止。 子孙从该节点向下追溯到所有末端节点的路径上的所有节点包括该节点的直接子节点、子节点的子节点以此类推直到达到叶子节点为止。 森林是由多个不相交的树组成的集合(并查集) 1.3树的表示 A 如果明确了树的度那么可以定义。 B、顺序表存储孩子。
C、双亲表示法。(每个位置只存双亲的指针或者下标) D、左孩子右兄弟表示法--简化树结构定义 树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。 我们这里就简单的了解其中最常用的孩子兄弟表示法。 代码实现 typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
}; 画图解析 1.4树在实际中的运用表示文件系统的目录树结构 二.二叉树概念及结构 1.概念 一棵二叉树是结点的一个有限集合该集合: 1. 或者为空 2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成 从上图可以看出 1. 二叉树不存在度大于2的结点(度为0也可以) 2. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 注意对于任意的二叉树都是由以下几种情况复合而成的 2.现实中的二叉树 2.3特殊的二叉树 1. 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是 说如果一个二叉树的层数为K且结点总数是2^k-1 则它就是满二叉树。 2.完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 2.4 二叉树的性质 1、若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点。 2、若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h-1。 3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0 n21 4. 若规定根节点的层数为1具有n个结点的满二叉树的深度hlog2n1). (pslog2n1)是log以2为底n1为对数) 5. 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 1. 若 i0 i 位置节点的双亲序号 (i-1)/2 i0 i 为根节点编号无双亲节点 2. 若 2i1n 左孩子序号 2i1 2i1n 否则无左孩子 3. 若 2i2n 右孩子序号 2i2 2i2n 否则无右孩子 证明性质2和1
如何证明性质2和性质1以下是证明过程 习题练习 1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 B A 不存在这样的二叉树 B 200 C 198 D 199 解析 2.下列数据结构中不适合采用顺序存储结构的是 A A 非完全二叉树 B 堆 C 队列 D 栈 解析 顺序存储结构适合于具有连续存储空间的数据结构其中元素按照线性顺序存储。 对于非完全二叉树由于其结构不规则无法通过连续的存储空间来表示。因此非完全二叉树不适合采用顺序存储结构。 B. 堆、C. 队列、D. 栈都可以通过顺序存储结构有效地实现。堆是一种完全二叉树可以使用数组来表示。队列和栈可以使用数组或者链表来表示都适合顺序存储结构。 3.在具有 2n 个结点的完全二叉树中叶子结点个数为A A n B n1 C n-1 D n/2 和节点个数相关的公式有二 n0 n2 1N n0 n1 n2 已知总个数N为2n那么只要知道n1即可求出n0. 这里有一个重要的结论 在完全二叉树中如果节点总个数为奇数则没有度为1的节点如果节点总个数为偶数只有一个度为1的节点。 节点个数是偶数只有一个度为1的节点 节点个数是奇数没有度为1的节点 2n为偶数因此有一个度为1的节点。 2n n0 1 n2 n0 1 n0 - 1 2n 2n0 n0 n故选A 4.一棵完全二叉树的节点数位为531个那么这棵树的高度为 B A 11 B 10 C 8 D 12 解析 根据性质4hlog2n1)n531h log2(532),找一个最接近的数就是log2(512)也就是log2(2^9)向上取整n10 5.一个具有767个节点的完全二叉树其叶子节点个数为B A 383 B 384 C 385 D 386 解析 N767个节点数是奇数个所以N n0 n2(奇数个没有度为1的节点) 由n0 n21; N 2n0 - 1 那么n0 (N 1) / 2 384 本篇完如有错误欢迎指正感谢来访
