先序序列创建二叉树,输出先序序列、中序序列、后序序列并输出叶子结点数
时间: 2023-05-31 16:18:42 浏览: 226
### 回答1:
先序遍历二叉树可以通过使用根结点、左子树、右子树的顺序来遍历整棵二叉树。中序遍历则是左子树、根结点、右子树的顺序遍历整棵二叉树。而后序遍历则是左子树、右子树、根结点的顺序遍历整棵二叉树。计算叶子结点数量可以通过判断每个结点是否有左右子树来确定。
### 回答2:
首先需要了解什么是先序序列、中序序列、后序序列。以先序序列为例,指的是对于一个二叉树,先输出二叉树的根节点,然后输出它的左子树的先序序列,再输出它的右子树的先序序列。而中序序列是指,在输出二叉树的中序序列时,先输出它的左子树的中序序列,然后输出它的根节点,再输出它的右子树的中序序列。后序序列是指,先输出二叉树的左子树的后序序列,然后输出它的右子树的后序序列,最后输出它的根节点。
接下来,我们可以根据先序序列和中序序列构建一个二叉树。由于先序序列的第一个节点是根节点,所以我们可以先找到它,然后根据它在中序序列中的位置,将中序序列一分为二,前半部分即为它的左子树的中序序列,后半部分即为它的右子树的中序序列。然后我们可以依次递归建立它的左子树、右子树。最后输出先序序列、中序序列、后序序列以及叶子结点数即可。
代码如下:
``` python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root = None # 二叉树的根节点
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
"""
根据先序序列和中序序列构建二叉树
"""
if not preorder: # 先序序列为空,返回None
return None
root_val = preorder[0] # 先序序列的第一个节点为根节点
root = TreeNode(root_val)
i = inorder.index(root_val) # 在中序序列中找到根节点的位置
# 递归构建左子树
root.left = self.buildTree(preorder[1:i+1], inorder[:i])
# 递归构建右子树
root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
self.root = root
return root
def preorder(self, node: TreeNode) -> None:
"""
先序遍历
"""
if not node:
return
print(node.val, end=' ')
self.preorder(node.left)
self.preorder(node.right)
def inorder(self, node: TreeNode) -> None:
"""
中序遍历
"""
if not node:
return
self.inorder(node.left)
print(node.val, end=' ')
self.inorder(node.right)
def postorder(self, node: TreeNode) -> None:
"""
后序遍历
"""
if not node:
return
self.postorder(node.left)
self.postorder(node.right)
print(node.val, end=' ')
def countLeaf(self, node: TreeNode) -> int:
"""
计算叶子结点个数
"""
if not node:
return 0
if not node.left and not node.right:
return 1
return self.countLeaf(node.left) + self.countLeaf(node.right)
preorder = [1, 2, 4, 5, 3, 6]
inorder = [4, 2, 5, 1, 3, 6]
bt = BinaryTree()
bt.buildTree(preorder, inorder)
print('先序序列:', end='')
bt.preorder(bt.root)
print()
print('中序序列:', end='')
bt.inorder(bt.root)
print()
print('后序序列:', end='')
bt.postorder(bt.root)
print()
print('叶子结点个数:', bt.countLeaf(bt.root))
```
输出结果:
```
先序序列:1 2 4 5 3 6
中序序列:4 2 5 1 3 6
后序序列:4 5 2 6 3 1
叶子结点个数:3
```
因为二叉树的根节点的值是唯一的,所以我们可以使用列表索引的方式来找到它在中序序列中的位置。而如果二叉树中存在重复元素,我们就不能使用这种方式来构建二叉树。此时,我们可以在先序序列中记录每个节点的出现次数,并将其作为参数传递给子函数,以判断节点是否已经被构建。如果此节点出现次数为0,则说明该节点还未被构建,可以构建它。如果出现次数不为0,则说明该节点已经被构建,在构建左子树和右子树时需要跳过该节点。
### 回答3:
二叉树是一种树形结构,其中每个节点最多有两个子节点。二叉树具有很多应用,如排序、二叉查找树、AVL树、红黑树等。在使用二叉树时,我们需要了解如何创建二叉树,并且知道如何输出二叉树的先序序列、中序序列、后序序列以及二叉树的叶子节点数。下面将对上述问题进行详细介绍。
一、创建二叉树
创建二叉树的过程可以通过递归来完成。具体步骤如下:
1.从先序序列中取出第一个元素,并将其作为根节点。
2.在中序序列中查找根节点,找到其位置后,把中序序列分成两部分,一部分是左子树的中序序列,一部分是右子树的中序序列。
3.在先序序列中找到左子树的第一个节点,把剩余部分作为右子树的先序序列。
4.递归创建左右子树。
代码示例:
二、输出先序序列、中序序列、后序序列
输出先序序列、中序序列、后序序列分别是遍历二叉树的三种方式。具体方法如下:
1.先序遍历(根-左-右):先输出根节点的值,然后递归输出左子树的先序序列,最后递归输出右子树的先序序列。
2.中序遍历(左-根-右):先递归输出左子树的中序序列,然后输出根节点的值,最后递归输出右子树的中序序列。
3.后序遍历(左-右-根):先递归输出左子树的后序序列,然后递归输出右子树的后序序列,最后输出根节点的值。
代码示例:
三、输出叶子节点数
叶子节点是指二叉树中没有子节点的节点,又称为终端节点。输出叶子节点数需要遍历整个二叉树,在访问每个节点时统计叶子节点的数量。
代码示例:
综上所述,本文介绍了如何创建二叉树,以及如何输出二叉树的先序序列、中序序列、后序序列和叶子节点数。在实际应用中,我们可以根据需要选择不同的遍历方式,并根据具体需求调整代码。
阅读全文