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

Question

我想用二叉树来计算一个数的平方根。

我们的想法是有一个起始点，当想要在左边或右边放置一个节点时，插入函数将调用除法函数。

在我的思考过程中，我希望除法函数一直除法，直到数字被平均除法，它将返回一个值。如果当红利达到9时，这个数字没有被平均分成，那么它将只返回开始的数字。

我想让除法函数也返回被除数，它应该在树的右边。我提交的代码应该输出4 2和['4'，'2']

我没有得到任何错误运行代码，但当我运行代码它的输出不低于初始的起始数

这也是我第一次在StackOverFlow上发帖，我是一个试图学习数据结构和算法的新程序员。我的逻辑是有缺陷的，所以如果我能得到一些建议，那将是惊人的。谢谢你的帮助!

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()

Answer 1

您似乎想要一个精确的格式。质因数分解就可以了。但为了更花哨，这里是:

我不确定你所说的"插入函数"是什么意思;当想要在左侧或右侧放置节点时，"插入函数"将调用"划分函数"。下面是我的实现:

股利取left，商取right。在right上始终呼叫divide。遵循divide的质因数分解算法。因此，二叉树中所有left的乘积是该数的质因数分解。(是的，不需要二叉树。)质因数分解可以很容易地转化为精确的复数形式。