二叉树

二叉树知识点总结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. 二叉树：每个节点最多只有两个子节点的树。

- 左子树：一个节点的左侧子树。

- 右子树：一个节点的右侧子树。

- 父节点：一个节点的直接上级节点。

- 子节点：一个节点的直接下级节点。

- 叶子节点：没有子节点的节点。

3. 二叉搜索树：一种特殊的二叉树，满足以下条件：
- 如果左子树不为空，则左子树上所有节点的值都小于该节点的值；
- 如果右子树不为空，则右子树上所有节点的值都大于该节点的值；
- 左右子树也都是二叉搜索树。

4. 完美二叉树：在一颗二叉树中，所有非叶子节点都有两个子节点，并且所有
叶子节点都位于同一层的二叉树。

5. 满二叉树：在一颗二叉树中，每个非叶子节点都有两个子节点，而且所有叶子节点都在同一层。

6. 完全二叉树：在一颗二叉树中，除了最后一层和可能的最后一个节点外，其它层的节点数都是满的，并且最后一层的节点都集中在该层的左侧。

7. 平衡二叉树：一种二叉搜索树，任意节点的两个子树的高度差不超过1。

二叉树基本知识：
1.二叉树的定义：二叉树是每个结点最多有两个子树的树结构，它有五种基本形态：
二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

2.二叉树的性质：若规定根结点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)
(i>0)个结点。

若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结
点数是2^K -1 (k >= 0)个。

对任何一颗二叉树，如果其叶子结点个数为n0，度为2的非叶子结点个数为n2，则有n0=n2+1。

3.二叉树的分类：二叉树有两大类，一是普通二叉树，二是特殊二叉树。

普通二叉树
是指除了满二叉树和完全二叉树之外的二叉树，特殊二叉树包括满二叉树和完全二叉树。

满二叉树是指所有层都完全填满的二叉树，而完全二叉树是指只有最下面两层结点度数可以小于2，并且最下面一层的叶子结点都位于本层中间位置的二叉树。

4.二叉树的遍历：二叉树的遍历主要有三种方法，分别是前序遍历、中序遍历和后序
遍历。

前序遍历是先访问根结点，然后遍历左子树，最后遍历右子树；中序遍历是先遍历左子树，然后访问根结点，最后遍历右子树；后序遍历是先遍历左子树，然后遍历右子树，最后访问根结点。

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

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

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

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

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

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

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

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

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

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

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

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

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

二叉树（Binary tree）是树形结构的一个重要类型。

许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。

当集合为空时，称该二叉树为空二叉树。

在二叉树中，一个元素也称作一个节点
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

二叉树是递归定义的，其节点有左右子树之分，逻辑上二叉树有五种基本形态：
1、空二叉树
2、2、只有一个根节点的二叉树
3、只有左子树
4、只有右子树
5、完全二叉树。

平衡树——特点：所有结点左右子树深度差≤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所指结点插入到右子树中。

二叉排序树的概念
二叉排序树，也称为二叉搜索树（Binary Search Tree，BST），是一种常用的数据结构，它具有以下特点：
1、结构特点：二叉排序树是一种二叉树，其中每个节点最多有两个子节点（左子节点和右子节点），且满足以下性质：
（1）左子树上的所有节点的值都小于根节点的值；
（2）右子树上的所有节点的值都大于根节点的值；
（3）左右子树都是二叉排序树。

2、排序特性：由于满足上述性质，二叉排序树的中序遍历结果是一个有序序列。

即，对二叉排序树进行中序遍历，可以得到一个递增（或递减）的有序序列。

3、查找操作：由于二叉排序树的排序特性，查找某个特定值的节点非常高效。

从根节点开始，比较目标值与当前节点的值的大小关系，根据大小关系选择左子树或右子树进行进一步的查找，直到找到目标值或者遍历到叶子节点为止。

4、插入和删除操作：插入操作将新节点按照排序规则插入到合适的位置，保持二叉排序树的特性；删除操作涉及节点的重新连接和调整，保持二叉排序树的特性。

二叉排序树的优点在于它提供了高效的查找操作，时间复杂度为O(log n)，其中n为二叉排序树中节点的个数。

它也可以支持其他常见的操作，如最小值和最大值查找、范围查找等。

然而，二叉排序树的性能受到数据的分布情况的影响。

当数据分
布不均匀时，树的高度可能会增加，导致查找操作的效率下降。

为了解决这个问题，可以采用平衡二叉树的变种，如红黑树、AVL 树等，以保持树的平衡性和性能。