让二叉树无处可逃

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

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


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语言)

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

    2024年02月06日
    浏览(47)
  • 树、二叉树(C语言版)详解

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

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

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

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

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

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

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

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

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

    2024年01月21日
    浏览(32)
  • 二叉树--C语言实现数据结构

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

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

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

    2024年02月08日
    浏览(48)
  • [数据结构 -- C语言] 二叉树(BinaryTree)

    目录 1、树的概念及结构 1.1 树的概念 1.2 树的相关概念(很重要) 1.3 树的表示 2、二叉树的概念及结构 2.1 概念 2.2 特殊二叉树 2.3 二叉树的性质(很重要) 2.4 练习题 2.5 二叉树的存储结构 2.5.1 顺序存储 2.5.2 链式存储 3、二叉树的顺序结构及实现 3.1 二叉树的顺序结构 3.2 堆的

    2024年02月16日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包