python 二叉树简介

雨点打透心脏的1/2处 2023-06-18 10:59 10阅读 0赞

# **一、树的定义** #

树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。  
树的递归定义：  
树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：  
(1)有且仅有一个特定的称为根(Root)的结点；  
(2)其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。

# **二、二叉树的定义** #

1、二叉树是由n（n≥0）个结点组成的有限集合、每个结点最多有两个子树的有序树。它或者是空集，或者是由一个根和称为左、右子树的两个不相交的二叉树组成。  
特点：  
（1）二叉树是有序树，即使只有一个子树，也必须区分左、右子树；  
（2）二叉树的每个结点的度不能大于2，只能取0、1、2三者之一；  
（3）二叉树中所有结点的形态有5种：空结点、无左右子树的结点、只有左子树的结点、只有右子树的结点和具有左右子树的结点。

2、满二叉树：如果一棵树的每一层的节点都达到了最大值（2的（n-1)次方)，则称这棵树为满二叉树。满二叉树的特点除了叶子结点外，所有的分支节点都含有左子树和右子树。其**特点**有：  
  （1）叶子节点只能出现在最下面一层  
  （2）非叶子节点度一定是2  
  （3）在同样深度的二叉树中，满二叉树的节点个数最多，节点个数为： 2h−12h−1 ，其中 hh 为树的深度。

![format_png][]

3、完全二叉树：假设根节点的标号是1，其余节点均按次序从上到下，从左到右编号，每个编号均和满二叉树相同，则称这棵二叉树为完全二叉树。完全二叉树不一定是满二叉树，满二叉树一定是完全二叉树。因为完全二叉树的最后一层的节点可以不达到该层的最大节点数。其具有以下**特点**：  
  （1）叶子节点可以出现在最后一层或倒数第二层。  
  （2）最后一层的叶子节点一定集中在左部连续位置。  
  （3）完全二叉树严格按层序编号。（可利用数组或列表进行实现，满二叉树同）  
  （4）若一个节点为叶子节点，那么编号比其大的节点均为叶子节点。

![format_png 1][]

扩充二叉树：除叶子结点外，其余结点都必须有两个孩子的二叉树。

# **三、**树结构相关专业术语 #

结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支

结点的度(degree)——结点拥有的子树数

叶子(leaf)——度为0的结点

孩子(child)——结点子树的根称为该结点的孩子

双亲(parents)——孩子结点的上层结点叫该结点的~

兄弟(sibling)——同一双亲的孩子

树的度——一棵树中最大的结点度数

结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……

深度(depth)——树中结点的最大层次数

森林(forest)——m(m0)棵互不相交的树的集合

# **四、二叉树的性质** #

二叉树有以下几个性质：TODO(上标和下标)  
**性质1**：二叉树第i层上的结点数目最多为 **2^(****i-1)** (i≥1)。  
**性质2**：深度为k的二叉树至多有**2^(k)-1**个结点(k≥1)。  
**性质3**：包含n个结点的二叉树的高度至少为**log2 (n+1)**。  
**性质4**：在任意一棵二叉树中，若终端结点的个数为**n0**，度为2的结点数为**n2**，则**n0=n2+1**。

## 满二叉树性质： ##

（1）具有 nn 个的结点的完全二叉树的深度为 log2n+1log2⁡n+1 。.  
  （2）如果有一颗有 nn 个节点的完全二叉树的节点按层次序编号，对任一层的节点 i，（1≥i≥n）i，（1≥i≥n） 有：  
    （2.1）如果 i=1i=1 ，则节点是二叉树的根，无双亲，如果 i>1i>1 ，则其双亲节点为 ⌊i/2⌋⌊i/2⌋ 。  
    （2.2）如果 2i>n2i>n 那么节点i没有左孩子，否则其左孩子为 2i2i 。  
    （2.3）如果 2i+1>n2i+1>n 那么节点没有右孩子，否则右孩子为 2i+12i+1 。

## 完全二叉树性质： ##

**性质7**:扩充二叉树：除叶子结点外，其余结点都必须有两个孩子的二叉树。

# **五、二叉树的存储结构** #

二叉树的存储结构有顺序存储结构、链式存储结构  
**顺序存储：**结构采用一维数组存储的。根据二叉树的性质6可计算出双亲结点、左右孩子结点的下标。因此满二叉树、完全二叉树的存储可采用一维数组，把结点按从上到下、从左到右的顺序存放在数组中，结点之间的关系可由性质6的公式计算得到。  
**链式存储：**结构采用链表存储二叉树中的数据元素，用链建立二叉树中结点之间的关系。二叉树最常用的链式存储结构是二叉链，每个结点包含三个域，分别是数据元素域data、左孩子链域lChild和右孩子链域rChild。与单链表带头结点和不带头结点的两种情况相似，二叉链存储结构的二叉树也有带头结点和不带头结点两种

## **六、二叉树的遍历方式** ##

二叉树有四种遍历方式：前序，中序，后序和按层遍历

### 1、前序遍历 ###

先访问根节点，再先序遍历左子树，然后再先序遍历右子树。总的来说是根—左—右

### **2、中序遍历** ###

先中序访问左子树，然后访问根，最后中序访问右子树。总的来说是左—根—右

### **3、后序遍历** ###

先后序访问左子树，然后后序访问右子树，最后访问根。总的来说是左—右—根

## **4、层次遍历（宽度优先遍历）** ##

利用**队列**，依次将根，左子树，右子树存入队列，按照**队列**的**先进先出**规则来实现层次遍历。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTIzODcyNC8yMDE4MDYvMTIzODcyNC0yMDE4MDYwNjA5MjgxMDQ2OC0xNjMzMzM3Mzk5LmpwZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTIzODcyNC8yMDE4MDYvMTIzODcyNC0yMDE4MDYwNjA5MzY0NjAxMC0yMDgwNzk4NTU1LmpwZw?x-oss-process=image/format,png