1. 利用二叉树的扩展遍历序列生成二叉树,并将二叉树的三种遍历序列全部输出; 2. 将二叉树以横向树形结构输出显示。 3. 统计二叉树的叶子结点个数,并将结果输出。 数据类型定义 :
时间: 2023-06-23 21:20:53 浏览: 45
好的,让我来回答你的问题。
首先,关于问题一,我们可以通过使用递归的方式,根据二叉树的扩展遍历序列生成二叉树。对于每一个节点,我们可以按照先左后右的顺序递归生成左右子树。具体实现可以参考下面的代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(nodes):
if not nodes:
return None
val = nodes.pop(0)
if val == '#':
return None
node = TreeNode(int(val))
node.left = buildTree(nodes)
node.right = buildTree(nodes)
return node
```
其中,`buildTree` 函数接受一个二叉树的扩展遍历序列 `nodes`,并返回对应的二叉树的根节点。
接下来,我们可以通过三种不同的遍历方式,分别输出二叉树的节点值。具体实现可以参考下面的代码:
```python
def preorderTraversal(root):
if not root:
return []
res = []
res.append(root.val)
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
def inorderTraversal(root):
if not root:
return []
res = []
res += inorderTraversal(root.left)
res.append(root.val)
res += inorderTraversal(root.right)
return res
def postorderTraversal(root):
if not root:
return []
res = []
res += postorderTraversal(root.left)
res += postorderTraversal(root.right)
res.append(root.val)
return res
```
其中,`preorderTraversal` 函数实现的是先序遍历,`inorderTraversal` 函数实现的是中序遍历,`postorderTraversal` 函数实现的是后序遍历。这三个函数都接受二叉树的根节点作为参数,并返回对应的遍历结果。
对于问题二,我们可以通过递归的方式,将二叉树以横向树形结构输出显示。具体实现可以参考下面的代码:
```python
def printTree(root):
if not root:
return
printTreeHelper(root, 0)
def printTreeHelper(node, depth):
if not node:
return
printTreeHelper(node.right, depth + 1)
print(' ' * 4 * depth + str(node.val))
printTreeHelper(node.left, depth + 1)
```
其中,`printTree` 函数接受二叉树的根节点作为参数,调用 `printTreeHelper` 函数进行实际的输出。`printTreeHelper` 函数接受当前节点和当前节点的深度作为参数,先递归遍历右子树,再输出当前节点,最后递归遍历左子树。
最后,对于问题三,我们可以通过递归的方式,统计二叉树的叶子结点个数,并将结果输出。具体实现可以参考下面的代码:
```python
def countLeaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return countLeaves(root.left) + countLeaves(root.right)
```
其中,`countLeaves` 函数接受二叉树的根节点作为参数,递归统计左右子树的叶子结点个数,并返回总的叶子结点个数。
希望这些代码可以帮助到你!