用Python实现 以{1,2,3,4,5,6,7,8,9}为元素构造一棵二叉树,并输出它的 (1)先序遍历; (2)中序遍历; (3)后序遍历; (4)层次遍历;非递归(队列) (5)该二叉树的高度; (6)该二叉树节点的个数。 输入:123456789 先序遍历:124895367 中序遍历:849251637 后序遍历:894526731
时间: 2023-07-22 08:06:44 浏览: 199
下面是使用 Python 实现该二叉树的代码:
```python
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def build_tree(s):
if len(s) == 0:
return None
root = Node(s[0])
index = 1
queue = [root]
while index < len(s):
node = queue.pop(0)
if s[index] != '#':
node.left = Node(s[index])
queue.append(node.left)
index += 1
if index >= len(s):
break
if s[index] != '#':
node.right = Node(s[index])
queue.append(node.right)
index += 1
return root
def pre_order_traversal(root):
if root is None:
return
print(root.value, end=' ')
pre_order_traversal(root.left)
pre_order_traversal(root.right)
def in_order_traversal(root):
if root is None:
return
in_order_traversal(root.left)
print(root.value, end=' ')
in_order_traversal(root.right)
def post_order_traversal(root):
if root is None:
return
post_order_traversal(root.left)
post_order_traversal(root.right)
print(root.value, end=' ')
def level_order_traversal(root):
if root is None:
return
queue = [root]
while len(queue) > 0:
node = queue.pop(0)
print(node.value, end=' ')
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
def get_height(root):
if root is None:
return 0
left_height = get_height(root.left)
right_height = get_height(root.right)
return max(left_height, right_height) + 1
def get_node_count(root):
if root is None:
return 0
left_count = get_node_count(root.left)
right_count = get_node_count(root.right)
return left_count + right_count + 1
s = '123456789'
root = build_tree(s)
print('先序遍历:', end='')
pre_order_traversal(root)
print()
print('中序遍历:', end='')
in_order_traversal(root)
print()
print('后序遍历:', end='')
post_order_traversal(root)
print()
print('层次遍历:', end='')
level_order_traversal(root)
print()
print('二叉树高度:', get_height(root))
print('二叉树节点个数:', get_node_count(root))
```
输出结果如下所示:
```
先序遍历:1 2 4 8 9 5 3 6 7
中序遍历:8 4 9 2 5 1 6 3 7
后序遍历:8 9 4 5 2 6 7 3 1
层次遍历:1 2 3 4 5 6 7 8 9
二叉树高度: 4
二叉树节点个数: 9
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)