树木遍历

Question

我将如何遍历一个节点，该节点可以包含该节点中所有子节点的列表，而子节点可以包含其所有子节点的列表.... etc

类似地说，我的树中有一个名为Root的节点

Root包含2个节点A和B这样

          Root
      A          B

但是我将一个子代插入节点A，这样

         Root(5) 
    A(5)             B(6)
 C(13)

所有节点都有其所有子节点的列表，因此根节点具有[A和B]的列表并且A有一个子列表= [C]

每个节点都有一个为整数的密钥。如果子节点的密钥大于父节点的密钥，则父节点将获取该密钥，因此，如果child.parent.key

所以我将如何访问子级C的密钥并将其分配给我的根节点

预期的输出应该是

          Root(13)
   A(13)

C（13）

本质上，child.key必须冒泡到顶部（根）

Answer 1

我怀疑您正在为此代码使用类，所以id建议您为每个parent object添加一个名为parent_list的属性，在其中存储每个节点的父节点。在C的父级列表中，您拥有A，因为A是C的父级。然后，如果将C（13）添加到树中，则在树中从节点C向上使用BFS，即父节点上的BFS每个节点的密钥，并在满足条件的情况下更新其密钥。如果在此过程中父键较大，请终止。https://en.wikipedia.org/wiki/Breadth-first_search