纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

Python 二叉树的概念 Python 二叉树的概念案例详解

Python碎片   2021-09-10 我要评论
想了解Python 二叉树的概念案例详解的相关内容吗Python碎片在本文为您仔细讲解Python 二叉树的概念的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Python,二叉树简介,Python,二叉树讲解下面大家一起来学习吧

二叉树简介

关于树的介绍请参考:https:

一、二叉树简介

二叉树是每个节点最多有两个子树的树结构是一种特殊的树如下图就是一棵二叉树

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

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

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

二、几种特殊的二叉树

只要树中所有节点的子树都不超过两个(0个1个2个)这就是一棵普通的二叉树在二叉树中有一些比较特殊除了满足二叉树的结构外还满足一些特殊的规则主要有如下几种

1. 完全二叉树:假设一棵二叉树的深度为d(d>1)除了第d层外其它各层的节点数目均已达最大值且第d层所有节点从左向右连续地紧密排列这样的二叉树被称为完全二叉树

完全二叉树的叶节点只能出现在最下层和次下层最下层的叶节点靠左紧密地排列次下层如果存在叶节点叶节点紧密地靠右排列

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

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

2. 满二叉树:所有叶节点都在最底层的完全二叉树称为满二叉树满二叉树是完全二叉树中的特殊情况除了满足完全二叉树的特征还满足所有叶节点都在最底层满二叉树是相同深度的二叉树中叶节点最多的树

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

3. 平衡二叉树(AVL树):如果二叉树的所有节点的两棵子树的高度差不大于1则二叉树被称为平衡二叉树

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

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

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

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

排序二叉树需要具有如下的性质:

4.1 如果二叉树的左子树不为空则左子树上所有节点的值均小于它的根节点的值

4.2 如果二叉树的右子树不为空则右子树上所有节点的值均大于它的根节点的值

4.3 如果独立地看左子树、右子树也分别为排序二叉树用递归的思想直到树的叶节点

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

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个

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

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

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

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

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


相关文章

猜您喜欢

  • Python 数据结构之树的概念 Python 数据结构之树的概念详解

    想了解Python 数据结构之树的概念详解的相关内容吗Python碎片在本文为您仔细讲解Python 数据结构之树的概念的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Python,数据结构之树,Python,数据结构之树讲解下面大家一起来学习吧..
  • Linux内核宏Container_Of Linux内核宏Container_Of的详细解释

    想了解Linux内核宏Container_Of的详细解释的相关内容吗仲一在本文为您仔细讲解Linux内核宏Container_Of的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Linux内核宏中Container_Of,Linux内核宏,Container_Of下面大家一起来学习吧..

网友评论

Copyright 2020 www.fresh-weather.com 【世纪下载站】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式