(1)设计一个类(或者结构)表示结点; (2)设计一个类(或者结构)表示二叉树; (3)定义并实现二叉树的创建,先序、中序和后序遍历的操作; (4)在main函数中按用户输入的数据创建二叉树,接着遍历这棵树。
时间: 2024-12-14 21:23:16 浏览: 7
(1)首先,我们可以设计一个简单的`Node`类来表示二叉树的节点:
```cpp
class Node {
public:
int data; // 节点存储的数据
Node* left; // 左子节点指针
Node* right; // 右子节点指针
Node(int value) : data(value), left(nullptr), right(nullptr) {} // 构造函数,初始化数据
};
```
(2)接着,我们设计一个`BinaryTree`类来表示整个二叉树:
```cpp
class BinaryTree {
private:
Node* root; // 树的根节点
public:
BinaryTree() : root(nullptr) {}
// 插入节点、删除节点等操作...
void insertNode(Node* &root, int value);
// 遍历函数模板
template <typename Func>
void traverse(Func visit) const;
// 先序遍历
void preOrderTraversal() const;
// 中序遍历
void inOrderTraversal() const;
// 后序遍历
void postOrderTraversal() const;
};
```
(3)接下来,我们需要实现插入节点和遍历操作:
```cpp
// 定义插入节点函数
void BinaryTree::insertNode(Node*& root, int value) {
if (!root) {
root = new Node(value);
} else {
insertNode(root->left, value); // 如果值小于当前节点,递归左子树
if (value == root->data) return; // 防止重复插入
insertNode(root->right, value); // 否则递归右子树
}
}
template<typename Func>
void BinaryTree::traverse(Func visit) const {
if (root) {
visit(root);
traverse(root->left, visit);
traverse(root->right, visit);
}
}
// 实现三种遍历方式
void BinaryTree::preOrderTraversal() const { traverse([](const Node* node) { cout << node->data << " "; }, this->root); }
void BinaryTree::inOrderTraversal() const { traverse([](const Node* node) { if (node) cout << node->data << " "; }, this->root); }
void BinaryTree::postOrderTraversal() const { traverse([](const Node* node) { if (node) { cout << node->data << " "; traverse(node); } }, this->root); }
```
(4)在`main`函数中,根据用户输入构建二叉树并遍历:
```cpp
int main() {
BinaryTree tree;
// 获取用户输入,例如
int input;
while (cin >> input) {
tree.insertNode(tree.root, input);
}
cout << "Preorder traversal: ";
tree.preOrderTraversal();
cout << endl;
cout << "Inorder traversal: ";
tree.inOrderTraversal();
cout << endl;
cout << "Postorder traversal: ";
tree.postOrderTraversal();
cout << endl;
return 0;
}
```
阅读全文