时间戳

首页 > 解决方案 > 创建二叉树

python - 创建二叉树

问题描述

我搜索过的关于二叉树的大多数问题都显示了二叉搜索树的实现，但不是二叉树。完全二叉树的项是：

我想出了一个概念，但它似乎没有正确地通过递归——有谁知道我做错了什么？

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)

标签： pythonclassif-statementbinary-treeself

解决方案

您的代码中的问题是您多次添加相同的值。您添加节点，然后仍然进行更深层次的递归，在此处执行相同操作。

更深层次的问题是，在到达树的底层之前，您并不真正知道在哪里插入节点，并且已经检测到该层不完整的位置。找到正确的插入点可能需要遍历整个树...这会破坏您最初期望从使用二叉树获得的速度增益。

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

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)

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

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

推荐阅读