本文主要是介绍树（Tree）——《啊哈！算法》，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
树
什么是树？树是一种特殊的图，不包含回路的连通无向树。
正因为树有着“不包含回路”这个特点，所以树就被赋予了很多特性。
- 一棵树中的任意两个结点有且仅有唯一的一条路径连通。
- 一棵树如果有n个结点，那么它一定恰好有n-1条边。
- 在一棵树中加一条边将会构成一个回路。
一棵树有且只有一个根结点。
- 没有父结点的结点称为根结点（祖先）。
- 没有子结点的结点称为叶结点。
- 如果一个结点既不是根结点也不是叶结点，称为内部结点。
二叉树
二叉树是一种特殊的树。二叉树的特点是每个结点最多有两个儿子，左边的叫做左儿子，右边的叫做右儿子，或者说每个结点最多只有两棵子树。
严格的递归定义：二叉树要么为空，要么由根结点、左子树和右子树组成，而左子树和右子树分别是一棵二叉树。
有两种特殊的二叉树：
- 如果二叉树中每个内部结点都有两个儿子，这样的二叉树叫做满二叉树。一棵深度为h且有(2^h)-1个结点的二叉树。
- 如果一棵二叉树除了最右边位置上有一个或者几个叶结点缺少外，其他都是丰满的，那么这样的二叉树叫做完全二叉树。若设二叉树的高度为h，除了第h层外，其他各层（1~h-1）的结点数都达到最大个数，第h层从右向左连续缺若干结点。
满二叉树是一种特殊的或者极其完美的完全二叉树。
堆
一种特殊的完全二叉树。
- 如果所有父结点比子结点小，称为最小堆。
- 如果所有父结点比子节点大，称为最大堆。
二叉查找树（二叉排序树）
- 左子树上所有的结点的值均小于或者等于它的根结点的值
- 有子树上所有的结点的值均大于或者等于它的根节点的值
- 左右子树也一定分别为二叉查找树
红黑树（平衡二叉查找树）
防止单链查找树的出现。
- 结点是红色或者黑色
- 根结点是黑色
- 每个叶子结点都是黑色的空结点（NULL）
- 每个红色结点的两个子结点都是黑色的
- 从任意结点到其每个叶子节点的所有路径都包含相同的黑色节点。
通过变色和旋转（左、右）调整和维持红黑树平衡。
变色
为了重新符合红黑树的规则，尝试把红色结点变为黑色，或者把黑色结点变为红色。
左旋转
逆时针旋转红黑树的两个结点，使得父结点被自己的右孩子取代，而自己成为自己的左孩子。
右旋转
顺时针旋转红黑树的两个结点，使得父结点被自己的左孩子取代，而自己成为自己的右孩子
这篇关于树（Tree）——《啊哈！算法》的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
