创建二叉树

Question

我搜索过的关于二叉树的大多数问题都显示了二叉搜索树的实现，而不是二叉树。完全二叉树的项是：要么是一棵空树，要么它有 1 个节点和 2 个孩子，其中每个孩子都是另一个二叉树。所有级别都已满（可能最后一个级别除外）最底层的所有叶子都尽可能靠左。我想出了一个概念，但它似乎没有正确运行递归——有人知道我做错了什么吗？class Node():    def __init__(self, key):        self.key = key        self.left = None        self.right = None    def add(self, key):         if self.key:             if self.left is None:                 self.left = Node(key)             else:                 self.left.add(key)                if self.right is None:                     self.right = Node(key)                 else:                     self.right.add(key)         else:             self.key = key        return (self.key)

Answer 1

您的代码中的问题是您多次添加相同的值。您添加节点，然后仍然更深入地递归，在那里您执行相同的操作。

更深层次的问题是，在到达树的底层并检测到该层的不完整位置之前，您并不知道将节点插入何处。找到正确的插入点可能需要遍历整棵树……这打败了您最初期望使用二叉树获得的速度增益。

我在这里提供三种解决方案，从最有效的开始：

1.使用列表作为树实现

对于完整的树，需要特别考虑：如果按级别对节点进行编号，从 0 开始作为根节点，并且在每个级别内从左到右，您会注意到节点的父节点的编号为(k-1) /2当它自己的编号是k时。在另一个方向：如果编号为k的节点有子节点，则其左子节点的编号为k*2+1，右子节点的编号大一。

因为树是完整的，所以这个编号永远不会有间隙，所以你可以将节点存储在一个列表中，并使用该列表的索引为节点编号。现在将节点添加到树中仅意味着将其附加到该列表。您没有Node对象，只有树列表，该列表中的索引是您的节点引用。

这是一个实现：

class CompleteTree(list):

    def add(self, key):

        self.append(key)

        return len(self) - 1

    def left(self, i):

        return i * 2 + 1 if i * 2 + 1 < len(self) else -1

    def right(self, i):

        return i * 2 + 2 if i * 2 + 2 < len(self) else -1            

    @staticmethod

    def parent(i):

        return (i - 1) // 2

    def swapwithparent(self, i):

        if i > 0:

            p = self.parent(i)

            self[p], self[i] = self[i], self[p]

    def inorder(self, i=0):

        left = self.left(i)

        right = self.right(i)

        if left >= 0:

            yield from self.inorder(left)

        yield i

        if right >= 0:

            yield from self.inorder(right)

    @staticmethod

    def depth(i):

        return (i + 1).bit_length() - 1

这是一个创建示例树的演示，然后打印按顺序遍历访问的键，按它们在树中的深度缩进：

tree = CompleteTree()

tree.add(1)

tree.add(2)

tree.add(3)

tree.add(4)

tree.add(5)

for node in tree.inorder():

    print("  " * tree.depth(node), tree[node])

当然，这意味着您必须引用与使用真实Node类时略有不同的节点，但效率的提高是有回报的。

2.使用额外的属性

如果您知道一棵（子）树中有多少个节点，那么从该数字的位表示，您就可以知道应该在何处添加下一个节点。

例如，在您的示例树中，您有 5 个节点。想象一下，你想给那棵树加一个 6。根节点会告诉您当前有 5，因此您需要将其更新为 6。在二进制中为 110。忽略最左边的 1 位，其余位告诉您是向左还是向右。在这种情况下，您应该向右走 (1)，然后最后向左走 (0)，在那个方向上创建节点。您可以迭代或递归地执行此操作。

这是一个递归的实现：

class Node():

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

        self.count = 1

    def add(self, key):

        self.count += 1

        if self.left is None:

            self.left = Node(key)

        elif self.right is None:

            self.right = Node(key)

        # extract from the count the second-most significant bit:

        elif self.count & (1 << (self.count.bit_length() - 2)):

            self.right.add(key)

        else:

            self.left.add(key)

    def inorder(self):

        if self.left:

            yield from self.left.inorder()

        yield self

        if self.right:

            yield from self.right.inorder()

tree = Node(1)

tree.add(2)

tree.add(3)

tree.add(4)

tree.add(5)

for node in tree.inorder():

    print(node.key)

3.无额外财产

如果没有属性可以添加到Node对象，则需要进行更广泛的搜索才能找到正确的插入点：

class Node():

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

    def newparent(self):

        # Finds the node that should serve as parent for a new node

        # It returns a tuple:

        #   if parent found: [-1, parent for new node]

        #   if not found: [height, left-most leaf]

        # In the latter case, the subtree is perfect, and its left-most  

        # leaf is the node to be used, unless self is a right child 

        # and its sibling has the insertion point.

        if self.right:

            right = self.right.newparent()

            if right[0] == -1: # found inbalance

                return right

            left = self.left.newparent()

            if left[0] == -1: # found inbalance

                return left

            if left[0] != right[0]:

                return [-1, right[1]] # found inbalance

            # temporary result in perfect subtree

            return [left[0]+1, left[1]]

        elif self.left:

            return [-1, self] # found inbalance

        # temporary result for leaf

        return [0, self]

    def add(self, key):

        _, parent = self.newparent()

        if not parent.left:

            parent.left = Node(key)

        else:

            parent.right = Node(key)

    def __repr__(self):

        s = ""

        if self.left:

            s += str(self.left).replace("\n", "\n  ")

        s += "\n" + str(self.key)

        if self.right:

            s += str(self.right).replace("\n", "\n  ")

        return s

tree = Node(1)

tree.add(2)

tree.add(3)

tree.add(4)

tree.add(5)

print(tree)

这从右到左递归搜索树，以找到要添加的节点的候选父节点。

对于大树，可以通过根据这些路径的长度在从根到叶的路径之间进行二进制搜索来稍微改进一下。但它仍然不会像前两种解决方案那样高效。

Answer 2

您可以使用 sklearn 决策树，因为它们也可以设置为二元决策树。链接到此处的文档。

Answer 3

你真的需要以某种方式扩充你的树。因为这不是二叉搜索树，所以关于每个节点的唯一真实信息是它是否有左孩子和右孩子。不幸的是，这对导航完整的二叉树没有帮助。想象一个有 10 个级别的完整二叉树。直到第 9 级，每个节点都有一个左孩子和一个右孩子，所以你无法知道从哪条路径向下到达叶子。那么问题来了，你给每个节点添加什么信息呢？我会添加该树中的节点数。

维护计数很容易，因为每次下降到子树时，您都知道要在该节点的计数上加一。你要识别的是最左边的不完美子树。每个完美二叉树都有 n = 2^k - 1，其中 k 是层数，n 是节点数。有一些快速简便的方法可以检查一个数是否小于 2 的幂（参见这个问题的第一个答案），事实上，在一棵完整的二叉树中，每个节点最多有一个不是根的子节点的完美二叉树。遵循一个简单的规则来添加节点：

1. 如果左孩子为 None，则设置root.left = Node(key)并返回

2. 否则，如果右孩子为 None，则设置root.right = Node(key)并返回

3. 如果当前节点的子节点之一是不完美子树的根，则使该节点成为当前节点（沿该子树下降）

4. 否则，如果大小不相等，则将具有较小子树的节点作为当前节点。

5. 否则，使左子节点成为当前节点。

通过用以该节点为根的子树的大小扩充每个节点，您可以在每个节点上获得构建递归解决方案所需的所有信息。