问题描述:设计一个与二叉树基本操作相关的演示程序。 要求: (1) 创建二叉树。 (2) 将创建的二叉树,以树状形式输出。 (3) 分别以先序、中序、后序三种遍历方式访问二叉树。 (4) 输出二叉树中的叶子结点以及叶子结点的个数。 (5) 输出二叉树的高度。
时间: 2024-04-30 16:19:47 浏览: 49
二叉树基本操作演示程序的设计与实现.doc
以下是 Python 语言的实现代码:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
self.leaf_count = 0
def insert(self, val):
if not self.root:
self.root = Node(val)
return
queue = []
queue.append(self.root)
while queue:
node = queue.pop(0)
if not node.left:
node.left = Node(val)
return
else:
queue.append(node.left)
if not node.right:
node.right = Node(val)
return
else:
queue.append(node.right)
def print_tree(self):
if not self.root:
return
queue = []
queue.append(self.root)
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.pop(0)
print(node.val, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
print()
def preorder_traversal(self, node):
if not node:
return
print(node.val, end=" ")
self.preorder_traversal(node.left)
self.preorder_traversal(node.right)
def inorder_traversal(self, node):
if not node:
return
self.inorder_traversal(node.left)
print(node.val, end=" ")
self.inorder_traversal(node.right)
def postorder_traversal(self, node):
if not node:
return
self.postorder_traversal(node.left)
self.postorder_traversal(node.right)
print(node.val, end=" ")
def count_leaves(self, node):
if not node:
return
if not node.left and not node.right:
self.leaf_count += 1
print(node.val, end=" ")
self.count_leaves(node.left)
self.count_leaves(node.right)
def get_height(self, node):
if not node:
return 0
left_height = self.get_height(node.left)
right_height = self.get_height(node.right)
return max(left_height, right_height) + 1
tree = BinaryTree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
print("Binary Tree:")
tree.print_tree()
print("Preorder Traversal:")
tree.preorder_traversal(tree.root)
print()
print("Inorder Traversal:")
tree.inorder_traversal(tree.root)
print()
print("Postorder Traversal:")
tree.postorder_traversal(tree.root)
print()
print("Leaves:")
tree.count_leaves(tree.root)
print()
print("Leaf Count:", tree.leaf_count)
print("Height:", tree.get_height(tree.root))
```
这个程序创建了一个二叉树,然后输出了它的树状形式以及进行了先序、中序和后序三种遍历方式的遍历,输出了二叉树中的叶子结点以及叶子结点的个数,并且输出了二叉树的高度。
阅读全文