数据结构(七)

ゝ一纸荒年。 2022-08-20 10:10 106阅读 0赞

接着树：

树的专业术语:  结点   父结点   子结点    子孙    堂兄弟

深度：从根结点到最底层结点的层数称为深度

叶子结点：没有子结点的结点

非终端结点：实际上就是非叶子结点

度：子结点的个数称为度

树分类：

一般树：任意一个结点的子结点个数不受限制

二叉树：任意一个结点的子结点个数最多两个，且子结点的位置不可更换

分类：

一般二叉树

满二叉树：不增加树的层数的前提下，无法再多添加一个结点的二叉树

完全二叉树：如果只是删除了满二叉树最底层最右边的连续若干个结                                        点，这样形成的二叉树就是完全二叉树，满二叉树是完全二叉树的特例

森林：n个互不相交的树的集合

树的存储：

二叉树的存储：

连续存储：\[完全二叉树\]

优点：查找某个结点的子结点和父结点（也包括判断有没有子结点）速度很快

缺点：耗用内存空间过大

树不是线性结构，而内存分配是线性结构，二叉树在存储过程中，都要转化为完全二叉树来存储，再由完全二叉树转化为线性结构

链式存储：

一般树的存储

双亲表示法

求父结点方便

孩子表示法

求子结点方便

双亲孩子表示法

求父结点和子结点都很方便

二叉树表示法

把一个普通树转化为二叉树来存储

具体转化方法：

设法保证任意一个结点的

左指针域指向它的第一个孩子

右指针域指向它的兄弟

只要能满足此条件，就可以把一个普通树转化为二叉树

一个普通树转化成的二叉树一定没有右子树

森林的存储

先把森林转化为二叉树，再存储二叉树

二叉树的操作：

遍历：先序遍历：\[锡先访问根结点\]

先访问根结点

再先序访问左子树

再先序访问右子树

中序遍历：\[中间访问根结点\]

中序遍历左子树

再访问根结点

再中序遍历右子树

后序遍历: \[最后访问根结点\]

先中序遍历左子树

再中序遍历右子树

再访问根结点

已知两种遍历序列求原始二叉树：

通过先序和中序或者中序和后序我们可以还原出原始二叉树，但是通过先序和后序是无法还原原始二叉树的。

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构题目收录（七）

1、在二叉树中有两个结点m和n，若m是n的祖先，则使用（）可以找到从m到n的路径。 A：先序遍历 B：中序遍历 C：后序遍历 D：层序遍历解

亦凉/ 2024年04月06日 10:27/ 0 赞/ 47 阅读

相关数据结构和算法（七）

从今晚开始补课 ================== 1. 7点到八点半晚上零长数组(柔性数组) ================== 定

迈不过友情╰/ 2022年12月13日 12:54/ 0 赞/ 109 阅读

相关数据结构 | 第七章图

文章目录一、图 1、图的定义 1.1 各种图的定义

迈不过友情╰/ 2022年09月01日 07:54/ 0 赞/ 244 阅读

相关数据结构(七)

接着树：树的专业术语: 结点父结点子结点子孙堂兄弟深度：从根结点到最底层结点的层数称为深度叶子结点：没有子结点的结点非终端结点：实

ゝ一纸荒年。/ 2022年08月20日 10:10/ 0 赞/ 107 阅读

相关数据结构小结（七）查找

几种查找算法 1.顺序查找 2.折半查找 3.分块查找 4.基于树的查找平均查找长度为确定某元素在查找表中的位置需要和给定值进行比较的关键字个数的期望值

ゝ一世哀愁。/ 2022年08月18日 12:22/ 0 赞/ 123 阅读

相关数据结构（七）链表

![这里写图片描述][20151012230722761] 二维数组是数组的数组，每一行作为一个二维数组的元素（当成一个线性表来看），可以把数组看成一个顺序存储的线性表。

- 日理万妓/ 2022年08月09日 05:26/ 0 赞/ 108 阅读

相关数据结构第七章图

数据结构笔记链接： [第一章绪论][Link 1] [第二章线性表][Link 2] [第三章栈和队列][Link 3] [第四章串][Link 4] [第五

柔情只为你懂/ 2022年06月08日 11:23/ 0 赞/ 540 阅读

相关数据结构(七)队列

1、队列需要具备的特性队列和栈的底层实现数据结构可以是：数组、链表，只不过在此基础上，队列和栈需要重载两个函数：节点的插入与删除函数。队列只能从链表头删除节点，从链表末尾插

比眉伴天荒/ 2022年05月31日 01:46/ 0 赞/ 89 阅读

相关数据结构 | 第七章图

很具体的知识点参考大佬blog： [https://blog.csdn.net/yuanlaijike/article/details/78074765][https_bl

怼烎@/ 2021年11月27日 06:20/ 0 赞/ 398 阅读

相关数据结构（七）：二叉树

二叉树的定义二叉树是 n （n >= 0）个节点的有限集合，该集合或者为空集（称为空二叉树）或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉

梦里梦外;/ 2021年09月11日 08:44/ 0 赞/ 285 阅读