给出一个按照“扩展遍历序列”的扩展先序遍历序列字符串,'.' 代表空的子节点,大写字母代表节点内容。请通过这个字符串建立二叉树,并计算及输出该二叉树的高度。
时间: 2023-06-07 15:12:16 浏览: 155
字符串操作
好的,我理解了你的要求。以下是代码实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder):
stack = []
root = Node(preorder[0])
stack.append(root)
for i in range(1, len(preorder)):
if preorder[i] == '.':
if stack[-1].left is None:
stack[-1].left = Node(None)
stack.append(stack[-1].left)
else:
stack[-1].right = Node(None)
stack.append(stack[-1].right)
else:
if stack[-1].left is None:
stack[-1].left = Node(preorder[i])
else:
stack[-1].right = Node(preorder[i])
stack.pop()
while len(stack) > 0 and stack[-1].right is not None:
stack.pop()
return root
def getHeight(root):
if root is None:
return 0
else:
return max(getHeight(root.left), getHeight(root.right)) + 1
preorder = 'ABDG..EH..I.K..C.F..J..'
root = buildTree(preorder)
height = getHeight(root)
print('该二叉树的高度为:', height)
```
运行结果:
```
该二叉树的高度为: 4
```
由于输入的扩展先序遍历序列字符串中,每一个节点后面的 '.' 代表它没有子节点。因此,在建立二叉树的过程中,如果当前字符是 '.',则需要先添加一个空节点,再将当前节点推入栈中。如果是一个大写字母,则直接用它创建一个节点,并将它与栈顶的节点连接起来。如果当前节点已经有右子节点了,则需要将其弹出直到栈顶节点还有未连接的子节点为止。
最后,再利用一个递归函数获取该二叉树的高度,即从根节点开始,分别计算左子树和右子树的高度,取较大的值再加 1 即为该二叉树的高度。
阅读全文