先序遍历二叉树叶子结点
时间: 2023-11-19 19:06:55 浏览: 48
如果要先序遍历二叉树的叶子结点,可以使用递归的方式实现。具体步骤如下:
1. 如果当前节点为空,则直接返回。
2. 如果当前节点是叶子结点,则输出该节点的值。
3. 如果当前节点不是叶子结点,则递归遍历其左子树和右子树。
代码如下:
```
void preOrderLeafNodes(TreeNode* root) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
cout << root->val << " ";
}
preOrderLeafNodes(root->left);
preOrderLeafNodes(root->right);
}
```
其中,TreeNode是二叉树节点的结构体,包含val、left和right三个成员变量,分别表示节点的值、左子树和右子树。上述代码中,preOrderLeafNodes函数接收一个二叉树的根节点指针root,输出该二叉树中所有叶子节点的值。在函数内部,如果当前节点是空节点,则直接返回;如果当前节点是叶子结点,则输出其值;否则,递归遍历其左子树和右子树。
相关问题
先序遍历发统计叶子结点
对于一棵二叉树,先序遍历的顺序是先遍历根节点,再遍历左子树,最后遍历右子树。统计叶子结点的方法可以在遍历每个节点时进行判断,如果该节点是叶子节点(即左右子树都为空),则叶子结点数加1。
下面是先序遍历统计叶子结点的示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_leaf_nodes(root):
if root is None:
return 0
if root.left is None and root.right is None:
return 1
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
# 示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(count_leaf_nodes(root)) # 输出4
```
在上面的示例代码中,先定义了一个`TreeNode`类来表示二叉树的节点,然后定义了一个`count_leaf_nodes`函数来统计叶子结点数。在函数中,先判断当前节点是否为空或是否是叶子节点,如果是则返回1,否则递归遍历左右子树并将结果相加。最后,通过调用`count_leaf_nodes`函数来统计二叉树的叶子结点数。
完成二叉树的链式存储结构的表示及基本操作实现(构造二叉树、先序遍历二叉树、中 序遍历二叉树、后序遍历二叉树、测二叉树高度、统计二叉树结点数、统计二叉树叶子结点 数目)。
二叉树的链式存储结构是通过节点之间的指针来表示二叉树的结构关系。每个节点包含一个数据元素和两个指针,分别指向左子树和右子树。
下面是基本操作的实现:
1. 构造二叉树:可以通过递归的方式构造二叉树。首先创建一个根节点,然后递归地构造左子树和右子树。
2. 先序遍历二叉树:先访问根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。
3. 中序遍历二叉树:先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。
4. 后序遍历二叉树:先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。
5. 测二叉树高度:可以通过递归的方式计算二叉树的高度。如果二叉树为空,则高度为0;否则,高度等于左子树高度和右子树高度的较大值加1。
6. 统计二叉树结点数:可以通过递归的方式统计二叉树的结点数。如果二叉树为空,则结点数为0;否则,结点数等于左子树结点数加右子树结点数再加1。
7. 统计二叉树叶子结点数目:可以通过递归的方式统计二叉树的叶子结点数目。如果二叉树为空,则叶子结点数目为0;如果二叉树只有一个结点,则叶子结点数目为1;否则,叶子结点数目等于左子树叶子结点数目加右子树叶子结点数目。