python写一个二叉树
时间: 2023-10-10 08:13:20 浏览: 31
以下是一个简单的二叉树类的 Python 实现:
```python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, value):
# 如果根节点为空,则新节点作为根节点
if self.root is None:
self.root = TreeNode(value)
else:
# 从根节点开始查找插入位置
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = TreeNode(value)
break
else:
current = current.left
elif value > current.value:
if current.right is None:
current.right = TreeNode(value)
break
else:
current = current.right
# 如果节点已存在,则不插入
else:
break
def search(self, value):
current = self.root
while current is not None:
if current.value == value:
return current
elif value < current.value:
current = current.left
else:
current = current.right
return None
def inorder_traversal(self, node):
if node is not None:
self.inorder_traversal(node.left)
print(node.value)
self.inorder_traversal(node.right)
def preorder_traversal(self, node):
if node is not None:
print(node.value)
self.preorder_traversal(node.left)
self.preorder_traversal(node.right)
def postorder_traversal(self, node):
if node is not None:
self.postorder_traversal(node.left)
self.postorder_traversal(node.right)
print(node.value)
```
使用示例:
```python
tree = BinaryTree()
tree.insert(50)
tree.insert(30)
tree.insert(70)
tree.insert(20)
tree.insert(40)
tree.insert(60)
tree.insert(80)
print('Inorder traversal:')
tree.inorder_traversal(tree.root)
print('Preorder traversal:')
tree.preorder_traversal(tree.root)
print('Postorder traversal:')
tree.postorder_traversal(tree.root)
print('Search 60:', tree.search(60).value)
print('Search 100:', tree.search(100))
```
输出:
```
Inorder traversal:
20
30
40
50
60
70
80
Preorder traversal:
50
30
20
40
70
60
80
Postorder traversal:
20
40
30
60
80
70
50
Search 60: 60
Search 100: None
```