建立C++代码二叉树,并实现二叉树的遍历,先序遍历采用递归算法实现,层次遍历用非递归算法来实现,可以自己输入字母来构成二叉树
时间: 2024-04-26 13:21:15 浏览: 96
好的,我来帮您解答这个问题。
首先,我们需要定义二叉树的节点结构体,包括节点值、左右子节点指针:
```c++
struct Node {
char value; // 节点值
Node* left; // 左子节点指针
Node* right; // 右子节点指针
};
```
然后,我们可以定义一个二叉树类,包括插入节点、先序遍历、层次遍历等方法:
```c++
class BinaryTree {
public:
BinaryTree(); // 构造函数
~BinaryTree(); // 析构函数
void insert(char value); // 插入节点
void preorderTraversal(); // 先序遍历
void levelTraversal(); // 层次遍历
private:
Node* root; // 根节点指针
void preorderTraversalHelper(Node* node); // 先序遍历辅助函数
};
```
下面是具体实现:
```c++
#include <iostream>
#include <queue>
using namespace std;
struct Node {
char value; // 节点值
Node* left; // 左子节点指针
Node* right; // 右子节点指针
};
class BinaryTree {
public:
BinaryTree() {
root = nullptr;
}
~BinaryTree() {
// TODO: 析构函数
}
void insert(char value) {
if (root == nullptr) {
root = new Node{value, nullptr, nullptr};
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
if (node->left == nullptr) {
node->left = new Node{value, nullptr, nullptr};
return;
} else {
q.push(node->left);
}
if (node->right == nullptr) {
node->right = new Node{value, nullptr, nullptr};
return;
} else {
q.push(node->right);
}
}
}
void preorderTraversal() {
preorderTraversalHelper(root);
cout << endl;
}
void levelTraversal() {
if (root == nullptr) {
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
cout << node->value << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
cout << endl;
}
private:
Node* root;
void preorderTraversalHelper(Node* node) {
if (node == nullptr) {
return;
}
cout << node->value << " ";
preorderTraversalHelper(node->left);
preorderTraversalHelper(node->right);
}
};
int main() {
BinaryTree tree;
// 构建二叉树
tree.insert('A');
tree.insert('B');
tree.insert('C');
tree.insert('D');
tree.insert('E');
tree.insert('F');
tree.insert('G');
tree.insert('H');
tree.insert('I');
// 先序遍历
tree.preorderTraversal();
// 层次遍历
tree.levelTraversal();
return 0;
}
```
输入字母来构成二叉树,可以将 `insert` 方法改为从标准输入读入节点值,具体实现略。
阅读全文