Skip to content
第4章

4.1 树 ​

什么是树 ​

这个文件夹目录可以看成一棵树:最顶层只有一个"文档",其余的东西一层套一层挂在它下面。

树的定义是这样的。树是n个结点的有限集合。n等于0时,叫空树。n大于0时:

  1. 有且只有一个特定的结点,叫根;
  2. 其余的结点分成m个互不相交的有限集合,每个集合本身又是一棵树,叫根的子树。

定义里用到了树自己:子树也是树。这就是3.8节的递归,一棵树用几棵小一点的树来说清楚。

放回文件夹里看。每个文件、每个文件夹都是一个结点,一共12个。根是"文档"。其余11个结点分成4组:

  • 工作、周报、合同、2025、年终总结,5个;
  • 论文、初稿,2个;
  • 照片、1.jpg、2.jpg,3个;
  • 下载,1个。
文档工作周报合同2025年终总结论文初稿照片1.jpg2.jpg下载

每一组正好是"文档"里的一个文件夹,连同它里面的全部内容。每一组自己又是一棵树:工作这棵子树的根是"工作";下载这棵子树只有一个结点。把"工作"整个拷到U盘上,拷走的就是一棵子树。

这个定义有三个要点,逐条看。

有且只有一个根。根只有一个,程序只要记住它,就能从它出发找到所有东西。电脑里的C盘和D盘各有自己的最顶层,放在一起就有两个根,不是一棵树:

C盘系统程序D盘资料备份

互不相交。除了根,每个结点只属于一组。假设周报同时放在"工作"和"论文"里:

文档工作周报合同2025年终总结论文初稿照片1.jpg2.jpg下载

"工作"那组和"论文"那组都有周报,两组相交了,这就不是树。互不相交,"周报在哪个文件夹里"就只有一个答案,从根走到它只有一条路。

每组又是一棵树。只看最上面一层还不够。假设年终总结放在2025里,又直接放在"工作"里:

文档工作周报合同2025年终总结论文初稿照片1.jpg2.jpg下载

看最上面一层,4组照样互不相交,年终总结只在"工作"这一组里。可是把"工作"这一组当成一棵树,再拆一层,"2025"那组和"年终总结"那组就相交了。所以判断是不是树,要一层一层拆到底,每一层都满足才行。

三个要点合起来,可以得到一个好用的结论:除了根,每个结点恰好有一个上级,而且从根出发往下走,能走到每一个结点。判断一样东西是不是树,看这一条最快。

选中正文里的任意文字,就可以针对它发表评论