C语言给出一个按照“扩展遍历序列”的扩展先序遍历序列字符串,'.' 代表空的子节点,大写字母代表节点内容。请通过这个字符串建立二叉树,并计算及输出该二叉树的高度。
时间: 2023-06-07 08:12:17 浏览: 149
给定一个前序的字母字符串,并把它们创建成一个二叉树,并且遍历输出它的中序和后序
好的,我会根据您的问题来建立二叉树,并计算该二叉树的高度。下面是我的代码实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(s):
if not s:
return None
stack = []
root = Node(s[0])
stack.append(root)
i = 1
while i < len(s):
cur = stack[-1]
if s[i] == '.':
if not cur.left:
cur.left = Node(s[i])
elif not cur.right:
cur.right = Node(s[i])
stack.pop()
else:
n = Node(s[i])
if not cur.left:
cur.left = n
elif not cur.right:
cur.right = n
else:
stack.pop()
continue
stack.append(n)
i += 1
return root
def height(root):
if not root:
return 0
left_height = height(root.left)
right_height = height(root.right)
return max(left_height, right_height) + 1
s = "AB..C.D..EF...G..."
root = buildTree(s)
print(height(root))
```
上面的代码中,我们首先定义了一个 `Node` 类来表示节点,然后通过一个 `buildTree` 函数来根据字符串构建二叉树。具体来说,我们使用一个栈来模拟遍历,遇到一个节点时,若其左子节点为空,则将其左子节点赋为当前节点,否则将其右子节点赋为当前节点,然后将该节点出栈;若遇到的是字符 '.',则表示当前节点的某个子节点为空,因此我们分两种情况来处理,即若该节点的左子节点为空,则将其左子节点赋为 None,否则将其右子节点赋为 None。
接下来,我们使用递归的方式来求解二叉树的高度,具体来说,我们先求出左子树的高度和右子树的高度,然后返回两者中较大值加1,即为该二叉树的高度。
最后,我们使用上面的代码来计算给定字符串对应的二叉树的高度,并输出结果。需要注意的是,我们在计算高度的时候需要判断给定二叉树是否为空,若为空则直接返回0。
阅读全文