山东省博兴县实验中学
由于子树的表示顺序可以不同
来源:www.bxsz.net 点击数: 1480 日期:2020-01-11

无根树

无根树与通常称为树(带有根树)的树非常相似。它由节点和分支组成,但不包含根。没有根树的节点之间只有邻接关系,父节点和子节点之间没有关系。如图3.3-1所示,有一个无根树,有7个节点。以图3.3-1的A为根节点,得到图3.3-2所示的根节点。主动3.3-1的B是根节点具有如图3.3-3所示的根树,但是从无根树的角度来看,图3.3-1,图3.3-2和图3.3-3都是相同的无根树树,没有根树。结构与节点名称无关。

C * * A * A * B

\/|/| \

* B * B * * *

|/\ A C/| \

F * * * F * * *

/| \ C/| \ E G D

* * * * * *

E G D E G D

图3.3-1图3.3-2图3.3-3

根树可以表示为字符串,其递归表示为:

根节点(子树1子树2子树3 .)

如图3.3-2所示,图3.3-3中的根树可以分别表示为A(B(CF(EGD)))B(ACF(EGD))。应当注意,子树的表示顺序可以不同。因此,一棵有根的树可以具有多种表示形式,如图3.3-3所示,可以表示为B(F(EGD)CA)和B(ACF(DEG))。

如果没有根树,则可以将其任何节点用作根节点,并将其视为根树,以便可以使用根树的字符串表示形式来表示无根树。

任务1:键盘读取由字符串表示的无根树。无根树的节点名称由彼此不同的大写英文字母表示。然后,用户输入节点的名称,程序应该能够输出以七个点为根节点的字符串形式。

当程序输出不带根树的廖字符串形式时,节点的名称无关紧要,所有节点都用P表示,随后的输出也以这种方式使用。