C语言学习网

怎么分析python二叉树

发表于:2022-10-04 作者:安全数据网编辑
编辑最后更新 2022年10月04日,这篇文章给大家介绍怎么分析python二叉树,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。很多新手可能刚接触到数据结构,下面先给出一张关于树的一些基本概念。二叉树的定义二叉树是n

这篇文章给大家介绍怎么分析python二叉树,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

很多新手可能刚接触到数据结构,下面先给出一张关于树的一些基本概念。

二叉树的定义

二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。下图展示了一棵普通二叉树:

二叉树的特点

由二叉树定义以及图示分析得出二叉树有以下特点:
1)每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点。
2)左子树和右子树是有顺序的,次序不能任意颠倒。
3)即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。

二叉树的性质

1)在二叉树的第i层上最多有2i-1 个节点 。(i>=1)
2)二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1)
3)n0=n2+1 n0表示度数为0的节点数,n2表示度数为2的节点数。
4)在完全二叉树中,具有n个节点的完全二叉树的深度为[log2n]+1,其中[log2n]是向下取整。

二叉树遍历

所谓遍历是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。

二叉树的遍历分为深度优先和广度优先两种,其中深度优先又包括前序遍历、中序遍历、后序遍历三种,所谓前、中、后是根据根节点与左右子树的遍历顺序决定的。

前序遍历是先访问根节点再访问左子树最后访问右子树;中序遍历是先访问左子树再访问根节点最后访问右子树;后序遍历是先访问左子树再访问右子树最后访问根节点。

广度优先遍历则是从根节点开始由上到下按层访问,每一层从左到右依次访问。

下面分别介绍这几种遍历方式以及它们的代码实现。

二叉树结点定义

python代码定义二叉树结点如下:

图 a(二叉树)

前(先)序遍历

递归思想实现先序遍历较易理解,从二叉树的根结点出发,当第一次到达结点时就输出结点数据,按照先向左在向右的方向访问 。二叉树的前序遍历输出为:ABDHIEJCFG

python代码实现如下:

非递归遍历思路如下:
1)定义一个栈
2)将根节点压入栈中
3)每次从栈中弹出结点记为cur并打印,如果右孩子不为空,将右孩子压入栈中,如果左孩子不为空,将左孩子压入栈中
4)不断重复步骤3,直到栈空结束

python代码实现如下:

中序遍历

递归思想实现中序遍历顺序,先遍历左子树;再访问根结点;最后遍历右子树。二叉树的中序遍历输出为:HDIBJEAFCG

python代码实现如下:

非递归遍历思路如下:

1)申请一个栈stack,申请一个变量cur指向头结点

2)先把头结点压入栈中,对于以cur为头结点的整颗子树来说,依次把整颗树的左边界压入栈中,即不断令cur=cur.left

3)不断重复步骤2,直到cur为空,此时从栈中弹出结点node并打印,然cur=node.right,然后重复步骤2

4)当stack为空并且cur为空时,结束。

python代码实现如下:

后序遍历

递归思想实现后序遍历顺序,先遍历左子树;再遍历右子树;最后访问根结点。二叉树的后序遍历输出为:HIDJEBFGCA

python代码实现如下:

非递归遍历思路如下:
1)申请两个栈s1,s2,然后将头结点压入s1
2)从s1中弹出的结点记为cur,并加入到栈s2中,然后把cur的左孩子压入s1中,然后把cur的右孩子压入s1中
3)不断重复2,直到s1为空
4)从s2弹出结点并打印

python代码实现如下:

广度优先(层序)遍历

广度优先(层序遍历)是用队列来实现的,从二叉树的第一层(根结点)开始,自上至下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。

按照从根结点至叶结点、从左子树至右子树的次序访问二叉树的结点。

算法:

1、初始化一个队列,并把根结点入列队;

2、当队列为非空时,循环执行步骤3到步骤5,否则执行6;

3、出队列取得一个结点,访问该结点;

4、若该结点的左子树为非空,则将该结点的左子树入队列;

5、若该结点的右子树为非空,则将该结点的右子树入队列;

6、结束。

python代码实现如下:

关于怎么分析python二叉树就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

0