求二叉树的前中后遍历、统计二叉树结点数、叶了数、求二叉树高度、打印二叉树等操作。
时间: 2024-11-22 13:38:21 浏览: 23
在C++中,对二叉树进行操作通常涉及到递归或迭代的方式。这里我将简要介绍这些常见操作:
1. **前序遍历(Preorder Traversal)**:根节点 -> 左子树 -> 右子树。对于每个节点,先访问该节点,然后递归地访问左子树和右子树。
```cpp
void preorder(TreeNode* root) {
if (root != nullptr) {
std::cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
}
```
2. **中序遍历(Inorder Traversal)**:左子树 -> 根节点 -> 右子树。先遍历左子树,然后访问根节点,最后访问右子树。
```cpp
void inorder(TreeNode* root) {
if (root != nullptr) {
inorder(root->left);
std::cout << root->val << " ";
inorder(root->right);
}
}
```
3. **后序遍历(Postorder Traversal)**:左子树 -> 右子树 -> 根节点。先访问左右子树,最后访问根节点。
```cpp
void postorder(TreeNode* root) {
if (root != nullptr) {
postorder(root->left);
postorder(root->right);
std::cout << root->val << " ";
}
}
```
4. **计算二叉树节点总数(Node Count)**:使用递归,从根节点开始计数,加左子树和右子树的节点数。
```cpp
int countNodes(TreeNode* root) {
return (root == nullptr) ? 0 : 1 + countNodes(root->left) + countNodes(root->right);
}
```
5. **计算叶子节点数量(Leaf Node Count)**:同样递归,如果节点没有子节点,则为叶子节点。
```cpp
int leafCount(TreeNode* root) {
return (root == nullptr) ? 0 : (root->left == nullptr && root->right == nullptr);
}
```
6. **求二叉树的高度(Height)**:通过递归找到最深的分支。可以定义一个辅助函数用于计算最大深度。
```cpp
int height(TreeNode* root) {
if (root == nullptr) return 0;
int left_height = height(root->left);
int right_height = height(root->right);
return std::max(left_height, right_height) + 1;
}
```
7. **层次遍历(Level Order Traversal)**:用队列实现广度优先搜索,逐层访问节点。
```cpp
void levelOrder(TreeNode* root) {
if (root == nullptr) return;
queue<TreeNode*> q {root};
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
std::cout << node->val << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
```
以上代码都是基于二叉树节点`TreeNode`的存在,其中`val`表示节点值,`left`和`right`分别指向左子节点和右子节点。如果你还没定义这样的结构,你需要根据实际的数据结构来调整代码。
阅读全文