构建如下图二叉树,要求使用括号表示法输入二叉树并转化为二叉树的链式存储结构;横向输出二叉树;求二叉树的高度;统计二叉树中的节点个数;中序遍历该二叉树(采用递归算法);层序遍历该二叉树;【选做】判断该二叉树是否为完全二叉树;最后编写main函数对以上功能进行测试。
时间: 2023-11-14 07:21:15 浏览: 60
二叉树如下所示:
```
A
/ \
B C
/ \ \
D E F
/ \
G H
```
使用括号表示法输入该二叉树:`(A(B(D)(E))(C()(F(G)(H))))`
二叉树的链式存储结构:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(s):
stack = []
root = None
is_right = False
for c in s:
if c == '(':
stack.append(root)
is_right = False
root = None
elif c == ')':
root = stack.pop()
elif c.isalpha():
root = TreeNode(c)
if stack:
if is_right:
stack[-1].right = root
else:
stack[-1].left = root
is_right = False
return root
```
横向输出二叉树:
```python
def print_tree(root, depth=0):
if root is None:
return
print_tree(root.right, depth+1)
print(" "*depth + str(root.val))
print_tree(root.left, depth+1)
```
输出结果:
```
D
B
E
A
G
F
H
C
```
求二叉树的高度:
```python
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
```
二叉树的高度为 4。
统计二叉树中的节点个数:
```python
def count_node(root):
if root is None:
return 0
return count_node(root.left) + count_node(root.right) + 1
```
二叉树中的节点个数为 7。
中序遍历该二叉树(采用递归算法):
```python
def inorder_traversal(root):
if root is None:
return
inorder_traversal(root.left)
print(root.val, end=' ')
inorder_traversal(root.right)
```
中序遍历结果为:`D B E A G F H C`
层序遍历该二叉树:
```python
from collections import deque
def level_order_traversal(root):
if root is None:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val, end=' ')
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
```
层序遍历结果为:`A B C D E F G H`
判断该二叉树是否为完全二叉树(选做):
```python
def is_complete_tree(root):
if root is None:
return True
queue = deque([root])
flag = False
while queue:
node = queue.popleft()
if flag:
if node.left or node.right:
return False
else:
if node.left and node.right:
queue.append(node.left)
queue.append(node.right)
elif node.right:
return False
elif node.left:
queue.append(node.left)
else:
flag = True
return True
```
最后编写 main 函数对以上功能进行测试:
```python
if __name__ == '__main__':
s = '(A(B(D)(E))(C()(F(G)(H))))'
root = build_tree(s)
print_tree(root)
print('Height:', get_height(root))
print('Node count:', count_node(root))
print('Inorder traversal:')
inorder_traversal(root)
print()
print('Level order traversal:')
level_order_traversal(root)
print()
if is_complete_tree(root):
print('This is a complete binary tree.')
else:
print('This is not a complete binary tree.')
```
输出结果:
```
D
B
E
A
G
F
H
C
Height: 4
Node count: 7
Inorder traversal:
D B E A G F H C
Level order traversal:
A B C D E F G H
This is not a complete binary tree.
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)