什么是树
这个文件夹目录可以看成一棵树:最顶层只有一个"文档",其余的东西一层套一层挂在它下面。
树的定义是这样的。树是n个结点的有限集合。n等于0时,叫空树。n大于0时:
- 有且只有一个特定的结点,叫根;
- 其余的结点分成m个互不相交的有限集合,每个集合本身又是一棵树,叫根的子树。
定义里用到了树自己:子树也是树。这就是3.8节的递归,一棵树用几棵小一点的树来说清楚。
放回文件夹里看。每个文件、每个文件夹都是一个结点,一共12个。根是"文档"。其余11个结点分成4组:
- 工作、周报、合同、2025、年终总结,5个;
- 论文、初稿,2个;
- 照片、1.jpg、2.jpg,3个;
- 下载,1个。
每一组正好是"文档"里的一个文件夹,连同它里面的全部内容。每一组自己又是一棵树:工作这棵子树的根是"工作";下载这棵子树只有一个结点。把"工作"整个拷到U盘上,拷走的就是一棵子树。
这个定义有三个要点,逐条看。
有且只有一个根。根只有一个,程序只要记住它,就能从它出发找到所有东西。电脑里的C盘和D盘各有自己的最顶层,放在一起就有两个根,不是一棵树:
互不相交。除了根,每个结点只属于一组。假设周报同时放在"工作"和"论文"里:
"工作"那组和"论文"那组都有周报,两组相交了,这就不是树。互不相交,"周报在哪个文件夹里"就只有一个答案,从根走到它只有一条路。
每组又是一棵树。只看最上面一层还不够。假设年终总结放在2025里,又直接放在"工作"里:
看最上面一层,4组照样互不相交,年终总结只在"工作"这一组里。可是把"工作"这一组当成一棵树,再拆一层,"2025"那组和"年终总结"那组就相交了。所以判断是不是树,要一层一层拆到底,每一层都满足才行。
三个要点合起来,可以得到一个好用的结论:除了根,每个结点恰好有一个上级,而且从根出发往下走,能走到每一个结点。判断一样东西是不是树,看这一条最快。
森林
把根"文档"去掉,剩下的4棵子树就各自独立了:
m棵互不相交的树放在一起,叫森林。m可以是0。
树的定义里说,其余的结点分成m个互不相交的集合,每个又是一棵树。这说的就是:去掉根,剩下的是一片森林。反过来,给这4棵树加一个共同的上级"文档",又成了一棵树。
树和森林只差一个根。上一页的C盘和D盘,合起来不是一棵树,而是一片有两棵树的森林。
程序也常常和森林打交道。后面把一棵树走一遍时,看完根以后,要接着走的正是它的子树组成的森林。
例题:组织架构和先修课能看成树吗
题目把每个人、每门课当作结点,下面两样东西能不能看成一棵树?
一家小公司:张总管着李经理和陈经理,李经理管着小王和小赵,陈经理管着小刘。
几门课的先修关系:学C语言和离散数学之前,要先学高中数学;学数据结构之前,要先学C语言和离散数学。
分析。先看公司,上级就是管着他的人。
- 看根:只有张总没有上级。是。
- 看互不相交:李经理、陈经理各管一组人。小王、小赵只在李经理那组,小刘只在陈经理那组,没有人同时在两组。是。
- 看每组是不是树:李经理那组,根是李经理,小王、小赵各成一组,互不相交;陈经理那组也一样。是。
再看课程,上级就是要先学的课。
- 看根:只有高中数学不需要先学别的课。是。
- 看互不相交:高中数学下面分成C语言、离散数学两组。数据结构既要先学C语言,又要先学离散数学,两组都有它。否。到这里就能下结论。
答案公司可以看成一棵树,根是张总。先修课不能,因为数据结构有两个上级,两组相交了。
两样东西都只有一个根,差别在互不相交这一条:一门课可以有好几门先修课,一个人却只有一个直接上级。
双亲、孩子、兄弟、祖先、子孙
这几个名词说的是结点和结点之间的关系,名字借自家谱。
一个结点的上级,叫它的双亲。它直接的下级,叫它的孩子。工作是周报的双亲;周报、合同、2025是工作的孩子。树里每个结点只有一个双亲,"双亲"这个词说的是一个结点,不是两个。
同一个双亲的孩子,互为兄弟。周报、合同、2025是兄弟。它们放在同一个文件夹里,所以不能重名。
从根走到一个结点,路上经过的结点都是它的祖先。年终总结的祖先是文档、工作、2025,一共3个。地址栏里的路径,写的正是它的全部祖先:
反过来,一个结点下面的所有结点,都是它的子孙。工作的子孙是周报、合同、2025、年终总结,一共4个。删除"工作"文件夹时,一起被删掉的就是它的全部子孙:
和2.1节的线性表对照一下:
text线性表:除了第一个,每个元素恰好一个前驱;除了最后一个,每个元素恰好一个后继
树: 除了根,每个结点恰好一个双亲;孩子可以有任意多个
双亲像前驱,只有一个。孩子不像后继,可以有好几个。树就是把"后继只有一个"放开了。反过来,每个结点最多一个孩子的树,就是一个线性表。
度、叶子、分支结点
一个结点有几个孩子,叫这个结点的度。打开一个文件夹,直接看到几项,它的度就是几:
度只数孩子,不数孩子的孩子。工作下面一共有4样东西,可它的度是3:年终总结在2025里,不是工作直接的孩子。文件里不能再放东西,度都是0。
各结点的度里最大的那个,叫树的度。这棵树的度是4,就是"文档"的度。
度为0的结点叫叶子,度不为0的结点叫分支结点。这棵树有7个叶子:6个文件,加上空文件夹"下载"。分支结点有5个:文档、工作、2025、论文、照片。
"下载"是文件夹,可它里面什么都没有,度是0,所以也是叶子。叶子看的是有没有孩子,不是是不是文件。从根往下找东西,走到叶子,这条路就走到头了。
验算一下:7个叶子加5个分支结点,正好12个结点。所有结点的度加起来是4 + 3 + 1 + 1 + 2,等于11,比结点数少1。因为除了根,每个结点都是某一个结点的孩子,在度里恰好被数了一次。
层次、深度、高度
根在第1层,根的孩子在第2层,孩子的孩子在第3层,依此类推。这叫结点的层次。
由层次,本书这样约定深度和高度:
- 结点的深度:从根往下数,就是它的层次。根的深度是1,年终总结的深度是4。
- 结点的高度:从它下面最深的叶子往上数,叶子的高度是1。2025的高度是2,工作的高度是3,文档的高度是4。
- 树的高度,也叫树的深度:最大的层次。这棵树的高度是4。空树的高度是0。
放回文件夹里:一个结点的深度,就是地址栏里有几段,文档\工作\2025\年终总结有4段。树的高度,就是最深的东西藏了几层:从"文档"开始,最多再点开3次文件夹,就能看到任何一个文件。
另一种约定
很多英文教材和LeetCode按边数算:根的深度是0,叶子的高度是0,算出来都比本书少1。做题时先看清用的是哪一种。本书和国内教材、考研统考一样,按层数算。
有序树和无序树。资源管理器里,文件可以按名称排,也可以按修改时间排。不管怎么排,周报还在工作里,目录还是同一个。孩子之间的先后不算数,这样的树叫无序树。
书的目录不一样。第一章、第二章、第三章的先后不能换,换了就是另一本书。孩子之间的先后算数,这样的树叫有序树。
回到本章开头的第一个问题:程序要记住文件夹之间的什么?这些文件夹可以看成一棵树,而树里除了根,每个结点恰好有一个双亲。所以程序要记住的,是每个结点的双亲是谁,或者反过来,每个结点的孩子是谁。有了这一条,层次、祖先、子孙、度、高度,都能算出来。
练习2:数一数
下面是一本菜谱的目录。菜谱分成凉菜、热菜和附录三部分。凉菜里有拍黄瓜、皮蛋豆腐。热菜分成炒菜、炖菜、蒸菜三类,炖菜里又有红烧肉、炖牛肉。
填空
把这本菜谱的目录看成一棵树,层次从1开始数。
- 树的度是
- 叶子一共有 个
- 红烧肉的祖先一共有 个
- 树的高度是
菜谱和热菜各有3个孩子,树的度是3。热菜下面一共有5样东西,但度只数孩子。叶子是没有孩子的结点:拍黄瓜、皮蛋豆腐、炒菜、红烧肉、炖牛肉、蒸菜,还有附录,一共7个;附录下面没有分类,也是叶子。红烧肉的祖先是炖菜、热菜、菜谱,3个,根也算。红烧肉在第4层,树的高度是4;按边数算才会得到3。
到这里你有了树的递归定义和三个要点:有且只有一个根,其余结点分成互不相交的几组,每组又是一棵树。去掉根剩下的是森林。描述树的一套名词:双亲、孩子、兄弟、祖先、子孙;度、叶子、分支结点;层次、深度、高度;有序树和无序树。