建立一棵二叉树,实现二叉树前序遍历、中序遍历、后序遍历遍历和其他操作。
时间: 2024-01-23 09:40:25 浏览: 28
好的,我来给你介绍一下二叉树和它的遍历方式。
二叉树是一种树形结构,它的每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树的遍历方式有三种:前序遍历、中序遍历和后序遍历。
前序遍历是从根节点开始,先访问根节点,然后遍历左子树,最后遍历右子树。中序遍历是先遍历左子树,然后访问根节点,最后遍历右子树。后序遍历是先遍历左子树,然后遍历右子树,最后访问根节点。
下面我们来实现一个二叉树,并对它进行遍历。
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, val):
node = TreeNode(val)
if self.root is None:
self.root = node
else:
queue = []
queue.append(self.root)
while queue:
curr = queue.pop(0)
if curr.left is None:
curr.left = node
return
elif curr.right is None:
curr.right = node
return
else:
queue.append(curr.left)
queue.append(curr.right)
def preorderTraversal(self):
def dfs(node):
if not node:
return
res.append(node.val)
dfs(node.left)
dfs(node.right)
res = []
dfs(self.root)
return res
def inorderTraversal(self):
def dfs(node):
if not node:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
res = []
dfs(self.root)
return res
def postorderTraversal(self):
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
res.append(node.val)
res = []
dfs(self.root)
return res
def levelorderTraversal(self):
queue = []
res = []
if self.root is None:
return res
queue.append(self.root)
while queue:
level = []
for _ in range(len(queue)):
curr = queue.pop(0)
level.append(curr.val)
if curr.left:
queue.append(curr.left)
if curr.right:
queue.append(curr.right)
res.append(level)
return res
```
在上面的代码中,我们定义了一个 `TreeNode` 类表示二叉树的每个节点,包括节点的值和左右子节点。然后我们定义了一个 `BinaryTree` 类,其中包括插入节点和遍历二叉树的方法。我们使用列表来实现队列,实现了二叉树的层序遍历。
接下来我们创建一个二叉树,并对它进行遍历:
```python
tree = BinaryTree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
print("前序遍历:", tree.preorderTraversal())
print("中序遍历:", tree.inorderTraversal())
print("后序遍历:", tree.postorderTraversal())
print("层序遍历:", tree.levelorderTraversal())
```
输出结果如下:
```
前序遍历: [1, 2, 4, 5, 3]
中序遍历: [4, 2, 5, 1, 3]
后序遍历: [4, 5, 2, 3, 1]
层序遍历: [[1], [2, 3], [4, 5]]
```
这就是一个简单的二叉树的实现和遍历方式。