树

[TOC] ## 树的种类 * 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为[自由树](https://zh.wikipedia.org/wiki/%E8%87%AA%E7%94%B1%E6%A0%91 "自由树")； * 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树； * [二叉树](https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91 "二叉树")：每个节点最多含有两个子树的树称为二叉树； * [完全二叉树](https://zh.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91 "完全二叉树")：对于一棵二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树； * [满二叉树](https://zh.wikipedia.org/wiki/%E6%BB%A1%E4%BA%8C%E5%8F%89%E6%A0%91 "满二叉树")：所有叶节点都在最底层的完全二叉树； * [平衡二叉树](https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91 "平衡二叉树")（[AVL树](https://zh.wikipedia.org/wiki/AVL%E6%A0%91 "AVL树")）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树； * [排序二叉树](https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E4%BA%8C%E5%85%83%E6%A8%B9 "排序二叉树")([二叉查找树](https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91 "二叉查找树")（英语：Binary Search Tree))：也称二叉搜索树、有序二叉树； * [霍夫曼树](https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E6%A0%91 "霍夫曼树")：[带权路径](https://zh.wikipedia.org/w/index.php?title=%E5%B8%A6%E6%9D%83%E8%B7%AF%E5%BE%84&action=edit&redlink=1 "带权路径（页面不存在）")最短的二叉树称为哈夫曼树或最优二叉树； * [B树](https://zh.wikipedia.org/wiki/B%E6%A0%91 "B树")：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。