python实现二叉树
时间: 2023-12-01 16:42:30 浏览: 53
以下是Python实现二叉树的示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
self._insert(val, self.root)
def _insert(self, val, node):
if val < node.val:
if node.left:
self._insert(val, node.left)
else:
node.left = TreeNode(val)
else:
if node.right:
self._insert(val, node.right)
else:
node.right = TreeNode(val)
def inorder_traversal(self):
res = []
self._inorder_traversal(self.root, res)
return res
def _inorder_traversal(self, node, res):
if not node:
return
self._inorder_traversal(node.left, res)
res.append(node.val)
self._inorder_traversal(node.right, res)
def preorder_traversal(self):
res = []
self._preorder_traversal(self.root, res)
return res
def _preorder_traversal(self, node, res):
if not node:
return
res.append(node.val)
self._preorder_traversal(node.left, res)
self._preorder_traversal(node.right, res)
def postorder_traversal(self):
res = []
self._postorder_traversal(self.root, res)
return res
def _postorder_traversal(self, node, res):
if not node:
return
self._postorder_traversal(node.left, res)
self._postorder_traversal(node.right, res)
res.append(node.val)
```
这个二叉树类包含了插入节点、中序遍历、前序遍历和后序遍历等方法。其中,插入节点方法使用递归实现,遍历方法使用了递归和栈两种方式。