用c++写一段代码,满足以下要求:1.-定义二叉链存储结构。 2-建立二叉链表存储的二叉树。 3.-实现二叉树的先序遍历、中序遍历和后序遍历。 4.-实现求二叉树的高度、求结点双亲、统计叶子结点数目的操作。5.-编写测试主函数,测试所实现的操作,并进行分析。
时间: 2024-10-23 11:07:30 浏览: 30
在C++中,我们可以首先定义一个二叉链节点的数据结构,然后构建二叉树并实现所需的遍历和属性计算功能。以下是相关的代码示例:
```cpp
#include <iostream>
using namespace std;
// 定义二叉链表节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 先序遍历
void preorderTraversal(TreeNode* root) {
if (root != nullptr) {
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root != nullptr) {
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root != nullptr) {
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
}
// 求二叉树高度
int height(TreeNode* root) {
if (root == nullptr) return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return max(leftHeight, rightHeight) + 1;
}
// 查找结点的双亲
TreeNode* findParent(TreeNode* root, TreeNode* node) {
if (root == nullptr || root == node) return nullptr;
if (node->val < root->val) {
return findParent(root->left, node);
} else {
return findParent(root->right, node);
}
}
// 统计叶子节点数目
int countLeaves(TreeNode* root) {
if (root == nullptr) return 0;
if (root->left == nullptr && root->right == nullptr) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}
int main() {
// 创建一个简单的二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 测试遍历
cout << "Preorder traversal: ";
preorderTraversal(root);
cout << endl;
cout << "Inorder traversal: ";
inorderTraversal(root);
cout << endl;
cout << "Postorder traversal: ";
postorderTraversal(root);
cout << endl;
// 测试其他操作
cout << "Height of the tree: " << height(root) << endl;
cout << "Parent of node 4 is: ";
if (findParent(root, root->left->left)) cout << findParent(root, root->left->left)->val << endl;
else cout << "None" << endl;
cout << "Number of leaves: " << countLeaves(root) << endl;
return 0;
}
```
这个例子创建了一个简单的二叉树,并展示了如何使用上述函数进行遍历以及计算其高度、查找双亲和统计叶子节点。在`main()`函数中,我们创建了一个二叉搜索树并执行了各种操作。你可以根据需要修改或扩展这个代码。
阅读全文