- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
书节上回,我们接着聊二叉树,N叉树,以及树的存储.
如果一个二叉树,除最后一层节点外,每一层的节点数都达到最大值,即每个节点都有两个子节点,同时所有叶子节点都在最后一层,则这个二叉树为满二叉树.
因此可以得到满二叉树有以下性质:
(1)树的最大层数为k(k>=0,即层数从0开始),则第i层的节点总数为2i,树的叶子节点总数为2k ,树的总节点数为2 ^(k+1) - 1; 。
(2)如果已知数的总节点数为n,则树的最大层数为k=log2(n+1) - 1(k>=0,即层数从0开始); 。
(3)从树的顶层开始从上到下,从左到右,对每个节点按顺序进行编号,根节点为1作为起始; 。
a.对于节点i,如果其存在父节点,则父节点编号为i/2向下取整; 。
b.对于节点i,如果其存在左节点则左节点编号为2i,如果其存在右节点则右节点编号为2i+1,
如果一棵树,叶子节点只能出现在最后两层,并且最后一层的节点都集中在左侧且从左到右是连续的.
由此我们可以得到完全二叉树有以下性质:
(1)叶子节点只能出现在倒数第一层和倒数第二层; 。
(2)倒数第一层的所有叶子节点都集中此层最左侧连续位置; 。
(3)倒数第二层如果存在叶子节点则层的所有叶子节点都集中在此层最右侧连续位置; 。
(4)所有节点中如果存在一个节点只有一个子节点,则此节点一定在倒数第二层,并且这个子节点一定是左节点; 。
(5)满二叉树一种特殊的完全二叉树; 。
(6)满二叉树性质(3)也适用于完全二叉树; 。
(7)如果完全二叉树不是满二叉树,则除最后一层外为满二叉树,适用满二叉树所有性质; 。
(8)如果节点总数为n,并且i<=n/2,则第i个节点为非叶子节点; 。
(9)如果节点总数为n,如果n为偶数则叶子节点数为n/2;如果n为奇数则叶子节点数为(n+1)/2; 。
(10)如果树的层数为k(k>=0),则树数的总节点数的访问为[2k,2(k+1) - 1)]; 。
(11)如果已知数的总节点数为n,则树的最大层数为k=log2(n+1) (k>=0,即层数从0开始),并且k向下取整; 。
二叉搜索树是一种特殊的二叉树,又叫二叉查找树、二叉排序树,可以说这是一种为了查询而生的二叉树.
二叉搜索树有以下性质:
(1)每个节点值必须唯一,不能有重复值; 。
(2)每个节点最多有两个子节点; 。
(3)对于任意一个节点,如果其存在左子树则左子树上所有节点值小于该节点值,如果其存在右子树则右子树上所有节点值大于该节点值; 。
(3)左子树和右子树本身也各自是二叉搜索树; 。
平衡二叉树顾名思义就是使二叉树平衡在某种状态下,某种状态具体指树中任意一个节点左右子树高度差绝对值小于等于1,并且其左右子树同样也是平衡二叉树.
平衡二叉树是通过控制树的深度来优化二叉搜索树平均操作时间.
AVL树是平衡二叉树的一种特例,严格执行平衡二叉树的定义,也是最早发明的自平衡二叉搜索树.
红黑树也是一种自平衡二叉搜索树,但其并没有严格执行平衡二叉树定义,平衡条件相对比较宽松,允许左右子树高度相差绝对值大于1.
这两种树我们后面会找机会单独详细讲解.
此外还有哈夫曼树、线段树、伸展树、替罪羊树等二叉树这里就不一一介绍了,后面我们单独拿出来讲解.
B树、B+树、2-3-4树、R树、Trie树等多叉树我们后面找机会单独拿出来详解.
顺序存储只用一组连续的地址空间存储整个树.
当然并不是所有树都适合顺序存储的,还记得上面说的满二叉树的性质(3)吗?如果把满二叉树从上到下、从左到右,则左右子节点编号可以通过父节点编号表示。如果父节点编号为i,则其左子节点编号为2i,其右子节点编号为2i+1。而根节点作为已知起始值1,就意味着其后代节点都可以通过根节点直接或间接表示.
而编号不经让我们想到数组下标,这就意味着我们可以把整个满二叉树装进数组里。因为完全二叉树也满足满二叉树的性质(3),所以完全二叉树也可以装进数组。如下图.
那如果非完全二叉树呢?能否放入数组中呢,答案是肯定可以的。我们只需要把非完全二叉树想象成满二叉树,把缺少的节点虚拟补全,然后对其编号,最后装入数组,入下图:
但是我们会发现编号4、5、7位都为空值,当然编号7是可以去掉的,即使如此,还是很浪费数组空间的,因此顺序存储是比较适合完全二叉树存储的,而其他类型二叉树并不是很适合.
顺序存储有其局限性,因此大多数树都是使用链式存储。链式存储的核心思想就是每一个节点设计为两部分,其一为数据域存放元素值,其二为指针域存放指向子节点指针,节点有多少个子节点指针域就有多少个指针.
我们还是以二叉树为例,链式存储结构如下:
注:测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。https://gitee.com/hugogoos/Planner 。
最后此篇关于数据结构-树,再探的文章就讲到这里了,如果你想了解更多关于数据结构-树,再探的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我目前正在尝试基于哈希表构建字典。逻辑是:有一个名为 HashTable 的结构,其中包含以下内容: HashFunc HashFunc; PrintFunc PrintEntry; CompareF
如果我有一个指向结构/对象的指针,并且该结构/对象包含另外两个指向其他对象的指针,并且我想删除“包含这两个指针的对象而不破坏它所持有的指针”——我该怎么做这样做吗? 指向对象 A 的指针(包含指向对象
像这样的代码 package main import "fmt" type Hello struct { ID int Raw string } type World []*Hell
我有一个采用以下格式的 CSV: Module, Topic, Sub-topic 它需要能够导入到具有以下格式的 MySQL 数据库中: CREATE TABLE `modules` ( `id
通常我使用类似的东西 copy((uint8_t*)&POD, (uint8_t*)(&POD + 1 ), back_inserter(rawData)); copy((uint8_t*)&PODV
错误 : 联合只能在具有兼容列类型的表上执行。 结构(层:字符串,skyward_number:字符串,skyward_points:字符串)<> 结构(skyward_number:字符串,层:字符
我有一个指向结构的指针数组,我正在尝试使用它们进行 while 循环。我对如何准确初始化它并不完全有信心,但我一直这样做: Entry *newEntry = malloc(sizeof(Entry)
我正在学习 C,我的问题可能很愚蠢,但我很困惑。在这样的函数中: int afunction(somevariables) { if (someconditions)
我现在正在做一项编程作业,我并没有真正完全掌握链接,因为我们还没有涉及它。但是我觉得我需要它来做我想做的事情,因为数组还不够 我创建了一个结构,如下 struct node { float coef;
给定以下代码片段: #include #include #define MAX_SIZE 15 typedef struct{ int touchdowns; int intercepti
struct contact list[3]; int checknullarray() { for(int x=0;x<10;x++) { if(strlen(con
这个问题在这里已经有了答案: 关闭 11 年前。 Possible Duplicate: Empty “for” loop in Facebook ajax what does AJAX call
我刚刚在反射器中浏览了一个文件,并在结构构造函数中看到了这个: this = new Binder.SyntaxNodeOrToken(); 我以前从未见过该术语。有人能解释一下这个赋值在 C# 中的
我经常使用字符串常量,例如: DICT_KEY1 = 'DICT_KEY1' DICT_KEY2 = 'DICT_KEY2' ... 很多时候我不介意实际的文字是什么,只要它们是独一无二的并且对人类读
我是 C 的新手,我不明白为什么下面的代码不起作用: typedef struct{ uint8_t a; uint8_t* b; } test_struct; test_struct
您能否制作一个行为类似于内置类之一的结构,您可以在其中直接分配值而无需调用属性? 前任: RoundedDouble count; count = 5; 而不是使用 RoundedDouble cou
这是我的代码: #include typedef struct { const char *description; float value; int age; } swag
在创建嵌套列表时,我认为 R 具有对列表元素有用的命名结构。我有一个列表列表,并希望应用包含在任何列表中的每个向量的函数。 lapply这样做但随后剥离了列表的命名结构。我该怎么办 lapply嵌套列
我正在做一个用于学习目的的个人组织者,我从来没有使用过 XML,所以我不确定我的解决方案是否是最好的。这是我附带的 XML 文件的基本结构:
我是新来的 nosql概念,所以当我开始学习时 PouchDB ,我找到了这个转换表。我的困惑是,如何PouchDB如果可以说我有多个表,是否意味着我需要创建多个数据库?因为根据我在 pouchdb
我是一名优秀的程序员,十分优秀!