请选择 进入手机版 | 继续访问电脑版

[python] Python 二叉树的概念案例详解

  [复制链接]
查看1029 | 回复227 | 2021-9-13 11:53:46 | 显示全部楼层 |阅读模式

二叉树简介

关于树的先容 ,请参考:https://www.jb51.net/article/222488.htm

一、二叉树简介

二叉树是每个节点最多有两个子树的树布局 ,是一种特殊 的树,如下图,就是一棵二叉树。

Python 二叉树的概念案例详解

二叉树是由n(n>=0)个节点构成 的数据集合。当 n=0 时,二叉树中没有节点,称为空二叉树。当 n=1 时,二叉树只有根节点一个节点。当 n>1 时,二叉树的每个节点都最多只能有两个子树,递归地构建成一棵完备 的二叉树。

二叉树的两个子树被称为左子树(left subtree)和右子树(right subtree)。在二叉树中,假如 节点没有子树,则左子树和右子树都为空,假如 节点只有一个子树,要根据子树的左右来区分子树是左子树还是右子树,假如 节点有两个子树,则左子树和右子树都有。

假如 ,树中存在一个节点,该节点的子树超过两个,则该树不是二叉树,如下图中,节点C有三个子树,以是 这不是一棵二叉树。

Python 二叉树的概念案例详解

二、几种特殊 的二叉树

只要树中全部 节点的子树都不超过两个(0个,1个,2个),这就是一棵平常 的二叉树。在二叉树中,有一些比较特殊 ,除了满足 二叉树的布局 外,还满足 一些特殊 的规则,紧张 有如下几种。

1. 完全二叉树:假设一棵二叉树的深度为d(d>1),除了第d层外,别的 各层的节点数目 均已达最大值,且第d层全部 节点从左向右一连 地精密 分列 ,如许 的二叉树被称为完全二叉树。

完全二叉树的叶节点只能出现在 最下层和次下层,最下层的叶节点靠左精密 地分列 ,次下层假如 存在叶节点,叶节点精密 地靠右分列 。

如下图,树的深度为4,除了第4层,节点数达到了最大(“挂满了”),第4层的节点都是精密 地靠左分列 (中心 没有空位),以是 这是一棵完全二叉树。

Python 二叉树的概念案例详解

如下图,树的深度也为4,除了第4层,节点数也达到了最大,但是第4层的节点不是紧靠左侧分列 的(节点E没有子节点,空了两个位置),以是 这不是一棵完全二叉树,只是一棵平常 的二叉树。

Python 二叉树的概念案例详解

2. 满二叉树:全部 叶节点都在最底层的完全二叉树称为满二叉树。满二叉树是完全二叉树中的特殊 环境 ,除了满足 完全二叉树的特性 ,还满足 全部 叶节点都在最底层。满二叉树是类似 深度的二叉树中叶节点最多的树。

如下图,这起首 是一棵完全二叉树,其次,全部 的叶节点都在最底层,以是 这是一棵满二叉树。着实 ,满二叉树也可以这么定义,二叉树有节点的全部 层,节点数目 均已达最大值,则这是一棵满二叉树。

Python 二叉树的概念案例详解

3. 平衡 二叉树(AVL树):假如 二叉树的全部 节点的两棵子树的高度差不大于1,则二叉树被称为平衡 二叉树。

如上图中的满二叉树,任何节点的两棵子树高度差都是0(高度都相称 ,高度差不大于1),以是 这是一棵平衡 二叉树。

如下图中的二叉树,对于根节点A,左子树是以节点B为根的子树,高度为4,右子树是以节点C为根的子树,高为2,A的左子树与右子树的高度差为2(高度差大于1),以是 这不是一棵平衡 二叉树。

Python 二叉树的概念案例详解

AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis,是两人姓的缩写。AVL树中任何节点的两个子树的高度差不大于1,通过高度来判定 是否平衡 ,以是 也被称为高度平衡 树。

4. 排序二叉树(二叉查找树,Binary Search Tree):又称为二叉搜索 树、有序二叉树。

排序二叉树必要 具有如下的性子 :

4.1 假如 二叉树的左子树不为空,则左子树上全部 节点的值均小于它的根节点的值。

4.2 假如 二叉树的右子树不为空,则右子树上全部 节点的值均大于它的根节点的值。

4.3 假如 独立地看,左子树、右子树也分别为排序二叉树,用递归的头脑 ,直到树的叶节点。

如下图,根节点8的左子树中,全部 节点的值都小于根节点,右子树中,全部 节点的值都大于根节点,并且左子树和右子树都是排序二叉树,以是 这是一棵排序二叉树。

Python 二叉树的概念案例详解

5. 斜树:除了叶节点,全部 节点都只有左子树的二叉树称为左斜树。除了叶节点,全部 节点都只有右子树的二叉树称为右斜树。他们统称为斜树,判定 二叉树是否为斜树,紧张 是看树的布局 ,对节点的值没有要求。

如下图,左边的树中,除了叶节点D,全部 节点都只有左子树,这是一棵左斜树,同理,右边的树是一棵右斜树。

三、二叉树的特点和性子

通过对二叉树的先容 和对几种特殊 二叉树的相识 ,可知二叉树有以下特点:

1. 每个节点最多有两颗子树,以是 二叉树中节点的度不大于2,二叉树的度也不会大于2。

2. 左子树和右子树的次序不能颠倒。

3. 即使某节点只有一棵子树,也要根据左右来区分它是左子树还是右子树。

此外,二叉树还具有如下性子 :

1. 在二叉树的第i层,至多有 2^(i-1) 个节点(i>0) 。

这里说的是至多的环境 ,满二叉树的每一层节点都“挂满”了,以是 可以用下图中的满二叉树来验证,第1层的节点数为2^(1-1)=1个,... 第4层的节点个数最多为 2^(4-1)=8个。

2. 深度为i的二叉树至多有 2^i - 1 个节点(k>0) 。

这里也是说至多的环境 ,以是 也用满二叉树来验证,深度为4时,二叉树的节点数最多为 2^4 - 1=16-1=15个。

Python 二叉树的概念案例详解

3. 对于恣意 一棵二叉树,假如 其叶节点数为M,度为2的节点总数为N,则 M=N+1 。

为了不失一样平常 性,下图中的树是一棵平常 的二叉树,叶节点为 F,H,I,J,K,L ,共6个,度为2的节点为 A,B,C,D,G ,共5个。

Python 二叉树的概念案例详解

4. 具有n个节点的满二叉树的深度必为 log2(n+1) 。这个性子 是上面第2点的逆运算。

5. 对于一棵完全二叉树,若从上至下、从左至右编号,则编号为 i 的节点,(叶节点除外)其左子节点的编号必为2i,(叶节点除外)其右子节点的编号必为 2i+1,(根节点除外)其父节点的编号必为i/2(取整除)。

如下图,这是一棵完全二叉树,已经按规则编好号了,可以恣意 取一个节点举行 验证,都是符合此性子 的。

Python 二叉树的概念案例详解

到此这篇关于二叉树的概念案例详解的文章就先容 到这了,更多干系 二叉树的概念内容请搜索 脚本之家从前 的文章或继续欣赏 下面的干系 文章渴望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar 摸金狂人 | 2021-9-13 20:49:28 | 显示全部楼层
读了admin楼主的帖子,顿时马桶就通了。。。
回复

使用道具 举报

avatar 123457476 | 2021-9-13 21:14:49 | 显示全部楼层
我对admin楼主的敬仰犹如滔滔江水绵延不绝!
回复

使用道具 举报

avatar 素身素 | 2021-9-19 19:31:20 | 显示全部楼层
楼上的这是啥态度呢?
回复

使用道具 举报

avatar 卡庙寺 | 2021-9-20 07:38:12 | 显示全部楼层
admin楼主是好人!
回复

使用道具 举报

avatar 普通人物怨 | 2021-9-20 07:46:22 | 显示全部楼层
这个帖子会火的,鉴定完毕!
回复

使用道具 举报

avatar 喝咖啡的牛山 | 2021-9-20 07:46:29 | 显示全部楼层
admin楼主的帖子实在是写得太好了。文笔流畅,修辞得体!
回复

使用道具 举报

avatar 123456806 | 2021-9-20 07:46:29 | 显示全部楼层
小弟默默的路过贵宝地~~~
回复

使用道具 举报

avatar 荷叶224 | 2021-9-20 07:46:32 | 显示全部楼层
楼上的心情不错啊!
回复

使用道具 举报

avatar 123457373 | 2021-9-20 07:46:39 | 显示全部楼层
今天上网不回帖,回帖就回精华帖!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则