外观
第4章 · 11 节
树:层层嵌套的数据怎么表示、怎么走遍
还没开始
第4章 树
打开电脑里的"文档"文件夹。里面有工作、论文、照片、下载四个文件夹。"工作"里放着周报、合同,还有一个文件夹2025,里面是年终总结。"论文"里是初稿,"照片"里是两张照片,"下载"还是空的。
带折角的框是文件夹,没有框的是文件。
2.1节的练习里,文件夹目录被判为不能看成线性表。试着硬把它排成一列:
text
(文档, 工作, 周报, 合同, 2025, 年终总结, 论文, 初稿, 照片, 1.jpg, 2.jpg, 下载)这一列只记得谁挨着谁。周报在哪个文件夹里?"工作"里直接有几项?"下载"是一个空文件夹,还是一个文件?从这一列里都看不出来。
一个文件夹里可以放好几项,它的后继不止一个。线性表记得住谁挨着谁,记不住谁装着谁。
公司的组织架构,一个经理管着几个人;一本书的目录,一章分成几节。它们也都是这样一层套一层。
在数据结构里,这样的数据叫树。
学完这一章,你会判断什么样的数据是树,用一套名词说清它的样子,把它放进内存,并把它的每个结点都走一遍。
要让程序管好这些文件夹,得先回答三个问题:
问题:
- 程序要记住文件夹之间的什么?
- 怎样把每个文件都看一遍,一个不漏、一个不重?
- 怎么把它放进内存?
先记住这三个问题。我们从第一个开始。要回答它,先得把"一层套一层"说精确。