什么是树？
树:
树(Tree) 是n (n≥0)个结点的有限集。n=0时称为空树。在任意- -棵非空，
树中: (1) 有且仅有一个特定的称为根(Root) 的结点; (2)当n>1时，其
余结点可分为m (m>0)个互不相交的有限集TI. T2、..... Te,其中每一-个
集合本身又是- -棵树，并且称为根的子树(SubTree)。
image.png
树的概念：
1、节点与树的度
度:结点拥有的子树数称为结点的度。
度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。除根结点以外，分支结点也称为内部结点。
树的度:是树内各结点的度的最大值。
image.png
2 、层次和深度
结点的层次(Level) 从根开始定义起，根为第-层， 根的孩子为第二层。若某结
点在第1层，则其子树的根就在第l+1层。其双亲在同一层的结点互为堂兄弟。显然图6-2-6中的D、E、F是堂兄弟，而G、H、1. I也是。树中结点的最大层次称为树的深度(Depth)或高度，当前树的深度为4。
image.png
3、森林
森林(Forest) 是m(m≥0)棵互不相交的树的集合。
4、树的存储结构
（1）、双亲表示法
image.png
（2）、孩子表示法
image.png
（3）、双亲孩子表示法
把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中。
image.png
（4）、孩子兄弟表示法
孩子兄弟表示法为每个节点设计三个域：一个数据域，一个该节点的第一个孩子节点域，一个该节点的下一个节点的兄弟指针域。
image.png
