树的性质和概念

淡淡的烟草味﹌ 2022-04-24 06:58 437阅读 0赞

### 文章目录 ###

*  树的概念和基本性质
 *   *  树简介
     *  树的概念
     *  树的特点
 *  二叉树
 *   *  定义：
     *  二叉树的五种基本形态
     *  满二叉树
     *  完全二叉树Complete Binary Tree
     *  二叉树的性质
 *  二叉树的遍历
 *   *  遍历类型：
     *   *  层序遍历
         *  深度优先遍历
 *  大顶堆和小顶堆

# 树的概念和基本性质 #

## 树简介 ##

*  树是一种非线性结构，
 *  树是n(n  ≥ \\geq ≥ 0)个元素的集合
    
     *  n = 0时，称为空树
     *  树只有一个特殊的没有前驱的元素，称为树的根Root
     *  树中除了根节点外，其余元素只能有一个前驱，可以有零个或多个后续
 *  递归定义
    
     *  树T是n(n  ≥ \\geq ≥ 0)个元素集合。n=0时，称为空树
     *  有且只有一个特殊元素根，剩余元素都可以被划分为m个互不相交的集合T1、T2、T3、…、Tm,而每一个集合都是树，称为T的子树Subtree
     *  字树也有自己的根

## 树的概念 ##

*  **结点**：树中的数据元素
 *  **结点的度degree**: 结点拥有的子树的数目称为度，记作d(v).
    
     *  树的度是树内部各结点的度的最大值。D结点度最大为3，树的度数就是3
 *  根据分支定义：
    
     *  **叶子节点** ：节点的度为0，称为叶子节点leaf、终端节点、末端结点。记作d(0)
     *  **分支结点**：结点度不为0，称为非终端节点或分支结点
     *  **分支**：结点之间的关系
     *  **内部结点**：除根节点外的分支节点，不包括叶子节点称为内部结点
 *  根据父子关系定义：
    
     *  **孩子结点（儿子Child结点）**：结点的子树的根结点成为该节点的孩子结点
     *  **双亲结点(父结点)**:一个结点是它各子树的根结点的双亲
     *  **兄弟结点**：具有相同双亲结点的结点
     *  **祖先结点**： 从根结点到该结点，经过分支上所有的结点。如下图中A、B、D都是G的祖先结点
     *  **子孙结点**： 结点的所有子树上的结点都称为该结点的子孙结点。如下图中B的子孙结点是D、G、H、I
     *  **堂兄弟**：双亲在同一层的结点
     *  **结点的层次(Level)**：根节点为第一层，根的孩子为第二层，以此内推，记作L(v)
     *  **树的深度（高度Depth）**:树的层次的最大值。下图的树深度为4
 *  其他定义：
    
     *  **有序树**：结点的子树是有顺序的（兄弟有大小，有先后次序），不能交换
     *  **无序树**：结点的子树是有无序的，可以交换
     *  **路径**：树中的k个结点n(1)，n(2),…n(k)，满足n(i)是n(i+1)的双亲,称为n(1)到n(k)的路径。就是一条线串下来的，前一个都是后一个的父结点，也称为前驱结点。
     *  **路径长度=路径上结点数-1，也是分支数**
     *  **森林**：m(m  g e q geq geq 0)棵不相交的树的集合。对于结点而言，其子树的集合就是森林。A结点的2棵子树的集合就是森林

## 树的特点 ##

*  树只有唯一一个根，且子树不相交
 *  除根以外，每个元素只能有一个前驱（父结点），可以有零个或多个后继(子结点)
 *  如果vi是vj的双亲，则L(vi) = L(vj)-1,也就是说双亲比孩子节点的层次小1
 *  注意： 堂兄弟的双亲，不一定是兄弟关系。因为：堂兄弟的定义是：双亲结点（父节点）是在同一层的结点。

![tree001][]

# 二叉树 #

## 定义： ##

*  每个结点最多2棵子树的树称为二叉树。
 *  二叉树是有序树，左子树，右子树是顺序的，不能交换次序
 *  即使某个结点只有一棵子树

## 二叉树的五种基本形态 ##

*  空二叉树
 *  只有一个根结点的二叉树
 *  根节点只有左子树的二叉树，又称为**左斜树**
 *  根节点只有右子树的二叉树，又称为**右斜树**
 *  根节点有左字树和右子树的二叉树

## 满二叉树 ##

*  一棵二叉树的所有分支结点都存在左子树和右子树，并且所有叶子节点只存在最下面一层
 *  同样深度二叉树中，满足二叉树结点最多。
 *  k为深度( 1  ≤ \\leq ≤ k  ≤ \\leq ≤ n),则结点总数为 2 k − 1 2^k-1 2k−1
 *  如下图，一个深度为4的15个结点的满二叉树  
    ![tree002][]

## 完全二叉树Complete Binary Tree ##

*  若二叉树的深度为k，二叉树的层次数从1到k-1层的结点数都达到了最大个数，在第k层的所有结点都集中在最左边，这就是完全二叉树
 *  完全二叉树由满二叉树引出
 *  满二叉树**一定**是完全二叉树，但完全二叉树**不一定**是满二叉树
 *  k为深度(1  ≤ \\leq ≤ k  ≤ \\leq ≤ n ),结点总数最大值为 2 k − 1 2^k-1 2k−1。当达到最大值的时候就是满二叉树
 *  例如：下图1,2,3都是完全二叉树，最下一层的叶子节点都连续的集中在最左边
    
     *  图1：完全二叉树  
        ![tree003][]
     *  图2：完全二叉树  
        ![tree004][]
     *  图3：完全二叉树  
        ![tree005][]

## 二叉树的性质 ##

*  **性质一**：在二叉树的第i层上至多有 2 i − 1 2^\{i-1\} 2i−1个结点（i  ≥ \\geq ≥ 1）
 *  **性质二**：深度为k的二叉树，至多有 2 k − 1 2^k-1 2k−1个结点（k  ≥ \\geq ≥ 1）
 *  **性质三**: 对任何一颗二叉树T，如果其终端节点（度数为0的结点)数为n0,度数为2的结点为n2,则有n0=n2+1
    
     *  换句话说，就是叶子节点数-1就等于度数为2的结点数
     *  证明：  
        ![tree006][]
 *  **性质四**： 具有n个结点的完全二叉树的深度为int( l o g 2 n log\_2n log2n)+1或者math.ceil( l o g 2 ( n + 1 ) log\_2\{(n+1)\} log2(n\+1))
    
     *  高度为k的二叉树，至少有k个结点
     *  含有n(n  ≥ \\geq ≥ 1)个结点的二叉树高度至多为n。最小为math.ceil(  l o g 2 ( n + 1 ) log\_2\{(n+1)\} log2(n\+1) ),不小于对数值的最小整数，向上取整。
        
         *  假设高度为h， 2 h − 1 = n 则 有 h = l o g 2 ( n + 1 ) 2^h-1 = n 则有 h =log\_2\{(n+1)\} 2h−1=n则有h=log2(n\+1),层次数是取整。如果是8个结点，3.1699就要向上取整为4，为4层
 *  **性质五**：对于有序二叉树，假定i位结点编号，该二叉树的所有结点为n，如果i=1为二叉树的根结点。那么当2i>n时说明结点i无左右孩子结点。即结点i无子节点。如果2i+1>n时，说明结点i无右孩子结点。
    
     *  如果有一棵n个结点的完全二叉树（深度为int( l o g 2 n log\_2n log2n)+1），结点按照层顺序编号，如图：  
        ![tree007][]
     *  如果i=1，则结点i是二叉树的根，无双亲（无父节点）；如果i>1,则其双亲是int(i/2),向下取整。就是子节点的编号整除2得到的就是父结点的编号。父结点如果是i,那么左孩子节点就是2i,右孩子结点就是2i+1.
     *  如果2i>n,则结点i无左孩子，即结点i为叶子结点；否则其左孩子结点存在编号为2i.
     *  如果2i+1>n，则结点i无右孩子，（注意这里并不能说明结点i没有左孩子）

# 二叉树的遍历 #

*  遍历：迭代所有元素一遍
 *  数的遍历：对树中所有元素不重复地访问一遍，也称作扫描

## 遍历类型： ##

*  广度优先遍历
    
     *  层序遍历
 *  深度优先遍历
    
     *  前序遍历
     *  中序遍历
     *  后序遍历
 *  遍历序列：将树中所有元素遍历一遍后，得到的元素的序列。将层次结构转换成了线性结构

### 层序遍历 ###

*  按照树的层次，从第一层开始，自左向右遍历元素
    
     *  例如遍历序列\[A,B,C,D,E,F,G,H,I\]  
        ![tree008][]

### 深度优先遍历 ###

*  设树的根结点为D,左子树为L,右子树为R,且要求L一定在R之前，则有下面几种遍历方式：
    
     *  前序遍历，也叫先序遍历、也叫先根遍历，DLR
     *  中序遍历，也叫中根遍历，LDR
     *  后序遍历，也叫后根遍历，LRD

1.  **前序遍历DLR**
    
     *  从根结点开始，先左子树后右子树
     *  每个子树内部依然是先根结点，再左子树后右字树。递归遍历
     *  例如:遍历序列：A BDGH CEIF  
        ![tree009][]
2.  **中序遍历LDR**
    
     *  从根结点的左子树开始遍历，然后是根节点，再右字树
     *  每个子树内部，也就是先左字树，后根节点，再右字树。递归遍历
     *  例如：左图遍历：GDHB A IECF。右图遍历：GDHB A EICF  
        ![tree010][]
3.  **后序比那里LRD**
    
     *  先左字树，后右字树，再根节点
     *  每一个字树内部依然是先左字树，后右字树，再根节点。递归遍历
     *  例如：遍历序列：GHDB IEFC A  
        ![tree011][]

# 大顶堆和小顶堆 #

*  大顶堆
    
    1.  完全二叉树的每个非叶子节点都要大于或者等于其左右孩子结点的值称为**大顶堆**
    2.  根节点一定是大顶堆中的最大值  
        ![tree012][]
 *  小顶堆
    
    1.  完全二叉树的每个非叶子节点都要小于或者等于其左右孩子结点的值称为**小顶堆**
    2.  根结点一定是小顶堆中的最小值  
        ![tree013][]

[tree001]: https://raw.githubusercontent.com/1263351411/xdd.github.io/master/img/tree001.jpg
[tree002]: https://raw.githubusercontent.com/1263351411/xdd.github.io/master/img/tree002.jpg
[tree003]: /images/20220218/1783456bef044b5890ff3aea102b8b85.png
[tree004]: /images/20220218/5888471671f34247bb1833502a59be08.png
[tree005]: /images/20220218/57fc8cb1ed184aa78d032d3623fd4099.png
[tree006]: /images/20220218/20aea1c4ad28488dac198d3aec41752b.png
[tree007]: /images/20220218/8c086757a2f7450c832cc85ca2691c82.png
[tree008]: /images/20220218/04be8da364af4ca6a1579edfd31052ce.png
[tree009]: /images/20220218/b711d42e759c4dc49e05bab2fe7c621a.png
[tree010]: /images/20220218/af43fd84828b478cadf2b28ccbf319c1.png
[tree011]: /images/20220218/2de8d71a5bdd4e69abac38a14cb52745.png
[tree012]: /images/20220218/3ac046761e424985aebee6e57787c8a4.png
[tree013]: /images/20220218/78aecd7b8f534288b8ab0588b2fc1d6d.png