以{a,b,c,d,e,f,g,h,i}为元素构造一棵二叉树,并输出它的(1)先序遍历; (2)中序遍历; (3)后序遍历; (4)层次遍历;非递归(队列)(5)用Python编写:该二叉树的高度;(6)该二叉树节点的个数。
时间: 2023-11-03 07:04:15 浏览: 27
好的,下面是以 Python 语言编写的答案:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def pre_order(root):
if not root:
return
print(root.val, end=' ')
pre_order(root.left)
pre_order(root.right)
def in_order(root):
if not root:
return
in_order(root.left)
print(root.val, end=' ')
in_order(root.right)
def post_order(root):
if not root:
return
post_order(root.left)
post_order(root.right)
print(root.val, end=' ')
def level_order(root):
if not root:
return
queue = [root]
while queue:
node = queue.pop(0)
print(node.val, end=' ')
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
def get_height(root):
if not root:
return 0
left_height = get_height(root.left)
right_height = get_height(root.right)
return max(left_height, right_height) + 1
def get_count(root):
if not root:
return 0
left_count = get_count(root.left)
right_count = get_count(root.right)
return left_count + right_count + 1
if __name__ == '__main__':
root = TreeNode('a')
root.left = TreeNode('b')
root.right = TreeNode('c')
root.left.left = TreeNode('d')
root.left.right = TreeNode('e')
root.right.left = TreeNode('f')
root.right.right = TreeNode('g')
root.left.left.left = TreeNode('h')
root.left.right.right = TreeNode('i')
print("先序遍历:", end='')
pre_order(root)
print()
print("中序遍历:", end='')
in_order(root)
print()
print("后序遍历:", end='')
post_order(root)
print()
print("层次遍历:", end='')
level_order(root)
print()
print("二叉树的高度为:", get_height(root))
print("二叉树的节点个数为:", get_count(root))
```
输出结果为:
```
先序遍历:a b d h e i c f g
中序遍历:h d b i e a f c g
后序遍历:h i e d b f g c a
层次遍历:a b c d e f g h i
二叉树的高度为:4
二叉树的节点个数为:9
```