【大话数据结构C语言】23 什么是树？

作者Allen，专注C/C++/IoT/算法等技术分享，技术交流群添加微信号：CoderAllen，回复关键字即可

之前的数据结构都是一对一的线性结构，而树是一对多的数据结构

树的定义：

树是有n个结点的有限集,n=0时称为空树
在任何一棵非空树中，有且仅有一个特定的称为根的结点
当n>1时，其余结点可分为m个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树，如下图

树的定义其实就是之前提到的栈的递归的方法，就是树的定义的之后还用到了树
如下图，子树T1和子树T2就是结点A的子树，D/G/H/I组成的树又是B为结点的子树，E/J组成的树是C为结点的子树

树的定义中有两点需要注意：
1.n>0的时候根结点是唯一的，不可能存在多个根结点
2.m>0时，子树的个数没有限制，但他们一定是互不相交的
下边的两个结构就不符合树的定义，因为有相交的子树:

结点分类：

• 树的结点包含一个数据元素和若干指向子树的分支
• 结点拥有的子树数称为结点的度（Degree）
• 度为0的结点称为叶节点或者终端结点
• 度不为0的结点称为非终端结点或者分支结点
• 除了跟结点外，分支结点也称为内部结点
• 树的度是树内部各结点的度的最大值
  

结点间关系：

结点的子树的根称为该结点的（child），对应，该结点称为孩子的（parent）
同一个双亲的孩子之间互称兄弟（sibling）
结点的祖先是从根到该结点所经分支上的所有结点

所以下图中，对于H来说，D,B,A都是他的祖先，反之，以某结点为根的子树中的任一结点都称为该结点的子孙，B的 子孙有D,G,H,I

树的其他概念

• 树中结点的最大层次称为树的深度（depth）或者高度，当前树的深度为4
  

• 如果将树中结点的各个子树看成从左到右是有次序的，不能互换的，则称该树为有序树，否则称无序树

• 森林（forest）是m棵互不相交的树的集合

对比线性表和树的结构，他们有很大的不同

树的抽象数据结构：

和线程表的差别还是很大的