创建二叉树

您的代码中的问题是您多次添加相同的值。您添加节点，然后仍然更深入地递归，在那里您执行相同的操作。更深层次的问题是，在到达树的底层并检测到该层的不完整位置之前，您并不知道将节点插入何处。找到正确的插入点可能需要遍历整棵树……这打败了您最初期望使用二叉树获得的速度增益。我在这里提供三种解决方案，从最有效的开始：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 stree = Node(1)tree.add(2)tree.add(3)tree.add(4)tree.add(5)print(tree)这从右到左递归搜索树，以找到要添加的节点的候选父节点。对于大树，可以通过根据这些路径的长度在从根到叶的路径之间进行二进制搜索来稍微改进一下。但它仍然不会像前两种解决方案那样高效。

创建二叉树

3回答