二叉树

二叉树知识点总结1. 二叉树的性质1.1 二叉树的性质一：二叉树的深度二叉树的深度是指从根节点到叶子节点的最长路径长度。

对于一个空树而言，它的深度为0；对于只有一个根节点的树而言，它的深度为1。

根据定义可知，深度为k的二叉树中，叶子节点的深度值为k。

由此可知，二叉树的深度为所有叶子节点深度的最大值。

1.2 二叉树的性质二：二叉树的高度二叉树的高度是指从根节点到叶子节点的最短路径长度。

对于一个空树而言，它的高度为0；对于只有一个根节点的树而言，它的高度为1。

由此可知，二叉树的高度总是比深度大一。

1.3 二叉树的性质三：二叉树的节点数量对于一个深度为k的二叉树而言，它最多包含2^k - 1个节点。

而对于一个拥有n个节点的二叉树而言，它的深度最多为log2(n+1)。

1.4 二叉树的性质四：满二叉树满二叉树是一种特殊类型的二叉树，它的每个节点要么是叶子节点，要么拥有两个子节点。

满二叉树的性质是：对于深度为k的满二叉树而言，它的节点数量一定是2^k - 1。

1.5 二叉树的性质五：完全二叉树完全二叉树是一种特殊类型的二叉树，它的所有叶子节点都集中在树的最低两层，并且最后一层的叶子节点从左到右依次排列。

对于一个深度为k的完全二叉树而言，它的节点数量一定在2^(k-1)和2^k之间。

2. 二叉树的遍历二叉树的遍历是指按照一定的顺序访问二叉树的所有节点。

二叉树的遍历主要包括前序遍历、中序遍历和后序遍历三种。

2.1 前序遍历（Pre-order traversal）前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

对于一个二叉树而言，前序遍历的结果就是按照“根-左-右”的顺序访问所有节点。

2.2 中序遍历（In-order traversal）中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

对于一个二叉树而言，中序遍历的结果就是按照“左-根-右”的顺序访问所有节点。

2.3 后序遍历（Post-order traversal）后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

基本二叉树知识讲解一、有关二叉树的学习性质1：二叉树上叶子结点数等于度为2的结点数加1。

性质2：二叉树的第i层上至多有2的i次方减1个结点（i>=1）。

性质3：深度为h的二叉树至多有2的h次方减1个结点。

满二叉树：在一棵二叉树中，当第i层的结点树为2的i次方减1个时，称此层的结点数是满的。

当一棵二叉树中的每一层都满时，称此树为满二叉树。

特性：除叶子结点以外的其他的结点的度皆为2，且叶子结点在同一层上。

深度为h的满二叉树中的结点数为2的h次方减1。

性质4：设含有n个结点的完全二叉树的深度为k，则k=(int)(log2n)+1,即深度k等于log2n的整数部分再加1。

二叉树的存储结构1：顺序存储结构二叉树的顺序存储结构类型定义如下：#define TREEMINSIZE 10typedef struct{BTreeDT(数据类型) *base;int spacesize;BTreeDT nullvalue;}SeqTree;2：链式存储结构（一般的二叉树主要采用链式存储结构通常有二叉链表和三叉链表两种形式）1>二叉链表存储结构二叉链表中的每个结点由data，lchild和rchild三个域组成，定义如下：typedef struct bkbtnode{BTreeDT data;struct bkbtnode *lchild;struct bkbtnode *rchild;}BTNode,*BKBTree;在二叉链表中，查找某结点的孩子很容易实现，但查找某结点的双亲不方便。

一棵喊有n个结点的二叉树采用二叉链表存储时，将有2n-（n-1）=n+1个指针域是空的。

2>三叉链表存储结构typedef struct tkbtnode{BTreeDT data;struct tkbtnode *lchild;struct tkbtnode *rchild;struct tkbtnode *parent;}TKBTNode,*TKBTree;其中，parent域存放该结点双亲的指针。

数据结构之⼆叉树（BinaryTree）⽬录导读 ⼆叉树是⼀种很常见的数据结构，但要注意的是，⼆叉树并不是树的特殊情况，⼆叉树与树是两种不⼀样的数据结构。

⽬录 ⼀、⼆叉树的定义 ⼆、⼆叉树为何不是特殊的树 三、⼆叉树的五种基本形态 四、⼆叉树相关术语 五、⼆叉树的主要性质（6个） 六、⼆叉树的存储结构（2种） 七、⼆叉树的遍历算法（4种） ⼋、⼆叉树的基本应⽤：⼆叉排序树、平衡⼆叉树、赫夫曼树及赫夫曼编码⼀、⼆叉树的定义 如果你知道树的定义（有限个结点组成的具有层次关系的集合），那么就很好理解⼆叉树了。

定义：⼆叉树是n(n≥0)个结点的有限集，⼆叉树是每个结点最多有两个⼦树的树结构，它由⼀个根结点及左⼦树和右⼦树组成。

（这⾥的左⼦树和右⼦树也是⼆叉树）。

值得注意的是，⼆叉树和“度⾄多为2的有序树”⼏乎⼀样，但，⼆叉树不是树的特殊情形。

具体分析如下⼆、⼆叉树为何不是特殊的树 1、⼆叉树与⽆序树不同 ⼆叉树的⼦树有左右之分，不能颠倒。

⽆序树的⼦树⽆左右之分。

2、⼆叉树与有序树也不同（关键） 当有序树有两个⼦树时，确实可以看做⼀颗⼆叉树，但当只有⼀个⼦树时，就没有了左右之分，如图所⽰：三、⼆叉树的五种基本状态四、⼆叉树相关术语是满⼆叉树；⽽国际定义为，不存在度为1的结点，即结点的度要么为2要么为0，这样的⼆叉树就称为满⼆叉树。

这两种概念完全不同，既然在国内，我们就默认第⼀种定义就好）。

完全⼆叉树：如果将⼀颗深度为K的⼆叉树按从上到下、从左到右的顺序进⾏编号，如果各结点的编号与深度为K的满⼆叉树相同位置的编号完全对应，那么这就是⼀颗完全⼆叉树。

如图所⽰：五、⼆叉树的主要性质 ⼆叉树的性质是基于它的结构⽽得来的，这些性质不必死记，使⽤到再查询或者⾃⼰根据⼆叉树结构进⾏推理即可。

性质1：⾮空⼆叉树的叶⼦结点数等于双分⽀结点数加1。

证明：设⼆叉树的叶⼦结点数为X，单分⽀结点数为Y，双分⽀结点数为Z。

二叉树的几种基本形态二叉树是一种重要的数据结构，在计算机科学和数据结构领域有着广泛的应用。

它由节点和边组成，每个节点最多有两个子节点。

根据节点和边的组合方式，我们可以将二叉树分为几种基本形态。

一、满二叉树满二叉树是指一个二叉树的每个节点都有两个子节点，除了叶子节点。

叶子节点是指没有子节点的节点。

满二叉树是一种特殊的完全二叉树，它的深度为h，节点个数为2^h - 1。

满二叉树具有以下特点：1. 每个节点都有两个子节点，除了叶子节点；2. 所有叶子节点都在同一层；3. 每个非叶子节点都有两个子节点；4. 节点个数为2^h - 1，其中h为深度。

满二叉树的应用非常广泛，例如在堆排序中，堆通常就是满二叉树。

二、完全二叉树完全二叉树是指除了最后一层节点可能不满外，其他层节点都是满的二叉树。

在最后一层，所有的节点都集中在左边。

完全二叉树具有以下特点：1. 最后一层的节点都集中在左边；2. 其他层节点都是满的；3. 如果一个节点有右子节点，则一定有左子节点；4. 节点个数最少为2^(h-1)，最多为2^h - 1，其中h为深度。

完全二叉树的应用也非常广泛，例如在二叉堆中，堆通常就是完全二叉树。

三、二叉搜索树二叉搜索树是一种特殊的二叉树，它的左子树中所有节点的值都小于根节点的值，右子树中所有节点的值都大于根节点的值。

同样的规则也适用于每个子树。

二叉搜索树具有以下特点：1. 左子树中所有节点的值都小于根节点的值；2. 右子树中所有节点的值都大于根节点的值；3. 每个子树都符合上述规则；4. 不存在相同节点。

二叉搜索树的应用也非常广泛，例如在数据库中，索引通常就是基于二叉搜索树实现的。

四、平衡二叉树平衡二叉树也称为AVL树，它是一种特殊的二叉搜索树，它的左子树和右子树的高度差不超过1。

这种平衡可以保证二叉树的查找、插入、删除等操作的时间复杂度都是O(log n)。

平衡二叉树具有以下特点：1. 左子树和右子树的高度差不超过1；2. 每个子树都符合上述规则；3. 它是一种特殊的二叉搜索树。

平衡树——特点：所有结点左右子树深度差≤1排序树——特点：所有结点―左小右大字典树——由字符串构成的二叉排序树判定树——特点：分支查找树（例如12个球如何只称3次便分出轻重）带权树——特点：路径带权值（例如长度）最优树——是带权路径长度最短的树，又称Huffman树，用途之一是通信中的压缩编码。

1.1 二叉排序树：或是一棵空树；或者是具有如下性质的非空二叉树：（1）若左子树不为空，左子树的所有结点的值均小于根的值；（2）若右子树不为空，右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。

例：二叉排序树如图9.7：二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。

中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。

搜索,插入,删除的复杂度等于树高，期望O(logn),最坏O(n)(数列有序,树退化成线性表).虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法.2.2 二叉排序树b中查找在二叉排序树b中查找x的过程为：1. 若b是空树，则搜索失败，否则：2. 若x等于b的根节点的数据域之值，则查找成功；否则：3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：4. 查找右子树。

[cpp]view plaincopyprint?1.Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){2. //在根指针T所指二叉排序樹中递归地查找其关键字等于key的数据元素，若查找成功，3. //则指针p指向该数据元素节点，并返回TRUE，否则指针P指向查找路径上访问的4. //最好一个节点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL5. if(!T){ p=f; return FALSE;} //查找不成功6. else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功7. else if LT(key,T->data.key)8. return SearchBST(T->lchild, key, T, p); //在左子树继续查找9. else return SearchBST(T->rchild, key, T, p); //在右子树继续查找10.}2.3 在二叉排序树插入结点的算法向一个二叉排序树b中插入一个结点s的算法，过程为：1. 若b是空树，则将s所指结点作为根结点插入，否则：2. 若s->data等于b的根结点的数据域之值，则返回，否则：3. 若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：4. 把s所指结点插入到右子树中。

简述二叉树的五种形态二叉树是一种常用的数据结构，它由节点组成，每个节点最多有两个子节点。

根据节点的分布情况，二叉树可以分为五种形态，分别是满二叉树、完全二叉树、平衡二叉树、搜索二叉树和线索二叉树。

一、满二叉树满二叉树是指除了叶子节点外，每个节点都有两个子节点的二叉树。

也就是说，满二叉树的所有层都是满的，并且最后一层的叶子节点都靠左排列。

满二叉树的节点数可以通过公式计算得到，假设树的高度为h，则节点数为2^h - 1。

满二叉树的特点是结构简单，查找速度快。

在满二叉树中，任意两个节点的路径长度都相同。

二、完全二叉树完全二叉树是指除了最后一层之外，其他层都是满的，并且最后一层的叶子节点都靠左排列的二叉树。

完全二叉树的特点是节点数较少，结构相对简单。

完全二叉树通常用数组来表示，因为它的节点之间的关系可以通过数组的下标来表示。

在完全二叉树中，任意一个节点的左子节点的下标为2i，右子节点的下标为2i+1。

三、平衡二叉树平衡二叉树是指左右子树的高度差不超过1的二叉树。

平衡二叉树的特点是查找、插入和删除的时间复杂度都为O(logn)，其中n是节点的数量。

平衡二叉树的高度可以通过节点的平衡因子来计算，平衡因子定义为左子树的高度减去右子树的高度。

平衡因子的取值范围为-1、0和1，当平衡因子的绝对值大于1时，需要通过旋转操作来调整树的平衡性。

四、搜索二叉树搜索二叉树，也称为二叉搜索树或排序二叉树，是一种特殊的二叉树。

它的特点是对于树中的任意一个节点，其左子树中的所有节点都小于它，右子树中的所有节点都大于它。

搜索二叉树的中序遍历结果是一个递增的有序序列。

搜索二叉树的特点是可以快速地查找某个节点，时间复杂度为O(logn)，其中n是节点的数量。

但是，如果搜索二叉树不平衡，即左子树或右子树过深，则会导致查找的时间复杂度退化为O(n)。

五、线索二叉树线索二叉树是对二叉树进行了优化的数据结构，它通过添加指向前驱和后继节点的线索，使得遍历操作更加高效。

计算机二级二叉树1. 概述二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点。

在计算机科学中，二叉树有着广泛的应用，例如在算法和数据存储中都能够发挥重要作用。

本文将介绍计算机二级二叉树的基本概念、性质以及相关操作。

2. 二叉树的定义二叉树是一种有序树，其中每个节点最多有两个子节点。

它通常用来表示层次关系、排序关系、树形结构等。

二叉树的子节点分为左子节点和右子节点，子节点的顺序是固定的。

3. 二叉树的性质(1) 二叉树的第i层最多有2^(i-1)个节点。

(2) 深度为k的二叉树最多有2^k-1个节点。

(3) 对于任意一棵二叉树，如果其叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。

(4) 对于完全二叉树，假设其深度为h，则其节点数为2^h-1（h≥1）。

4. 二叉树的遍历二叉树的遍历主要分为前序遍历、中序遍历和后序遍历。

下面分别介绍这三种遍历方式的定义和实现。

(1) 前序遍历：遍历顺序为根节点、左子树、右子树。

(2) 中序遍历：遍历顺序为左子树、根节点、右子树。

(3) 后序遍历：遍历顺序为左子树、右子树、根节点。

二叉树的遍历可以用递归或者迭代的方法实现。

5. 二叉树的插入在二叉树中插入节点是一种常见的操作。

下面介绍一种基本的插入算法：(1) 如果树为空，则将节点作为根节点插入。

(2) 如果树不为空：- 将节点与根节点进行比较，若小于根节点，则插入到左子树中。

- 若大于根节点，则插入到右子树中。

- 对左子树或右子树递归执行插入操作。

6. 二叉树的删除二叉树的删除操作比插入操作稍微复杂一些。

一般情况下，可以按照以下步骤进行删除：(1) 如果要删除的节点是叶子节点，直接删除即可。

(2) 如果要删除的节点只有一个子节点，将其子节点代替要删除的节点。

(3) 如果要删除的节点有两个子节点，则需要找到其右子树中的最小节点（或左子树中的最大节点）来代替要删除的节点，并删除那个最小节点。

7. 二叉树的应用二叉树在计算机科学中有着广泛的应用，下面介绍几种常见的应用场景：(1) 搜索二叉树：可以在O(log n)的时间复杂度内进行搜索操作。

数据结构二叉树知识点总结二叉树是指每个节点最多有两个子节点的树结构。

它是一种重要的数据结构，在算法和程序设计中被广泛应用。

下面是对二叉树的主要知识点进行详细总结。

1.二叉树的基本概念：-树节点：树的基本单元，包含数据项（节点值）和指向其他节点的指针。

-根节点：树的第一个节点。

-叶节点（又称为终端节点）：没有子节点的节点。

-子节点：一些节点的下一级节点。

-父节点：一些节点的上一级节点。

-兄弟节点：拥有同一父节点的节点。

-深度：从根节点到当前节点的路径长度。

-高度：从当前节点到最远叶节点的路径长度。

2.二叉树的分类：-严格二叉树：每个节点要么没有子节点，要么有两个子节点。

-完全二叉树：除了最后一层外，其他层的节点数都达到最大，并且最后一层的节点依次从左到右排列。

-满二叉树：每个节点要么没有子节点，要么有两个子节点，并且所有叶节点都在同一层上。

-平衡二叉树：任意节点的两棵子树的高度差不超过13.二叉树的遍历：-前序遍历：根节点->左子树->右子树。

递归实现时，先访问当前节点，然后递归遍历左子树和右子树。

-中序遍历：左子树->根节点->右子树。

递归实现时，先递归遍历左子树，然后访问当前节点，最后递归遍历右子树。

-后序遍历：左子树->右子树->根节点。

递归实现时，先递归遍历左子树，然后递归遍历右子树，最后访问当前节点。

-层序遍历：从上到下，从左到右依次访问每个节点。

使用队列实现。

4.二叉查找树（BST）：-二叉查找树是一种有序的二叉树，对于树中的每个节点，其左子树的节点的值都小于当前节点的值，右子树的节点的值都大于当前节点的值。

-插入操作：从根节点开始，递归地比较要插入的值和当前节点的值，根据比较结果向左或向右移动，直到找到插入位置为止。

-查找操作：从根节点开始，递归地比较要查找的值和当前节点的值，根据比较结果向左或向右移动，直到找到目标节点或到叶节点。

-删除操作：有三种情况：-被删除节点是叶节点：直接将其删除。

二叉树的基本概念一、引言二叉树是计算机科学中最基础的数据结构之一，它是由节点和边组成的树形结构，其中每个节点最多有两个子节点。

在计算机科学中，二叉树被广泛应用于搜索、排序、编译器等领域。

本文将详细介绍二叉树的基本概念。

二、定义二叉树是一种特殊的树形结构，其中每个节点最多有两个子节点。

通常将左子节点称为左子树，右子节点称为右子树。

三、基本术语1. 根节点：二叉树的顶层节点称为根节点。

2. 叶子节点：没有任何子节点的节点称为叶子节点。

3. 父节点和子节点：一个父亲可以有多个儿子，但是一个儿子只能有一个父亲。

4. 兄弟：具有相同父亲的两个或多个儿子称为兄弟。

5. 深度：从根到某个节点所经过的边数称为该节点的深度。

6. 高度：从某个节点到其所有后代中深度最大者加一（即包括该结点）称为该结点所在的二叉树的高度。

四、分类1. 满二叉树：一棵深度为k且有2^k-1个节点的二叉树称为满二叉树。

2. 完全二叉树：对于一棵深度为k的，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称之为完全二叉树。

3. 平衡二叉树：平衡二叉树也称为AVL树，是一种自平衡的排序二叉搜索树。

它具有以下性质：左右子树高度差不超过1，并且左右子树也是平衡二叉树。

五、遍历遍历是指按照某种顺序访问每个节点。

常见的遍历方式有三种：1. 前序遍历（Pre-order）：先访问当前节点，再依次遍历左子树和右子树。

2. 中序遍历（In-order）：先依次遍历左子树，再访问当前节点，最后遍历右子树。

3. 后序遍历（Post-order）：先依次遍历左子树和右子树，最后访问当前节点。

六、应用1. 搜索算法：在搜索算法中，二叉树被广泛应用于二分查找。

2. 排序算法：在排序算法中，二叉树被广泛应用于堆排序和快速排序。

3. 编译器：在编译器中，二叉树被广泛应用于语法分析和代码生成。

七、总结本文介绍了二叉树的基本概念、术语、分类、遍历以及应用。

【二叉树的定义】（ binary tree）是 n 个结点的有限集合，该集合或为空集（空二叉树），或由一个根结点与两棵互不相二叉树（右子树的二叉树构成。

交的，称为根结点的左子树左子树、右子树二叉树的特点是：每个结点最多有两棵子树，故二叉树中不存在度大于 2 的结点二叉树是有序的，其次序不能任意颠倒，即使树中的某个结点只有一棵子树，也要区分它是左子树还是右子树二叉树具有以下 5 种基本形态：【特殊的二叉树】在实际应用中，常会用到以下几种特殊的二叉树。

1.斜树右斜树左斜树，所有的结点都只有右子树的二叉树称为右斜树所有的结点都只有左子树的二叉树称为左斜树在斜树中，每层只有一个结点，因此斜树的结点个数与其深度相同2.满二叉树满二叉树。

在一棵二叉树中，若所有的分支结点都存在左子树和右子树，且所有的叶子都在同一层上，则称为满二叉树其特点是：叶子只能出现在最下一层只有度为 0、度为 2 的结点满二叉树在同样深度的二叉树中结点个数、叶结点个数最多。

由于满二叉树的特性可知：满二叉树在同样深度的二叉树中结点个数、叶结点个数最多。

3.完全二叉树对一棵具 n 个结点的二叉树按层序编号，若编号为 i 的结点与同样深度的满二叉树中编号 i 的结点在二叉树中的满二叉树是完全二叉树位置完全相同，则称为完全二叉树完全二叉树，那么显然有：满二叉树是完全二叉树其特点是：叶结点只能出现在最下两层，且最下层的叶结点都集中在二叉树左侧连续的位置若有度为 1 的结点，只可能有一个，且其只有左孩子深度为 k 的完全二叉树在 k -1 层上行一定是满二叉树简单来说，在满二叉树中，从最后一个结点开始，连续去掉任意个的结点，即是一棵完全二叉树【二叉树的性质】1.二叉树二叉树的第 i 层上行最多有个结点2.二叉树中，最多有个结点，最少有 k 个结点在一棵深度为 k 的二叉树推论：深度为 k 且具个结点的二叉树一定是满二叉树，但深度为 k 具有 k 个结点的二叉树不一定是斜树3.具有 n 个结点的二叉树二叉树，其分支数：B=n-1，对于任意一个结点，每度贡献一个分支，即：度为 0 的结点贡献 0 个分支，度为 1 的结点贡献 1 个分支，度为 2 的结点贡献 2 个分支。

二叉树的定义、定义、存储二叉树的定义二叉树是每个节点最多有两个子树的树结构。

通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

特殊二叉树1. 斜树所有结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树。

斜树的每一层都只有一个结点，结点的个数与斜树的深度相同。

2. 满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。

（上图中所示的二叉树，就是一棵满二叉树）3. 完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中的编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。

（数学归纳法可证）性质2：深度为k的二叉树最多有2k-1个结点（k≥1）。

（由性质1，通过等比数列求和可证）性质3：一棵二叉树的叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。

证：结点总数n = n0 + n1 + n2。

设B为分支总数，因为除根节点外，其余结点都有一个分支进入，所以n = B + 1。

又因为分支是由度为1或2的结点射出，所以B = n1 + 2n2。

综上：n = n0 + n1 + n2 = B + 1 = n1 + 2n2 + 1，得出：n0 = n2 + 1。

性质4：具有n个结点的完全二叉树的深度为floor(log2n) + 1 。

性质5：如果对一棵有n个结点的完全二叉树（其深度为floor(log2n) + 1 ）的结点按层序编号，则对任一结点i（1≤i≤n）有：（1）如果i = 1，则结点i是二叉树的根，无双亲；如果i > 1，则其双亲PARENT(i)是结点 floor((i)/2)。