数据结构-树

树形结构是一类非常重要的非线性数据结构，它是以分支关系定义的层次结构。树形结构在现实世界中广泛存在，在计算机领域中也有广泛应用。

树

树是由n(n ≥ 0)个节点组成的有限集合（记为T）。其中：

• 如果n = 0，它是一棵空树，这是树的特例
• 如果n > 0，这n个节点中存在（且仅存在）一个节点作为树的根节点，简称为根节点（Root），其余节点可分为m(m > 0)个互不相交的有限集T1, T2, …, Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树

image-20210109160515110

image-20210109160616058

树的表示

树形表示法

树形表示法是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。

image-20210109160754374

文氏图表示法

文氏图表示法是使用集合以及集合的包含关系描述树结构。

凹入表示法

凹入表示法是使用线段的伸缩描述树结构。