设计算法,对于1中建立的二叉树进行先序、中序遍历,并计算二叉树的深度、二叉树的叶子结点的个数。
时间: 2024-12-19 09:27:24 浏览: 16
在C++中,我们可以使用递归或迭代的方式来实现二叉树的遍历和计算。这里我会分别介绍先序(Preorder)、中序(Inorder)遍历以及深度(Depth)和叶子节点(Leaf Nodes)的数量。
首先,我们定义一个简单的二叉树节点结构:
```cpp
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
### 先序遍历 (Preorder)
- 访问根节点 -> 左子树 -> 右子树
```cpp
void preorderTraversal(TreeNode* root, vector<int>& result) {
if (root != nullptr) {
result.push_back(root->val); // 访问根节点
preorderTraversal(root->left, result); // 左子树
preorderTraversal(root->right, result); // 右子树
}
}
```
### 中序遍历 (Inorder)
- 左子树 -> 访问根节点 -> 右子树
```cpp
void inorderTraversal(TreeNode* root, vector<int>& result) {
if (root != nullptr) {
inorderTraversal(root->left, result);
result.push_back(root->val); // 访问根节点
inorderTraversal(root->right, result);
}
}
```
### 深度计算 (Depth)
- 使用递归,每次增加一层直到到达空节点
```cpp
int depth(TreeNode* root) {
if (root == nullptr) return 0;
else return 1 + max(depth(root->left), depth(root->right));
}
```
### 叶子节点数量 (Leaf Nodes)
- 判断当前节点是否有左右孩子
```cpp
int leafNodes(TreeNode* root) {
if (root == nullptr) return 0;
else if (root->left == nullptr && root->right == nullptr) return 1; // 如果没有左右孩子则为叶子节点
else return leafNodes(root->left) + leafNodes(root->right);
}
```
现在你可以用这些函数来处理你的二叉树了。如果你有一个具体的二叉树实例,记得提供它的根节点,然后调用上述函数。
阅读全文