本文转载自微信公众号“小明菜市场”，作者小明菜市场。转载本文请联系小明菜市场公众号。你好！我是晓晓。今天总结一下什么是树，以及关于树的一些内容。.树树是一种非常常用的数据结构，与线性列表、堆栈并驾齐驱。树的定义树是从自然界中抽象出来的，指的是N个父子节点的有限集，对于这个有限集，需要满足如下条件：当N=0时，节点集为空，且treeisalsoEmpty在任何非空树中，只能有一个根节点。当N>1时，除非预期节点外的其余节点也必须组装成一棵树。也就是说，树具有递归属性。一棵树由若干个子树组成，每棵树又由若干个更小的子树组成。如图所示，二叉树是指一个节点最多只能有两个子树。有序树。通常左子树称为左子树，右子树称为右子树。一棵二叉树最多只能有两棵对称树，一棵二叉树可以分为左树和右树。树和二叉树的区别1.树节点的度数没有限制，二叉树限制为2，树没有限制。2、无序树的节点没有左右之分，二叉树的节点有左右之分。二叉搜索树二叉搜索树，它是一棵空树，具有以下性质的二叉树称为二叉搜索树，它的左子树不为空，左子树的所有节点值都必须小于以下节点的值。如果它的右子树不为空，则右子树中所有节点的值都必须大于根节点的值。它的左右子树分别是二叉排序树。平衡二叉树平衡二叉树具有以下性质：他是一棵树或者他的左右子树的高度差的绝对值不超过1，左右子树都是平衡二叉树。平衡二叉树实现红黑树、AVL、splay树，最小二叉平衡树的节点公开为：F(n)=F(n-1)+F(n-2)+1B-tree一棵m阶B树是一棵平衡的m路搜索树，或者说是一棵空树，它满足以下性质：1、根节点至少有两个孩子，每个非根节点包含k-1个元素和k子节点，其中m/2<=k<=m所有叶节点都在同一层。每个节点中的元素从小到大排列，节点中的k-1个元素恰好是k个子节点中包含的元素取值范围的划分。一般用于文件系统或数据库索引。一般用于文件系统或数据库索引B+树。B+树有以下特点：k个子树的中间节点包含k个元素，每个元素不存储数据，只用于存储索引，所有数据都存储在叶子节点中。所有的叶子节点都包含了所有的元素信息，以及指向这些元素信息的治理，叶子节点本身也是按照降序排列的。所有中间节点元素都存储在叶节点中，叶节点始终是子元素中最大或最小的元素。红黑树红黑树是平衡二叉树的一种实现，具有以下特征：节点为红色或黑色。根节点是黑色的。每个叶子节点都是黑色节点的空节点每个红色节点的两个孩子都是黑色的，从每个叶子节点到根的所有路径上不能有两个连续的红色节点从任何节点到每个叶子节点所有路径包含相同数量的黑色节点。
