python - 如何使用二叉树计算平方根?

我想使用二叉树计算数字的平方根。

思考过程是要有一个起点,当想要将节点放置在左侧或右侧时,插入函数将调用除法函数。

在我的思考过程中,我希望除法函数继续除法,直到数字被均匀除,它会返回一个 value。如果当被除数达到 9 时数字没有被平均分配,那么它将只返回起始数字。

我希望除法函数也能返回被除数,它会进入树的右侧。我提交的代码应该输出 4 2 和 ['4','2']

运行代码时我没有收到任何错误,但是当我运行代码时,输出并不低于初始起始编号

这也是我第一次在 StackOverFlow 上发帖,我是一名尝试学习 data structures 和 algorithms 的新程序员。我的逻辑是有缺陷的,所以如果我能得到一些提示,那就太棒了。谢谢你的帮助!

class Square:
    def __init__(self, start, dividend = 2):
        self.start = start
        self.right = None
        self.left = None
        self.num = self.start
        self.value = None
        self.dividend = dividend
    
    def divide(self, num):
        self.num = num
        if self.num % self.dividend == 0:
            return self.num / self.dividend
        if self.dividend == 9:
            return self.num
        self.divide(num)
        return self.dividend+1
    
    
    def insert(self, num):
        _noDivide = 3
        _divide = 4
        if self.start >= _noDivide:
            self.value = self.divide(self.start)
            if self.value == self.start:
                if self.right is None:
                    self.right = Square(self.num)
                else:
                    self.right.insert(self.num)
            elif self.value >= _divide:
                if self.left is None:
                    self.left = Square(self.num)
                else:
                    self.left.insert(self.num)
        else:
            self.num = num   
 
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print(self.num),
        if self.right:
            self.right.PrintTree()   

    def inorderTraversal(self, root):
        res = []
        if root:
            res = self.inorderTraversal(root.left)
            res.append(root.num)
            res = res + self.inorderTraversal(root.right)
        return res


def main():
    root = Square(8)
    root.insert(root.start)
    root.PrintTree()
    root.inorderTraversal(root)


if __name__ == '__main__':
    main()

回答1

看来你想要一个精确的 surd 形式。质因数分解就可以了。但为了花哨,这里是:

我不确定“插入函数会在想要放置在左侧或右侧的节点中时调用除法函数”是什么意思。但这是我的实现:

被除数取left,商取right。始终在 right 上调用 divide。遵循 divide 的素数分解 algorithm。结果,二叉树中所有 left 的乘积是数字的素数分解。 (是的,所以真的不需要二叉树。)素数分解可以很容易地转换为精确的 surd 形式。

相似文章

key - 如何编辑 JSON Arrays?

我想更改数组中的所有元素,删除我不需要的keys并将名称转换为keys为简单起见。你怎么办?是否有可以以这种方式编辑JSONarrays的简单软件或网站?我的意思是我想变成这样的东西:"一":{"st...