(一)假设二叉树采用二叉链表存储结构,二叉树中结点值为单个字符且所有结点值不相同。设计二叉树的基本运算程序,包括创建二叉链,输出二叉树,求二叉树的高度、结点数和叶子结点数。并用相关数据进行测试。
时间: 2024-12-01 09:12:58 浏览: 11
(一)在使用二叉链表存储结构的二叉树中,我们可以设计如下的基本操作:
1. **创建二叉链**(Insertion):
- 输入一个字符值,创建一个新的节点,并将其设置为根节点。
- 如果节点已存在,则递归地在左或右子链中插入新值,依据当前节点的值和输入值的大小关系。
2. **输出二叉树**(Traversal):
-Left-Right)、中序遍历(Left-Root-Right)或后序遍历(Left-Right-Root)来展示节点顺序。
- 遇到空节点时直接跳过。
3. **求二叉树高度** (Height):
- 使用递归方法计算每个节点的最大子树高度,然后取最大值加一。
- 或者用层次遍历,将每层的高度添加到一个数组中,最后返回最大值。
4. **求结点数** (Node Count):
- 从根节点开始,逐层增加节点总数,直到遍历完整棵树。
5. **求叶子结点数** (Leaf Node Count):
- 叶子节点是没有子节点的节点,所以可以从根节点开始,计数遇到的没有左右指针的节点。
以下是部分伪代码示例:
```python
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def create_binary_tree(char_value):
# 创建新节点并插入到合适位置
pass
def inorder_traversal(root):
if root is not None:
inorder_traversal(root.left)
print(root.val) # 输出节点值
inorder_traversal(root.right)
def height(root):
if root is None:
return 0
else:
left_height = height(root.left)
right_height = height(root.right)
return max(left_height, right_height) + 1
# 完成类似函数以计算节点数和叶节点数
# 测试数据
root = create_binary_tree('a') # 用字符 'a' 初始化根节点
inorder_traversal(root)
print("Height:", height(root))
print("Node count:", total_nodes(root))
print("Leaf node count:", leaf_node_count(root))
```
阅读全文