二叉树的概念和基本术语

悠悠 2021-12-01 22:46 447阅读 0赞

二叉树简单说就是有两个子树的树

1.种类及概念:

二叉树是每个结点最多有两个子树的树结构。

完全二叉树：除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点。

满二叉树：每一层上的节点数都是最大节点数，深度为k，且有2^k-1个节点。

平衡二叉树：又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

森林：不考虑连通性，允许图中有多个连通分量的结构。

![1188607-20190523014758542-1640476648.png][]

(1)空二叉树：图(a)

(2)只有一个根结点的二叉树：图(b)

(3)只有左子树：图(c)

(4)只有右子树：图(d)

(5)完全二叉树：图(e)

2.定义及性质：

二叉树常被用于实现二叉查找树和二叉堆。

二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。

二叉树不是树的一种特殊情形，树和二叉树有两个主要差别：

1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；

2. 树的结点无左、右之分，而二叉树的结点有左、右之分。

3.其他术语：

子树：通常被称作“左子树”（left subtree）和“右子树”（right subtree）；

根结点（root）：也叫树根，所有非空的二叉树中，都有且仅有一个根结点。它是同一棵树中除本身外所有结点的祖先，没有父结点。

树的结点（node）：包含一个数据元素及若干指向子树的分支；

孩子结点（child node）：结点的子树的根称为该结点的孩子；

双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；

兄弟结点：同一双亲的孩子结点；

堂兄结点：位于同一层的，并且父节点之间是兄弟结点的结点

祖先结点: 从根到该结点的所经分支上的所有结点；

子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；

结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；也叫结点的层次或结点的深度；

树的深度（depth）：树中最大的结点层，也叫结点的最大层次；

结点的高度（height of node）：高度与深度不同，高度的描述是自下向顶的；

路径（path）和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，...，nk,ni是ni+1的父结点。路径所包含边的个数为路径的长度；

结点的度（Degree）：拥有子结点（子树）的数量；

树的度： 选取所有结点中最大的度；

叶子结点：也叫终端结点，是度为 0 的结点。位于树最深层，并且树只要非空，就一定存在叶子结点

分枝结点：度不为0的结点。除了叶子结点之外的结点都为分支结点，而且根结点也是分支结点

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序。

【注：参考：https://blog.csdn.net/weixin\_41133154/article/details/80027285

https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91/1602879?fr=aladdin】

转载于:https://www.cnblogs.com/GodSince/p/10909565.html

[1188607-20190523014758542-1640476648.png]: /images/20211201/2855718f17c2427ab940b6b936e53ddf.png

发表评论取消回复

表情：

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

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

相关阅读

相关【数据结构】二叉树的基本概念

![在这里插入图片描述][f601c179eaf04219afa7d83b5cd94a0b.png] 文章目录一、树 1、什么是树 2

╰半夏微凉°/ 2024年03月04日 02:50/ 0 赞/ 129 阅读

相关树、二叉树、完全二叉树的区别与基本概念

树、二叉树、完全二叉树的区别与基本概念一、树树：不包含回路的连通无向图（树是一种简单的非线性结构）。 ![watermark_type_ZmFuZ3poZW5

我会带着你远行/ 2023年01月02日 12:22/ 0 赞/ 217 阅读

相关二叉树的基本概念

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 二叉树的定义一棵二叉树是结点的一个有限集合，该集合或

本是古典何须时尚/ 2022年10月02日 01:55/ 0 赞/ 225 阅读

相关二叉树（定义，基本术语，常考性质）

知识点归纳：二叉树的五种形态几种特殊的二叉树满二叉树，完全二叉树，二叉排序树，平衡二叉树 \-满二叉树注意第三条性质，有助于用顺序存储的方式存储二叉树![在

电玩女神/ 2022年09月09日 09:18/ 0 赞/ 183 阅读

相关树的术语、二叉树的性质、二叉树的基本操作总结

一、树的术语 <table style=""> <tbody> <tr> <td style="border:1px solid rgb(211,

傷城~/ 2022年06月09日 04:06/ 0 赞/ 237 阅读

相关关于二叉树二叉堆的一些基本概念

文章转载自：[http://blog.csdn.net/include\_u/article/details/48092129][http_blog.csdn.net_incl

古城微笑少年丶/ 2022年06月07日 09:25/ 0 赞/ 451 阅读

相关基本概念和术语

数据:计算机中可以操作的对象 1.可以输入计算机，能被计算机识别 2.可以被计算机处理数据项:构成数据的最小单位，若干个数据项构成数据元素。（人这个数据元素中，眼耳鼻等

青旅半醒/ 2022年05月09日 23:04/ 0 赞/ 268 阅读

相关二叉树的基本概念和特点

首先，什么是二叉树？二叉树（Binary Tree）是n （n>=0）个节点的有限集合，该集合可以为空集（称为空二叉树），或者由一个根节点和两个互不相交的，分别称为根节点

太过爱你忘了你带给我的痛/ 2022年01月31日 22:43/ 0 赞/ 531 阅读

相关二叉树的概念和基本术语

二叉树简单说就是有两个子树的树 1.种类及概念: 　　二叉树是每个结点最多有两个子树的树结构。　　完全二叉树：除最后一层外，若其余层都是满的，并且最后一层或者是满的，或

悠悠/ 2021年12月01日 22:46/ 0 赞/ 448 阅读

相关树和二叉树的基本概念

一树示意图 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubm

ゝ一纸荒年。/ 2021年07月25日 02:49/ 0 赞/ 458 阅读