数据结构之究竟什么是树笔记

最初的最初，先来看看树的定义吧（定义即灵魂）

树是n(n>=0)个结点的有限集。当n=0时，称为空树。在任意一颗非空树中应该满足：
1）有且仅有一个特定的称为根(Root)的结点。
2) 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树。

有图有真相
不知道你是否发现了，在树的定义中又出现了树？

是的，树的定义是递归的。也就是说树是一种递归的数据结构。

另外，我们还可以把树看作一个一层一层的结构，也就是层次结构，树非常适合表示具有层次结构的数据呢。她具有以下两个特点：

1）树的根结点没有前驱，除根结点外，所有结点有且仅有一个前驱。
2）树中所有结点可以有零个或多个后继。

有了树，怎么可以没有森林呢？

森林(Forest)是m(m>=0)颗互不相交的树的集合。

既然如此，那将根结点去掉，不就是森林了嘛

事实上，对树中每个结点而言，其子树的集合即为森林。

由此，那么就不难联想到，可以用森林和树相互递归的定义来描述树。

就逻辑结构而言，任何一颗树是一个二元组Tree(root,F),其中：
root是数据元素，称作数的根结点；
F是m颗树的森林，F= (T1,T2,…,Tm),
其中Ti=(ri,Fi）称为根root的第i颗子树；

【数据结构之究竟什么是树】最后的最后，总结一下树结构中的基本术语：

数据结构之究竟什么是树