树的介绍&树的节点计算公式(跑路人笔记)

文章目录

舒文未来目标: 进大厂啊进大厂~🤪.让我家人放松一些,努力让生活更棒,好耶!
舒文现状:大一菜鸡,从食品转码,目前已经结识了很多学习的朋友.(挺棒的👍)
博客目的:写博客是为了记录自己的学习路径.也是为了让面试官眼前一亮,然后就是装逼.
小小推荐: 我在CSDN和朋友创建管理了一个社区大家如果感兴趣的话可以来看看👉非科班转码社区.👈
现阶段目标: 好好学习基础知识多多了解计算机行业情况.保持良好的身体素质,多多交朋友,多多犯错多多从错误中学习😍.
之前的博客是整理了两道关于队列和栈的题目:👉设计循环队列(c实现)(链表和顺序表版)👈.

前言

这篇主要讲解树的知识点,没有代码实现但是知识点较多,我会尽量细的向大家讲解.毕竟这也是俺的笔记.
最近朋友越来越卷了,我也要抓紧跟上,不然清明节就是给我过了,呜呜呜呜呜.

正文

树的基础概念

树一种非线性的数据结构,它是由n(n>=0)个有限节点组成的具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个节点是根节点,根节点是所有节点的唯一交点,及上图的A节点,根节点的分支是类似于根节点结构的子树
• 子树的结构一定是和树的结构类似的子树有且只有一个根
• 树的问题可以分为总问题和多个子问题所有树是通过递归定义的
• 树的之间是不能有交集的如果有交集就不能叫做树如下图p和I有交集就不可以叫做这个为树 因为上个特性所有我们的树在有N个节点的情况下也有着N-1个边(边就是连接两个节点的线😁). 除了根节点外每个节点有且只有一个父节点.

树的相关性质

节点的度：一个节点含有的子树的个数称为该节点的度； 如下图：A的为6

叶节点或终端节点：度为0的节点称为叶节点； 如下图：B、C、H、I…等节点为叶节点,及下面无连接节点的节点.

非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点,这个和叶子节点或终端节点反着来除根节点(A)外其他非叶子节点都是非终端节点或分支节点
（记得是除A以外的）

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； A是B的父节点.
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
父亲节点和孩子可以一起理解如下图
A就是D和E的父亲节点相应的D和E就是A的孩子节点

兄弟节点: 具有相同父节点的节点互称为兄弟节点,这个兄弟只能是亲兄弟； 如上图：D,E就是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6;
简单易懂我们的A的度就是6所以树的度就和A的度相同

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

堂兄弟节点：双亲在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
有趣的是如果得H的祖先和子孙H本身就可以算作他自己的祖先或子孙,不过具体情况还是要看一下题目要求,所以子孙和祖先算是一个比较模糊的概念了.

森林：由m（m>0）棵互不相交的树的集合称为森林；多颗树便是森林

树的结构节点代码实现

树节点有多种形势的实现,不过舒文指向介绍最优秀的一种结构如下代码

typedefint DataType;structNode{structNode* _firstChild1;// 第一个孩子结点structNode* _pNextBrother;// 指向其下一个兄弟结点
    DataType _data;// 结点中的数据域};

这种结构无论下面是多少个孩子旁边有多少个兄弟我们都可以进行表示.
如下图表示了旁边的树图.

简化图如下

这种结构是公认的最优的结构,如果有更优的,请务必让俺瞅瞅,咱一定认真学习.

二叉树的概念

树的特殊结构,是个被计划生育的树,及每个节点最多只有两个子节点.也就是树的度最大为2

二叉树的组成: 1. 为空 2. 由根和左右子树组成.
二叉树的结构: 二叉树的左树和右树是有区别的不可以交换

所以二叉树有着更多的性质和特性,下面我们来介绍二叉树的特性.

特殊二叉树

满二叉树

每一层的节点数都达到了最大值,节点数目满足以二为公比的等比数列求和公式及2k-1,则他就是满二叉树

完全二叉树

完全二叉树要求若为k的深度的完全二叉树要求前k-1深度的节点未满第k层节点必须连续

二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2(i-1)个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2h-1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n0 = n2+1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1) . (ps： 是log以2为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有： 1.若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点 2.若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子 3.若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

结尾

后续舒文会再给一些关于二叉树的计算类型的选择题（大约三天后）大家期待一下。ʕ ᵔᴥᵔ ʔ