前几篇文章一直说的是线性结构，各有各的优缺点，也有各有各的应用场景，但是这些数据元素之间的关系都为一对一的关系，而我们生活中关系不止是一对一，有可能是一对多，多对多，所以本篇开始介绍一对多的关系。

1.树的定义

树：顾名思义，跟生活中的树是一样的，由根长成一棵大树，会有很多树枝以及叶子，在生活中有很多类似于树的结构，比如一个家族的族谱，一个公司的组织架构。

所以树（tree）是一个包含n个节点的有限集合(n>0)，其中每个元素称之为节点，我们通常将第一个节点作为一个特定的节点就是我们通常说的根节点（root），除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。所以单个结点是一棵树，树根就是该结点本身。空集合也是树，称为空树。空树中没有结点。

树.png

• 叶结点或终端结点： 度为0的结点称为叶结点；

• 分支结点： 度不为0的结点；

• 父结点（双亲结点）： 若一个结点含有子结点，则这个结点称为其子结点的父结点；

• 子结点（孩子结点）： 一个结点含有的子树的根结点称为该结点的子结点；

• 兄弟结点： 具有相同父结点的结点互称为兄弟结点；

• 结点的度： 一个结点含有的子结点的个数称为该结点的度；

• 树的度： 一棵树中，最大的结点的度称为树的度；

• 结点的层次： 从根开始定义起，根为第1层，根的子结点为第2层，以此类推；

• 树的高度： 树中结点的最大层次树，第一层为最高；

• 树的深度： 与高度的计算相反，第一层为1，以此类推；

• 堂兄弟结点： 双亲在同一层的结点互为堂兄弟；

• 结点的祖先： 从根到该结点所经分支上的所有结点；

• 子孙： 以某结点为根的子树中任一结点都称为该结点的子孙。

• 森林： 由m（m>=0）棵互不相交的树的集合称为森林；
  

  树的属性图示.png

2.树的分类

树的种类分很多，根据是子节点之间否有序可分为有序树和无序树；根据子节点数量分为二叉树和多路查找树；而其中二叉树又分为斜二叉树、满二叉树、完全二叉树、线索二叉树、二叉排序树、平衡二叉树、红黑树、哈夫曼树等。多路查找树分为2-3树、2-3-4树、B树、B树变种树B+树等。多棵互不相交的树称为森林。

树的分类图解.png

3. 二叉树

二叉树是每个结点最多有两个子树的树结构。通常子树被称作左子树（孩子）和右子树（孩子）。

• 满二叉树： 除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

• 完全二叉树： 若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

• 平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。（摘自百度百科）
  

  满二叉树/完全二叉树示例.png

二叉树的一些性质：

• 在非空二叉树中，第i层的结点总数不超过2的i-1次方, i>=1；

• 深度为h的二叉树最多有2的h次方-1个结点(h>=1)，最少有h个结点；

• 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

• 具有n个结点的完全二叉树的深度为[㏒2 n]+1, 注：2是底数，[ ]表示向下取整）；

• 对具有n个结点的完全二叉树，如果按照从上至下和从左至右的顺序对二 叉树的所有结点从1开始编号，则对于任意的序号为i的结点有:
  A. 如果i>1，那么序号为i的结点的双亲结点序号为i/2;
  B. 如果i=1，那么序号为i的结点为根节点，无双亲结点;
  C. 如果2i<=n，那么序号为i的结点的左孩子结点序号为2i;
  D. 如果2i>n，那么序号为i的结点无左孩子;
  E. 如果2i+1<=n，那么序号为i的结点右孩子序号为2i+1;
  F. 如果2i+1>n，那么序号为i的结点无右孩子。