引入
之前我们讲的都是线性表,它们有可以是顺序存储结构或者链式存储结构
的数组、链表、栈、队列。
我们之前讨论的线性结构
都是一对一的。那什么不是一对一呢?例如妈妈的两个孩子,一个妈妈对应了两个孩子,这种一对多的数据结构,我们称之为树。
当然了,以后还会有多对多的概念,今天我们先了解一下树的概念。
树的定义
树(Tree)是 n ($n\geq0$) 个结点的有限集。n=0 时,我们称之为空树
。
在任意一棵非空树
中:
- 有且仅有一个特定的称之为根(Root)的结点。
- 当 n>1 时,其余结点可分为 m($m\geq0$)个互补相交的有限集
- 有限集 T1、T2、….、Tm,其中每一个集合本身又是一棵树
- 我们称由这些有限集合构成的树,为根的子树(SubTree)。
上面的图中
- 根:A 结点是这棵树的根
- 结点:每一个圈都是一个结点
- 子树:B、C、D、E、F、G、H都是子树