数据结构建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果;
时间: 2023-07-10 16:15:05 浏览: 78
对所建立的二叉树分别进行先序、中序和后序遍历,并输出结果。
4星 · 用户满意度95%
好的,以下是建立二叉树并进行遍历的示例代码:
```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, root=None):
self.root = root
def build_tree(self, nodes):
self.root = self._build_tree(nodes, 0)
def _build_tree(self, nodes, i):
if i < len(nodes):
if nodes[i] is None:
return None
node = TreeNode(nodes[i])
node.left = self._build_tree(nodes, 2*i+1)
node.right = self._build_tree(nodes, 2*i+2)
return node
def preorder_traversal(self, node):
if node:
print(node.val, end=' ')
self.preorder_traversal(node.left)
self.preorder_traversal(node.right)
def inorder_traversal(self, node):
if node:
self.inorder_traversal(node.left)
print(node.val, end=' ')
self.inorder_traversal(node.right)
def postorder_traversal(self, node):
if node:
self.postorder_traversal(node.left)
self.postorder_traversal(node.right)
print(node.val, end=' ')
```
以上代码实现了二叉树的建立、先序遍历、中序遍历和后序遍历功能。下面是使用示例:
```python
nodes = [1, 2, 3, None, None, 4, 5]
bt = BinaryTree()
bt.build_tree(nodes)
print('Preorder traversal:')
bt.preorder_traversal(bt.root)
print('\nInorder traversal:')
bt.inorder_traversal(bt.root)
print('\nPostorder traversal:')
bt.postorder_traversal(bt.root)
```
输出结果如下:
```
Preorder traversal:
1 2 4 5 3
Inorder traversal:
4 2 5 1 3
Postorder traversal:
4 5 2 3 1
```
阅读全文