Skip to content

第4章 · 11 节

树:层层嵌套的数据怎么表示、怎么走遍

还没开始

开始阅读

第4章 树 ​

打开电脑里的"文档"文件夹。里面有工作、论文、照片、下载四个文件夹。"工作"里放着周报、合同,还有一个文件夹2025,里面是年终总结。"论文"里是初稿,"照片"里是两张照片,"下载"还是空的。

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

带折角的框是文件夹,没有框的是文件。

2.1节的练习里,文件夹目录被判为不能看成线性表。试着硬把它排成一列:

text
(文档, 工作, 周报, 合同, 2025, 年终总结, 论文, 初稿, 照片, 1.jpg, 2.jpg, 下载)

这一列只记得谁挨着谁。周报在哪个文件夹里?"工作"里直接有几项?"下载"是一个空文件夹,还是一个文件?从这一列里都看不出来。

一个文件夹里可以放好几项,它的后继不止一个。线性表记得住谁挨着谁,记不住谁装着谁。

公司的组织架构,一个经理管着几个人;一本书的目录,一章分成几节。它们也都是这样一层套一层。

在数据结构里,这样的数据叫树。

学完这一章,你会判断什么样的数据是树,用一套名词说清它的样子,把它放进内存,并把它的每个结点都走一遍。

要让程序管好这些文件夹,得先回答三个问题:

问题:

  1. 程序要记住文件夹之间的什么?
  2. 怎样把每个文件都看一遍,一个不漏、一个不重?
  3. 怎么把它放进内存?

先记住这三个问题。我们从第一个开始。要回答它,先得把"一层套一层"说精确。

本章目录

  1. 4.1 树
  2. 4.2 树的操作
  3. 4.3 树的存储结构
  4. 4.4 树的存储结构的实现
  5. 4.5 二叉树
  6. 4.6 二叉树的性质
  7. 4.7 二叉树的存储结构
  8. 练 二叉树的结点表 · 第一问:结点信息
  9. 4.8 二叉树的遍历
  10. 练 二叉树的结点表 · 第二问:三种遍历
  11. 4.9 二叉树的属性计算
  12. 练 二叉树的结点表 · 第三问:树的高度
  13. 4.10 由遍历序列构造二叉树
  14. 4.11 哈夫曼树和哈夫曼编码