数据结构学习笔记11--树与二叉树

绝地灬酷狼 2022-06-06 13:20 166阅读 0赞

1.树的定义：

树是n个结点的有限集。在任意一颗非空树中应满足：

(1)有且仅有一个特定的称为根(Root)的结点；

(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树。

每棵子树的根节点有且仅有一个直接前驱，但可以有0个或多个直接后继。

由此可以看到，树的定义是一个递归的定义，即树的定义中又用到了树的定义。

下图中给出了常见的树的例子：

![Center][]

树的相关概念（重要性质）:

(1).结点的度：每个结点度指的是这个结点的子女数，即结点所拥有的子树的个数。

(2).所有结点的度数+1=结点总数

2.二叉树

(1)二叉树的定义：

二叉树是一种应用广泛的树形结构，它的特点是每个结点最多只能有两个孩子。在二叉树中，必须严格区分左右孩子，次序不能颠倒，若改变次序则变成

二叉树的特点：

(a).非空二叉树上叶子结点数等于双分支结点数+1。（证明方法可用上文中树的性质：所有结点的度数+1=结点总数。设二叉树中的叶子结点数、单分支结点数、双分支结点数分别为N0，N1，N2，则N0+N1+N2=N0X0+N1X1+N2X2+1，即N0=N2+1）

(b).非空二叉树上第i层上至多有2^(i-1)个结点。

(3).高度为h的二叉树至多有2^i -1个结点。

(2)满二叉树

满二叉树的定义：一棵高度为h，并且有2^h-1个结点的二叉树称为满二叉树。

因此，在满二叉树中，每一层结点都达到了最大个数。除最底层结点的度为0之外，其他各层结点的度都为2.

![Center 1][]

(3)完全二叉树

完全二叉树的定义：设一个深度为h的二叉树，每层结点的数目如果满足：

a)第i层( 1<=i<=(h-1) )上的结点个数均为2^(i-1)

b)第h层从右边起连续缺若干个结点

这样的二叉树称为完全二叉树，其特点是：

a)叶节点仅在层次最大的两层出现

b)对任一结点，若其右子树的高度为l，则其左子树的高度只能是l或l+1.

![Center 2][]

[Center]: /images/20220606/eaeb1f59a0a544f39a9e2c08f817dd39.png
[Center 1]: /images/20220606/1ef6a73a300e419dbcc35f2403f15934.png
[Center 2]: /images/20220606/985a830e8ca34870a33b7771bdf70643.png

发表评论取消回复

表情：

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

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

相关阅读

相关《数据结构高分笔记》树与二叉树

文章目录二叉树的递归遍历(前中后)计算树型的表达式二叉树的递归遍历(前中后)typedef struct BTNode{ char data; struc...

比眉伴天荒/ 2024年05月08日 06:06/ 0 赞/ 61 阅读

相关【数据结构】树与二叉树

文章目录 * ?树型结构 * * ??什么是树型结构 * ??树型结构的概念 * ??树的表示形式 * ?...

冷不防/ 2024年04月17日 10:34/ 0 赞/ 70 阅读

相关【数据结构】树与二叉树

【数据结构】树与二叉树一、树的基本概念二、二叉树的基本概念三、二叉树的性质四、二叉树的存储结构五、二叉树的遍历（访问）六、

「爱情、让人受尽委屈。」/ 2023年09月23日 20:41/ 0 赞/ 65 阅读

相关数据结构学习笔记 - 二叉树

二叉树简介树, 非线性表结构树有三个概念: 高度从下向上数, 起点是0 深度从上向下数, 起点是0 层数从上向下数, 起点是1 二叉树

た入场券/ 2023年01月12日 12:00/ 0 赞/ 109 阅读

相关【数据结构——树与二叉树】

【数据结构——树和二叉树】目录：【数据结构——树和二叉树】一、树和二叉树的定义（一）树的定义（二）基本术语

不念不忘少年蓝@/ 2022年12月18日 00:55/ 0 赞/ 230 阅读

相关【数据结构】树与二叉树

定义 ![树][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55uW5Li955S3_si

た入场券/ 2022年09月10日 05:09/ 0 赞/ 225 阅读

相关数据结构学习笔记（5）——树与二叉树

树的基本概念结点：结点不仅包含数据元素，而且包含指向子树的指针结点的度：结点拥有的子树个数或者分支的个数。树的度：树中各结点度的最大值。叶

「爱情、让人受尽委屈。」/ 2022年08月30日 13:52/ 0 赞/ 166 阅读

相关数据结构学习笔记11--树与二叉树

1.树的定义：树是n个结点的有限集。在任意一颗非空树中应满足： (1)有且仅有一个特定的称为根(Root)的结点； (2)当n>1时，其余结点可分为m(m>

绝地灬酷狼/ 2022年06月06日 13:20/ 0 赞/ 167 阅读

相关【数据结构与算法】树（二）：二叉树

二叉树的特点每个结点最多有两颗子树，所以二叉树的度最大就是2. 左子树和右子树是由顺序的，不能够颠倒，即使树中只有一颗子树，也是要区分它是左子树还是右子树的

骑猪看日落/ 2022年05月21日 06:58/ 0 赞/ 305 阅读

相关数据结构——树与二叉树

一、引言在介绍索引前，要先了解一下数据结构——树。因为MySQL中常用的InnoDB和MyISAM引擎中，索引的存储结构用到的数据结构就是B+树，所以有必要要了解一下。

谁践踏了优雅/ 2022年03月26日 03:52/ 0 赞/ 351 阅读