基本概念

树是一系列点组成的、具有层次结构的集合。

基本特点

• 每个节点有0或多个子节点
• 没有父节点的节点称为根节点（root）
• 每个非根节点有且仅有一个子节点
• 除了根节点，每个子节点可以分为多个不相交的子树

特定术语

• 节点的度：节点所含的子树个数（A-->3）
• 树的度：一棵树中，最大的节点的度（A-->3）
• 叶节点：子节点为0的节点（E、F、G、H、I、J）
• 兄弟节点：具有相同父节点的节点（BCD、EF、GH、IJ）
• 节点层次：从根节点开始，根为第一层，根节点的子节点为第二层，以此类推
• 深度：对于节点n，从根节点到n的唯一路径长（C-->1）
• 高度：对于节点n，从n到树叶节点的最长路径（A-->2）
• 森林：有n（n>0）棵互不相交的树组成的集合

image.png

树的分类

1、无序树

  任意节点的子节点间是没有顺序的，也称自由树

2、有序树

  任意节点的子节点间是存在顺序的

二叉树

  每个节点中最多含有2个子节点的树称为二叉树。

2.1、完全二叉树

  假设一棵树的深度为n（n>1），除了第n层以为，其余层数的节点数已达最大值，且若第n层有节点，则节点是从左到右依次排序的。

2.2、满二叉树

   所有叶节点都在最底层的完全二叉树

2.3、平衡二叉树（AVL树）

   当且仅当任何节点的两棵子树的高度差不大于2的二叉树

2.4、二叉查找树

   具有以下特性的二叉树：
   1.若任一节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
   2.若任一节点的右子树不为空，则左子树上所有节点的值均大于它的根节点的值
   3.若任一节点的子树也分别是二叉查找树
   4.不存在键值相等的节点

2.4、红黑树

  一种自平衡二叉树，典型的用途的实现关联数组。

• 哈夫曼树
    带权路径最短的二叉树称为哈夫曼树或最优二叉树；

• B树
    一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树