外观
4.2 树的操作
树的基本操作
4.1节说的是树"是什么"。要用它,还得规定能对它做什么。1.3节说过,逻辑关系加上一组操作,就是抽象数据类型。这一节给树定下这组操作。
树常用的操作有很多,不同的程序用到的不一样。这里取最基本的八个,文件夹正好都要用。下面把树记作T,结点记作p,新结点的名字记作x。接着用4.1节那棵文件夹树:
InitTree(T):建立一棵空树。一个文件夹都还没有的时候,先要有一棵空树。
Root(T):返回根。一切从根开始找。在这棵树上,返回的是"文档"。空树没有根,返回NULL。
Value(T, p):返回结点p的名字。拿到一个结点,要知道它叫什么,才能显示出来。
Parent(T, p):返回p的双亲,也就是点一下"上一级"。根没有双亲,返回NULL。Parent(T, 周报)返回工作:
FirstChild(T, p):返回p的第一个孩子,也就是打开文件夹,看第一项。p没有孩子时返回NULL。FirstChild(T, 工作)返回周报;FirstChild(T, 下载)返回NULL,因为"下载"是空的。
NextSibling(T, p):返回p的下一个兄弟,也就是往下看一项。p后面没有兄弟时返回NULL。NextSibling(T, 周报)返回合同:
InsertChild(T, p, x):给p加一个孩子,名字是x,返回新结点,也就是在文件夹里新建一项。新结点放在p的孩子最前面。4.1节说过,文件夹是无序树,孩子的先后不算数,放在哪里都还是这棵树。p写NULL时,表示往空树里放,x成为根。
DeleteSubtree(T, p):删除p和它的全部子孙,也就是删除文件夹。DeleteSubtree(T, 工作)删掉的是工作、周报、合同、2025、年终总结,一共5个结点:
八个操作汇总如下:
| 操作 | 含义 | 文件夹里的动作 |
|---|---|---|
| InitTree(T) | 建立一棵空树 | 还没有任何文件夹 |
| Root(T) | 返回根 | 打开最顶层 |
| Value(T, p) | 返回p的名字 | 看这一项叫什么 |
| Parent(T, p) | 返回p的双亲 | 点"上一级" |
| FirstChild(T, p) | 返回p的第一个孩子 | 打开文件夹,看第一项 |
| NextSibling(T, p) | 返回p的下一个兄弟 | 往下看一项 |
| InsertChild(T, p, x) | 给p加一个孩子x | 新建一项 |
| DeleteSubtree(T, p) | 删除p和它的全部子孙 | 删除文件夹 |
和2.2节线性表的操作比,有三处不同。
位置是结点,不是序号。线性表说"第i个"。树没有第i个,一层有好几个结点,从左到右数也说不清它是谁的孩子。所以操作直接拿结点说话,就是2.16节的按结点操作。
孩子一个一个地看。一个文件夹里有几项,事先不知道。所以先用FirstChild拿到第一个,再用NextSibling一个一个往下看,看到NULL就完了。也可以定成"取第i个孩子",这是一种取舍,这里选了更贴近打开文件夹的那种。
删除连子孙一起删。删掉一个结点,它的孩子不能悬空,总得有个去处。删除文件夹时,里面的东西一起没了,所以这里定成连子孙一起删。
常见的还有求高度、把每个结点都走一遍等操作,用到时再加。