Skip to content
第4章

4.2 树的操作 ​

树的基本操作 ​

4.1节说的是树"是什么"。要用它,还得规定能对它做什么。1.3节说过,逻辑关系加上一组操作,就是抽象数据类型。这一节给树定下这组操作。

树常用的操作有很多,不同的程序用到的不一样。这里取最基本的八个,文件夹正好都要用。下面把树记作T,结点记作p,新结点的名字记作x。接着用4.1节那棵文件夹树:

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

InitTree(T):建立一棵空树。一个文件夹都还没有的时候,先要有一棵空树。

Root(T):返回根。一切从根开始找。在这棵树上,返回的是"文档"。空树没有根,返回NULL。

Value(T, p):返回结点p的名字。拿到一个结点,要知道它叫什么,才能显示出来。

Parent(T, p):返回p的双亲,也就是点一下"上一级"。根没有双亲,返回NULL。Parent(T, 周报)返回工作:

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

FirstChild(T, p):返回p的第一个孩子,也就是打开文件夹,看第一项。p没有孩子时返回NULL。FirstChild(T, 工作)返回周报;FirstChild(T, 下载)返回NULL,因为"下载"是空的。

NextSibling(T, p):返回p的下一个兄弟,也就是往下看一项。p后面没有兄弟时返回NULL。NextSibling(T, 周报)返回合同:

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

InsertChild(T, p, x):给p加一个孩子,名字是x,返回新结点,也就是在文件夹里新建一项。新结点放在p的孩子最前面。4.1节说过,文件夹是无序树,孩子的先后不算数,放在哪里都还是这棵树。p写NULL时,表示往空树里放,x成为根。

DeleteSubtree(T, p):删除p和它的全部子孙,也就是删除文件夹。DeleteSubtree(T, 工作)删掉的是工作、周报、合同、2025、年终总结,一共5个结点:

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

八个操作汇总如下:

操作含义文件夹里的动作
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个孩子",这是一种取舍,这里选了更贴近打开文件夹的那种。

删除连子孙一起删。删掉一个结点,它的孩子不能悬空,总得有个去处。删除文件夹时,里面的东西一起没了,所以这里定成连子孙一起删。

常见的还有求高度、把每个结点都走一遍等操作,用到时再加。

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