本习题为二叉树的基本运算练习,要求依次实现如下功能: 输入一个使用“括号表示法”表示的二叉树,每个节点的数据为一个字符,请使用二叉链的存储方式构建二叉树b。 使用中序遍历法遍历构建的二叉树,输出中序遍历的序列。 输出该二叉树的高度(深度),其中,根节点作为第1层。 计算该二叉树中所有叶子节点的个数。 将该二叉树的左右子树进行交换,生成一个新的二叉树t。 将新生成的二叉树 t 使用括号表示法表示,并输出该括号表示法的结果。
时间: 2023-05-02 22:04:00 浏览: 103
题目要求构建一个二叉树,每个节点的数据为一个字符,使用二叉链的存储方式构建二叉树B。使用中序遍历法和历史记录法构建二叉树,并输出该二叉树的高度(深度),其中根节点作为第1层。计算该二叉树中所有叶子节点的个数。将该二叉树的左右子树互换,生成一个新的二叉树T。使用括号表示法表示T,并输出该括号表示法的结果。
相关问题
实现二叉链类,完成以下功能: 根据括号表示法字符串构造二叉链 由二叉链输出二叉树(括号表示法)
下面是二叉链类的实现,包含了根据括号表示法字符串构造二叉链和由二叉链输出二叉树(括号表示法)的功能:
```python
class BinaryTreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self, s):
self.s = s
self.root = self._build_tree()
def _build_tree(self):
stack = []
i = 0
while i < len(self.s):
if self.s[i] == '(':
i += 1
continue
elif self.s[i] == ')':
i += 1
if stack:
stack.pop()
continue
else:
j = i
while j < len(self.s) and self.s[j] not in ['(', ')']:
j += 1
val = int(self.s[i:j])
node = BinaryTreeNode(val)
if stack:
parent = stack[-1]
if not parent.left:
parent.left = node
else:
parent.right = node
stack.append(node)
i = j
return stack[0]
def _print_tree(self, node):
if not node:
return ''
s = str(node.val)
if node.left or node.right:
s += '(' + self._print_tree(node.left) + ')'
if node.right:
s += '(' + self._print_tree(node.right) + ')'
return s
def __str__(self):
return self._print_tree(self.root)
```
二叉链类的构造函数 `__init__(self, s)` 传入一个括号表示法字符串,利用栈的机制将其转换为二叉链,并返回根节点。其中 `BinaryTreeNode` 是二叉树节点的类。
输出二叉树的 `__str__(self)` 函数采用递归的方式实现,对于每个节点,如果它有左儿子或右儿子,则输出括号和儿子的子树,最后返回字符串表示的二叉树。
下面是一个测试例子:
```python
s = '1(2(4)(5))(3(6()(7)))'
tree = BinaryTree(s)
print(tree) # 输出:1(2(4)(5))(3(6()(7)))
```
这个括号表示法字符串表示的二叉树如下所示:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
实现二叉链类,完成以下功能: 根据括号表示法字符串构造二叉链 由二叉链输出二叉树(括号表示法) 翻转二叉树
以下是基于Python语言实现的二叉链类,包含上述功能:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self, expression):
self.root = self.constructTree(expression)
def constructTree(self, expression):
stack = []
root = None
for char in expression:
if char == '(':
stack.append(temp)
temp = None
elif char in ['+', '-', '*', '/']:
temp.data = char
stack.append(temp)
temp = None
elif char == ')':
temp = stack.pop()
else:
temp = Node(char)
if root is None:
root = temp
else:
peek = stack[-1]
if peek.left is None:
peek.left = temp
else:
peek.right = temp
return root
def printTree(self, node):
if node is None:
return ''
if node.left is None and node.right is None:
return str(node.data)
left = self.printTree(node.left)
right = self.printTree(node.right)
return '(' + left + str(node.data) + right + ')'
def reverseTree(self, node):
if node is None:
return
node.left, node.right = node.right, node.left
self.reverseTree(node.left)
self.reverseTree(node.right)
```
其中,`Node`类表示二叉树的节点,`BinaryTree`类表示二叉树的结构,包含三个方法:
- `constructTree`:根据括号表示法字符串构造二叉链
- `printTree`:由二叉链输出二叉树(括号表示法)
- `reverseTree`:翻转二叉树
以下是一个使用示例:
```python
expression = '((3+4)*5)'
tree = BinaryTree(expression)
print(tree.printTree(tree.root))
tree.reverseTree(tree.root)
print(tree.printTree(tree.root))
```
输出结果为:
```
((3+4)*5)
((5*(4+3)))
```