建立一棵二叉树(采用二叉链表存储方式); 2.输出该二叉树结点的前序遍历、中序遍历、后序遍历序列。
时间: 2024-04-29 20:26:05 浏览: 111
好的,我会为您解答问题。
首先,建立一棵二叉树(采用二叉链表存储方式)的代码如下:
```python
class BinaryTreeNode:
def __init__(self, val):
self.val = val
self.left_child = None
self.right_child = None
class BinaryTree:
def __init__(self):
self.root = None
def build_tree(self, node_list):
"""
用节点列表构建二叉树
:param node_list: list,节点列表
:return:
"""
nodes = []
for data in node_list:
node = BinaryTreeNode(data)
nodes.append(node)
self.root = nodes[0]
for i in range(len(nodes) // 2):
nodes[i].left_child = nodes[i * 2 + 1]
if i * 2 + 2 < len(nodes):
nodes[i].right_child = nodes[i * 2 + 2]
return self.root
```
接着,输出该二叉树结点的前序遍历、中序遍历、后序遍历序列的代码如下:
```python
def pre_order_traversal(root):
"""
前序遍历二叉树
:param root: 二叉树根节点
:return:
"""
if root:
print(root.val, end=' ')
pre_order_traversal(root.left_child)
pre_order_traversal(root.right_child)
def in_order_traversal(root):
"""
中序遍历二叉树
:param root: 二叉树根节点
:return:
"""
if root:
in_order_traversal(root.left_child)
print(root.val, end=' ')
in_order_traversal(root.right_child)
def post_order_traversal(root):
"""
后序遍历二叉树
:param root: 二叉树根节点
:return:
"""
if root:
post_order_traversal(root.left_child)
post_order_traversal(root.right_child)
print(root.val, end=' ')
```
以上就是如何建立一棵二叉树并输出该二叉树结点的前序遍历、中序遍历、后序遍历序列的代码,希望能为您解决问题。
阅读全文