algorithm - 如何将普通二叉树转换为 "smarter"二叉树，其中每个节点都知道其父节点、子节点总数和级别？

Question

我还在习惯数据结构，我对以各种方式遍历二叉树感到很舒服，但现在我遇到的情况是我有一个普通的二叉树，它由只知道的节点构成具有 data、left 和 right 属性。

但是我想把它转移到一个“更聪明”的二叉树中。这棵树就是要知道它的父节点，它的总子节点，以及它在总树中的层级。

我真的很纠结如何将一棵“笨”树转移到更智能的版本中。我的第一直觉是递归遍历，但我不确定如何区分父级和级别。

Answer 1

将旧树复制到新树，使用普通的递归方法遍历原树。

由于您要向节点添加新属性，我认为您需要构建具有新属性字段的新节点。

定义一个递归函数来复制以给定节点为根的(子)树。它需要将其深度和父对象作为输入。 (当然，父级需要是新树中的父级。)让它返回新(子)树的根。

function copy_node (old_node, new_parent, depth) -> returns new_node {
    new_node = new node
    new_node.data = old_root.data // whatever that data might be
    new_node.depth = depth
    new_node.parent = parent
    new_node.left = copy_node (old_node.left, new_node, depth + 1)
    new_node.right = copy_node (old_node.right, new_node, depth + 1)
    return new_node }

复制整棵树

new_tree = copy_node (old_tree, nil, 0)

如果您使用的语言可以随意将字段添加到现有对象，您甚至不必进行额外的复制:

function adorn_node (node, parent, depth) {
    node.parent = parent
    node.depth = depth
    adorn_node (node.left, node, depth + 1)
    adorn_node (node.right, node, depth + 1) }

开始滚动

adorn_node (root, nil, 0)

话虽如此，您可能会发现大多数二叉树实现不包含这些额外字段是有充分理由的。在要对树执行的许多不同操作中维护它们需要大量工作。 深度，尤其是当您需要重新平衡树时，很难保持正确。

田地通常不会给你买任何东西。大多数对树进行运算的算法都使用递归函数，正如您从上面的示例中看到的那样，在运行时重新计算parent 和depth 真的很容易你在树上行走。它们本身不需要存储在节点中。

树平衡通常需要知道左右子树的高度差。 (“深度”是到根的距离；“高度”是到子树中最远叶节点的距离。)高度在从根向下的路径上不是那么容易计算的，但幸运的是，您通常只对哪个子树具有最大的高度感兴趣，为此通常在每个节点中仅存储值 -1、0、+1 就足够了。