首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >将节点插入二叉树

将节点插入二叉树
EN

Stack Overflow用户
提问于 2018-02-03 03:13:26
回答 1查看 623关注 0票数 1

我正在尝试实现一个Binary Tree以及用于插入节点、遍历节点等的支持方法。我有一种特殊的情况,在这种情况下,我的代码进入循环,或者等待太久才能返回特定的输入。鉴于我所面临的问题,我认为它是独特的,因此我张贴它,我试图了解我可能做错了什么。以下是我的代码:

代码语言:javascript
代码运行次数:0
运行
复制
# 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,54,78,100,13,12,11

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

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

我看到程序永远不会返回,等待/无限期运行,有人能帮助我理解这里的问题吗?

EN

回答 1

Stack Overflow用户

发布于 2018-02-03 04:37:21

你的名单上有第10位。

首先将'10‘变成一个变量,n2

代码语言:javascript
代码运行次数:0
运行
复制
n2 = 10
rt = Node(n2)
...

在其中加上一些重复的,当然还有违规的数字10

代码语言:javascript
代码运行次数:0
运行
复制
lst = [14,15,4,9,7,18,5,6,3,54,78,100,13,12,11,12,12, 10]

将lst更改为set,这将不允许重复,并将删除任何副本。

代码语言:javascript
代码运行次数:0
运行
复制
lst_set = set()

换乘lst_set。我们将add用于python中的集合,而不是append

代码语言:javascript
代码运行次数:0
运行
复制
for i in lst:
    lst_set.add(i)

nodes = []
for i in lst_set:

最后检查,以确保它不是原来的n2号码。

代码语言:javascript
代码运行次数:0
运行
复制
    if i != n2:
        nodes.append(Node(i))

当然,这假定您的原始数据是以列表形式出现的。如果以集合开头,则可以避免从列表中进行转换。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/48593572

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档