python - 将节点插入二叉树

Question

我正在尝试实现一个二叉树以及用于向其中插入节点、遍历它等的支持方法。我有一个特殊的情况，我的代码进入循环或等待太长时间才能返回某个输入。鉴于我面临的问题，我认为它是独一无二的，因此我将其发布。我试图了解我可能做错了什么。以下是我的代码:

# Create a class for the node data structure


    class Node:
        data = None
        left = None
        right = None
        depth = 0

        # Create a node with some data
        def __init__(self, data):
            self.data = data

        # Set a left node to this node
        def set_left(self, lnode):
            self.left = lnode

        def set_right(self, rnode):
            self.right = rnode

        def get_left(self):
           return self.left.data

        def is_leaf(self):
           if self.left is None and self.right is None:
               return True
           return



       def has_left(self):
           if self.left:
               return True
           return False

       def has_right(self):
           if self.right:
              return True
           return False
# Class for the Btree 
class BTree:
    root = None

    # Create a tree with a base node
    def __init__(self,root):
        self.root = root
        self.count = 0

    # Add node based on the value it's holding

    def insert_node(self,node):
        prev = temp = self.root
        # Traverse until you find the right place to insert the node
        print("Inserting node {}".format(node.data))
        while temp is not None:
            prev = temp
            if node.data < temp.data:
                temp = temp.left
                continue
            if node.data > temp.data:
                temp = temp.right
                continue

        # Go ahead and insert the node here
        if node.data < prev.data:
            prev.set_left(node)
        if node.data > prev.data:
            prev.set_right(node)
    '''
    Pre-order traversal
    Visit the root
    Visit the left subtree
    Visit the right subtree
    '''

    def traverse_pre(self,root):
        # Start with the root
        if root:
            self.count += 1
            print("{}".format(root.data))
            self.traverse_pre(root.left)
            self.traverse_pre(root.right)

    def maxdepth(self, node):
        if node is None:
            return 0
        else:
            # Compute the depth of each subtree
            ldepth = self.maxdepth(node.left)
            rdepth = self.maxdepth(node.right)

            return max(ldepth, rdepth) + 1



if __name__ == '__main__':
    rt = Node(10)
    btree = BTree(rt)
    lst = [14,15,4,9,7,18,5,6,3,54,78,10,100,13,12,11]
    nodes = []
    for i in lst:
        nodes.append(Node(i))
    for node in nodes:
        btree.insert_node(node)
    btree.traverse_pre(rt)
    print("The node count is {}".format(btree.count))
    print(btree.maxdepth(rt))

我的输入没有问题

[14,15,4,9,7,18,5,6,3,54,78,100,13,12,11]

但是当我输入一个额外的 10 时，即

[14,15,4,9,7,18,5,6,3,54,78,10,100,13,12,11]

我看到程序永远不会返回并无限期地等待/运行，任何人都可以帮助我理解这里的问题吗？

Answer 1

列表中的起始数字为 10..

首先将“10”设为变量，n2

n2 = 10
rt = Node(n2)
...

添加一些重复项，当然还有有问题的数字 10

lst = [14,15,4,9,7,18,5,6,3,54,78,100,13,12,11,12,12, 10]

将 lst 更改为集合，这将不允许重复，并将删除任何重复。

lst_set = set()

将 lst 更改为 lst_set。我们在 python 中使用 add 来表示集合，而不是 append

for i in lst:
    lst_set.add(i)

nodes = []
for i in lst_set:

最后检查以确保它不是原始的 n2 数字。

    if i != n2:
        nodes.append(Node(i))

当然，这假设您的原始数据采用列表的形式。如果您从一组开始，则可以避免从列表进行转换。