让二叉树无处可逃

这篇具有很好参考价值的文章主要介绍了让二叉树无处可逃。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

志不立,天下无可成之事。 ——王阳明


1、树?什么是树

1、1、基本概念

树也是属于一种数据结构,它是一种非线性的数据结构,与栈,队列和链表是不同的存在。
由n(n>=0)个有限的结点组成的具有层次关系的集合。至于为什么是树呢?其实按照结构图来看,把一颗二叉树的结构图倒过来就像一颗树了。让二叉树无处可逃,C语言历程,c语言,二叉树

让二叉树无处可逃,C语言历程,c语言,二叉树
也就是像这样。
1、树都会有一个特殊的结点,称为根节点,根节点没有父节点
2、除去根节点之后,其余的结点被分为M(M>0)个互不相交的集合T1,T2,Tm,其中每一个集合又是一棵结构类似的子树。
3、因此,树是递归定义的。(在后面的关于树之类的问题上,递归的解决方法占很大一部分)

注意:根据观察,其实真正的树,根和根之间不会相互交错。那计算机的树其实也是,子树也是不能有交集的,否则将不会是树的结构。让二叉树无处可逃,C语言历程,c语言,二叉树

1、2、树的相关概念

让二叉树无处可逃,C语言历程,c语言,二叉树

:一个节点的子树的个数。(例如A的度就是6)
叶节点或终端节点:度为0的节点称为叶子节点(就例如B,C,等等)
分支节点或非终端节点:度不为0的节点(例如 D,E,J等)
双亲结点或父节点:若一个结点有子节点,则这个结点称为其子节点的父节点:(例如A是B的父节点)
孩子结点或子节点:一个节点含有子树的根结点称为该子节点的父节点:(例如B是A的孩子节点)
兄弟节点:具有相同父节点的节点互称为兄弟节点;(B、C是兄弟节点)
树的度:一棵树中,最大的节点的度称为树的度;(树的度为6)
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
树的高度或深度:树中节点的最大层次; (例如这棵树的高度为4)
堂兄弟节点:双亲在同一层的节点互为堂兄弟;(H、I互为兄弟节点)
节点的祖先:从根到该节点所经分支上的所有节点;(A是所有节点的祖先)
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。(所有节点都是A的子孙)
森林:由m(m>0)棵互不相交的树的集合称为森林;

1、3、树的表示方式

相对于线性表的表示,由于树的不确定的性质,树的存储表示会相对比较麻烦,不只是需要保存树中的数值,还要保证节点和节点之间的关系。由于树的复杂性,所以树的表示方法也会出现多元化,就比如:双亲表示法,孩子表示法,孩子双亲表示法以及孩子兄弟表示法等。在这里不方便多说,就简单的介绍几种常用的方法孩子兄弟表示法(也是一个很妙的表示方法)

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

让二叉树无处可逃,C语言历程,c语言,二叉树
这就是通过孩子找兄弟,让父节点只指向一个节点,而处于同一层的都通过,带头的兄弟来找到。

下面的这个就是我简单的写一下其余的表示方法,因为相对于其余的方法,我对于孩子兄弟法还是更喜欢一点的。
让二叉树无处可逃,C语言历程,c语言,二叉树
这里的我想到的问题,在这篇文章有详细的讲解,关于指针的,如果不熟悉,可以再看一下

1、4、树的实际运用

让二叉树无处可逃,C语言历程,c语言,二叉树

2、二叉树?只有两个分支吗?

2、1、基本概念

二叉树也是一棵节点的有限集合
1、可能为空
2、由根节点加上两棵左子树和右子树的二叉树构成。让二叉树无处可逃,C语言历程,c语言,二叉树
1、二叉树不存在度大于2的节点
2、二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序的树

二叉树也可以通过递归的方式来组成,二叉树也只能分为这几种情况让二叉树无处可逃,C语言历程,c语言,二叉树

2、2、二叉树的相关定义

特殊的二叉树
==1、满二叉树:==一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k)-1,则它就是满二叉树。
==2、完全二叉树:==完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

2、3、二叉树的相关性质

二叉树很类似与我们高中学习的生物中的关于细胞分裂的公式。(下面的公式都是相当于根节点的层数是1的情况下)
1、一棵非空的二叉树的第i层上的节点个数最多有2^(k-1)个节点。
2、深度为h的二叉树最大节点数为2^h-1。
3、如果度为 0 的节点个数为 n0 ,度为 2 的节点个数为 n2 ,那么则有n0=n2+1
4、一个有n个节点的满二叉树,那么它的深度为log(n+1),log是以2为底
(ps:明天出一个关于树相关的问题集合,感兴趣的记得关注!)

2、4、二叉树的表示方式

看过树的介绍,不难发现,二叉树相对与树的结构多样,规则变化,二叉树相对简单,所以对于二叉树的存储方式来说也是更简单一点
1、顺序存储
顺序结构就是用数组来存储,一般来说,数组的使用**只适合表示完全二叉树,**对于不是完全二叉树时会有空间的浪费。二叉树顺序存储在物理结构上是数组,但是逻辑结构上是一棵二叉树。
正常来说,这种的数组结构都是大部分存储 堆
让二叉树无处可逃,C语言历程,c语言,二叉树
2、链式存储
用链表来表示一棵二叉树
让二叉树无处可逃,C语言历程,c语言,二叉树
让二叉树无处可逃,C语言历程,c语言,二叉树
转换成代码的形式,也就是相当于这样

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
};

3、总结

对于二叉树其实本质上的基础就只有那么多,下面会推出二叉树的衍生的结构,堆。对于二叉树的问题和操作都会在之后推出,敬请期待。文章来源地址https://www.toymoban.com/news/detail-819318.html

到了这里,关于让二叉树无处可逃的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 树、二叉树(C语言版)详解

    🍕博客主页:️自信不孤单 🍬文章专栏:数据结构与算法 🍚代码仓库:破浪晓梦 🍭欢迎关注:欢迎大家点赞收藏+关注 树是n(n=0)个结点的有限集。当n = 0时,称为空树。在任意一棵非空树中应满足: 有且仅有一个特定的称为根的结点。 当n1时,其余节点可分为m(m0)个

    2024年02月15日
    浏览(26)
  • 数据结构---二叉树(C语言)

    空树 非空:根节点,根节点的左子树、根节点的右子树组成的。 从二叉树的定义来看,二叉树是递归定义的,因此我们可以用递归的形式来遍历二叉树。 1.1.1二叉树前中后序遍历(递归版) 访问根结点的顺序不同。 1.1.2 层序遍历 层序遍历是按照二叉树的高度,一层一层遍

    2024年02月06日
    浏览(48)
  • Redis的实现三:c语言实现平衡二叉树,通过平衡二叉树实现排序集

    概况 :Redis中的排序集数据结构是相当复杂的独特而有用的东西。它不仅提供了顺序排序数据的能力,而且具有按排名查询有序数据的独特特性。 (Sorted Set)是一种特殊的数据结构,它结合了集合(Set)和有序列表(List)的特点。在Redis中,每个成员都有一个分数(score),

    2024年01月16日
    浏览(43)
  • 【C语言题解】 | 965. 单值二叉树

    提示: 给定树的节点数范围是 [1, 100]。 每个节点的值都是整数,范围为 [0, 99] 。 这个题目我们通过分治思想来解题: 首先传入的是根节点 其次判断根节点是否有左子树和右子树,若存在则判断左右子树的值是否于根节点的值相同(不同则返回false,相同则继续) 若正确,

    2024年01月21日
    浏览(33)
  • 二叉树的层次遍历(C语言)

    二叉树是n(n=0)个节点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组。 先序遍历 中序遍历    后序遍历  层次遍历     一、头文件   二、二叉树的结构   三、队列的结构   四、队列的初始化

    2024年02月07日
    浏览(36)
  • 【数据结构】二叉树---C语言版

    树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树,是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个特殊的结点,称为根结点, 根节点没有前驱结点 除根节点外,其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(45)
  • 二叉树--C语言实现数据结构

    本期带大家一起用C语言实现二叉树🌈🌈🌈 二叉树是一种特殊的树状数据结构,它由节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点 二叉树的链式存储结构是指用 链表 来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点

    2024年02月17日
    浏览(41)
  • 【数据结构初阶】八、非线性表里的二叉树(二叉树的实现 -- C语言链式结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)-CSDN博客  ==========

    2024年02月08日
    浏览(52)
  • 手撕链式二叉树(二)—【C语言】

    链式二叉树(一)         http://t.csdn.cn/HWu6E 目录 1. 二叉树找值为x的节点 代码实现分析  代码实现 递归展开图 2. 求二叉树层数 代码思路分析 代码实现   3. 二叉树的销毁 代码思路分析 代码实现 运行结果 4. 二叉树的一些OJ题目 1. 单值二叉树                      OJ链接

    2024年02月06日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包