二叉树（Binary Trees)

二叉树

---

通常在一棵树中，树中的每个节点可能有任意数量的子节点。二叉树是普通树的一个特例，在二叉树中，每个节点至多有俩个子节点，其中一个成为左子节点，另外一个称为右子节点。

二叉树的属性

---

1. 在非空二叉树中，第i层的结点总数不超过 $2^(i-1)$2(i−1) , i>=1；
2. 深度为h的二叉树最多有$2^h-1$2h−1个结点（h>=1),最少有h个节点
3. 对于任意一颗二叉树，如果其叶节点数为N0,而度数为2的节点总数为N2，则N0=N2+1;
4. 具有n个节点的完全二叉树的深度为$[log_2 n]+1$[log2​n]+1

二叉树的表现形式

---

可以使用两种形式来表示二叉树

二叉树的数组表现形式

---

二叉树存储在一个一维数组中，根节点位于索引为0的位置，然后从左到右从上到下对元素进行编号，即使元素为空，也存储在数组中。

将每个节点相对于树中的索引放入数组中。

二叉树的链式表现形式

---

使用链表的形式来存储二叉树，树中的每个节点包含三个字段，数据域、左节点指针域和右节点指针域。叶子节点的左右两个指针均指向NULL，表示树的末端。

二叉树的类型

---

1. 严格二叉树 一颗二叉树，其内部每个节点都有零个或者两个子节点，即树中的每个节点的度为0或者2
2. 完全二叉树 一颗二叉树，其内部每个节点恰好有两个子节点，且所有的叶节点都处于同一级
3. 扩充二叉树 通过使用虚拟节点来替换所有NULL子树来构成扩充二叉树。生成的树是一颗完全二叉树，其中每个节点刚好有两个子节点，每个外部节点都是一个叶子
4. 线索二叉树 在线索二叉树中，所有左侧为NULL的左指针都指向其有序的前置；所有右侧为NULL的指针均指向其有序的后继者。通过使用线索二叉树，使得树的遍历更加快速。

线索二叉树的两种变体

1. 单线索二叉树 如果存在右指针为空的节点，使其指向有序的后继者
2. 双线索二叉树 使其左右为NULL的指针分别指向有序的前驱和后继，此情况下，对于树的反向遍历是非常有用的

更多内容，欢迎访问：