本期是C++基础语法分享的第十四节，今天给大家来梳理一下树！

二叉树

BinaryTree.cpp：

性质

（1）非空二叉树第 i 层最多 2(i-1) 个结点 （i >= 1）

（2）深度为 k 的二叉树最多 2k - 1 个结点 （k >= 1）

（3）度为 0 的结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1

（4）有 n 个结点的完全二叉树深度 k = ⌊ log2(n) ⌋ + 1

（5）对于含 n 个结点的完全二叉树中编号为 i （1 <= i <= n） 的结点

a.若 i = 1，为根，否则双亲为 ⌊ i / 2 ⌋

b.若 2i > n，则 i 结点没有左孩子，否则孩子编号为 2i

c.若 2i + 1 > n，则 i 结点没有右孩子，否则孩子编号为 2i + 1

存储结构

二叉树数据结构

顺序存储

二叉树顺序存储图片

链式存储

二叉树链式存储图片

遍历方式

a.先序遍历

b.中序遍历

c.后续遍历

d.层次遍历

分类

（1）满二叉树

（2）完全二叉树（堆）

        大顶堆：根 >= 左 && 根 >= 右

        小顶堆：根 <= 左 && 根 <= 右

（3）二叉查找树（二叉排序树）：左 < 根 < 右

（4）平衡二叉树（AVL树）：| 左子树树高 - 右子树树高 | <= 1

（5）最小失衡树：平衡二叉树插入新结点导致失衡的子树：调整：

        LL型：根的左孩子右旋

        RR型：根的右孩子左旋

        LR型：根的左孩子左旋，再右旋

        RL型：右孩子的左子树，先右旋，再左旋

其他树及森林

1、树的存储结构

（1）双亲表示法

（2）双亲孩子表示法

（3）孩子兄弟表示法

并查集

一种不相交的子集所构成的集合 S = {S1, S2, ..., Sn}

2、平衡二叉树（AVL树）

性质

（1）| 左子树树高 - 右子树树高 | <= 1

（2）平衡二叉树必定是二叉搜索树，反之则不一定

（3）最小二叉平衡树的节点的公式：F(n)=F(n-1)+F(n-2)+1 （1 是根节点，F(n-1) 是左子树的节点数量，F(n-2) 是右子树的节点数量）

平衡二叉树图片

最小失衡树

平衡二叉树插入新结点导致失衡的子树

调整：

LL 型：根的左孩子右旋

RR 型：根的右孩子左旋

LR 型：根的左孩子左旋，再右旋

RL 型：右孩子的左子树，先右旋，再左旋

3、红黑树

RedBlackTree.cpp：

红黑树的特征是什么？

（1）节点是红色或黑色。

（2）根是黑色。

（3）所有叶子都是黑色（叶子是 NIL 节点）。

（4）每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）（新增节点的父节点必须相同）

（5）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。（新增节点必须为红）

调整

（1）变色

（2）左旋

（3）右旋

应用

关联数组：如 STL 中的 map、set

红黑树、B 树、B+ 树的区别？

（1）红黑树的深度比较大，而 B 树和 B+ 树的深度则相对要小一些

（2）B+ 树则将数据都保存在叶子节点，同时通过链表的形式将他们连接在一起。

B 树（B-tree）、B+ 树（B+-tree）

特点

一般化的二叉查找树（binary search tree）

“矮胖”，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先定义好）

应用

大部分文件系统、数据库系统都采用B树、B+树作为索引结构

区别

B+树中只有叶子节点会带有指向记录的指针（ROWID），而B树则所有节点都带有，在内部节点出现的索引项不会再出现在叶子节点中。

B+树中所有叶子节点都是通过指针连接在一起，而B树不会。

B树的优点

对于在内部节点的数据，可直接得到，不必根据叶子节点来定位。

B+树的优点

非叶子节点不会带上 ROWID，这样，一个块中可以容纳更多的索引项，一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。

叶子节点之间通过指针来连接，范围扫描将十分简单，而对于B树来说，则需要在叶子节点和内部节点不停的往返移动。

B 树、B+ 树区别来自：differences-between-b-trees-and-b-trees、B树和B+树的区别

八叉树

八叉树图片

八叉树（octree），或称八元树，是一种用于描述三维空间（划分空间）的树状数据结构。八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心。

用途

三维计算机图形

最邻近搜索

今天的分享就到这里了，大家要好好学C++哟~

写在最后：对于准备学习C/C++编程的小伙伴，如果你想更好的提升你的编程核心能力（内功）不妨从现在开始！

微信公众号：C语言编程学习基地

整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）

欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！