在python中实现二叉树？
在python中实现二叉树？
提问于 2020-11-09 06:05:24
我试图在python中为BST做插入函数，但我只是对如何正确地访问公共方法感到困惑，这给我带来了一些痛苦，现在当我测试它时，它只是停留在第一个测试，并指出非类型对象没有属性数据，但是当t= tree()并且tree没有数据构造器时，我如何访问数据？
class Node(object):
def __init__(self, data):
self.parent = None
self.left = None
self.right = None
self.data = data
class Tree(object):
# Binary Search Tree
# class constants
PREORDER = 1
INORDER = 2
POSTORDER = 3
def __init__(self):
# Do not create any other private variables.
# You may create more helper methods as needed.
self.root = None
def print(self):
# Print the data of all nodes in order
self.__print(self.root)
def __print(self, curr_node):
# Recursively print a subtree (in order), rooted at curr_node
if curr_node is not None:
self.__print(curr_node.left)
print(str(curr_node.data), end=' ') # save space
self.__print(curr_node.right)
def insert(self, data):
# Find the right spot in the tree for the new node
# Make sure to check if anything is in the tree
# Hint: if a node n is null, calling n.getData() will cause an error
root = Node(data)
print("this is my", self.root)
if self.root is None:
self.root = root
return Node(data)
else:
if root.data == data:
return root
elif root.data < data:
root.right = insert(root.right,data)
else:
root.left = insert(root.left, data)
return root这是我正在运行的测试用例
import lab3
import unittest
class T0_tree__insert(unittest.TestCase):
def test_balanced_binary_search_tree(self):
print("\n")
print("tree_insert_with_individual_check")
t = lab3.Tree()
t.insert(4)
t.insert(2)
t.insert(6)
t.insert(1)
t.insert(3)
t.insert(5)
t.insert(7)
#The following check is without using tree as an iterator (which uses inorder traversal)
#So this function also does not check the implementation of the traversal function
self.assertEqual(t.root.data, 4)
self.assertEqual(t.root.left.data, 2)
self.assertEqual(t.root.left.left.data, 1)
self.assertEqual(t.root.left.right.data, 3)
self.assertEqual(t.root.right.data, 6)
self.assertEqual(t.root.right.left.data, 5)
self.assertEqual(t.root.right.right.data, 7)
print("\n")回答 1
Stack Overflow用户
发布于 2020-11-09 07:36:47
提供了两个选项
- 为插入到树中添加了辅助函数(类似于辅助打印函数__print)。这允许跟踪我们在tree
- Non-recursive插入中遍历的节点，该插入通过节点进行处理。
这两个选项都满足unittest。
选项1-添加实用程序函数以插入
文件labe3.py
class Node(object):
def __init__(self, data):
self.parent = None
self.left = None
self.right = None
self.data = data
class Tree(object):
# Binary Search Tree
# class constants
PREORDER = 1
INORDER = 2
POSTORDER = 3
def __init__(self):
# Do not create any other private variables.
# You may create more helper methods as needed.
self.root = None
def print(self):
# Print the data of all nodes in order
self.__print(self.root)
def __print(self, curr_node):
# Recursively print a subtree (in order), rooted at curr_node
if curr_node is not None:
self.__print(curr_node.left)
print(str(curr_node.data), end=' ') # save space
self.__print(curr_node.right)
def insert(self, d):
print("this is my", self.root)
if self.root is None:
self.root = Node(d)
else:
self._insert(self.root, d) # here's the call to a "private" function to which we are passing nodes down, starting from root
def _insert(self, node, value):
''' helper function for insert
node - node in BST to add value
value - value to add
'''
if value < node.data: # we know that `node` cannot be None
# so it's safe to check its value!
if node.left:
self._insert(node.left, value) # the recursive call is done only when `node.left` is not None
else:
node.left = Node(value) # direct assignment
else:
if node.right:
self._insert(node.right, value)
else:
node.right = Node(value) # direct assignment选项2-非递归插入函数
文件labe3.py
class Node(object):
def __init__(self, data):
self.parent = None
self.left = None
self.right = None
self.data = data
class Tree(object):
# Binary Search Tree
# class constants
PREORDER = 1
INORDER = 2
POSTORDER = 3
def __init__(self):
# Do not create any other private variables.
# You may create more helper methods as needed.
self.root = None
def print(self):
# Print the data of all nodes in order
self.__print(self.root)
def __print(self, curr_node):
# Recursively print a subtree (in order), rooted at curr_node
if curr_node is not None:
self.__print(curr_node.left)
print(str(curr_node.data), end=' ') # save space
self.__print(curr_node.right)
def insert(self, d):
print("this is my", self.root)
if self.root is None:
self.root = Node(d)
else:
# current node
current = self.root
# Finds node to add data
while True:
if current.data > d:
if current.left == None:
current.left = Node(d)
break
else:
current = current.left
elif current.data < d:
if current.right == None:
current.right = Node(d)
break
else:
current = current.right
else:
break文件main.py
import lab3
import unittest
class T0_tree__insert(unittest.TestCase):
def test_balanced_binary_search_tree(self):
print("\n")
print("tree_insert_with_individual_check")
t = lab3.Tree()
t.insert(4)
t.insert(2)
t.insert(6)
t.insert(1)
t.insert(3)
t.insert(5)
t.insert(7)
#The following check is without using tree as an iterator (which uses inorder traversal)
#So this function also does not check the implementation of the traversal function
self.assertEqual(t.root.data, 4)
self.assertEqual(t.root.left.data, 2)
self.assertEqual(t.root.left.left.data, 1)
self.assertEqual(t.root.left.right.data, 3)
self.assertEqual(t.root.right.data, 6)
self.assertEqual(t.root.right.left.data, 5)
self.assertEqual(t.root.right.right.data, 7)
print("\n")
if __name__ == '__main__':
unittest.main()输出
tree_insert_with_individual_check
this is my None
this is my <lab3.Node object at 0x7fa4386b92e0>
this is my <lab3.Node object at 0x7fa4386b92e0>
this is my <lab3.Node object at 0x7fa4386b92e0>
this is my <lab3.Node object at 0x7fa4386b92e0>
this is my <lab3.Node object at 0x7fa4386b92e0>
this is my <lab3.Node object at 0x7fa4386b92e0>
.
----------------------------------------------------------------------
Ran 1 test in 0.001s
OK页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64743504
复制相关文章
相似问题
腾讯云开发者
