二叉树数据结构实现csdn
时间: 2023-10-25 15:18:22 浏览: 54
二叉树是一种常用的数据结构,它由一个根节点和最多两个子树构成,其中左子树和右子树也是二叉树。下面是一个基于C++的二叉树数据结构实现。
```c++
#include <iostream>
using namespace std;
// 二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 二叉树类
class BinaryTree {
private:
TreeNode* root; // 根节点
public:
BinaryTree() : root(nullptr) {} // 构造函数
// 插入节点
void insert(int val) {
if (root == nullptr) { // 如果根节点为空,插入根节点
root = new TreeNode(val);
return;
}
TreeNode* cur = root;
while (true) { // 找到插入位置
if (val < cur->val) { // 如果小于当前节点,往左子树找
if (cur->left == nullptr) { // 如果左子树为空,插入左子树
cur->left = new TreeNode(val);
return;
}
cur = cur->left;
} else { // 如果大于等于当前节点,往右子树找
if (cur->right == nullptr) { // 如果右子树为空,插入右子树
cur->right = new TreeNode(val);
return;
}
cur = cur->right;
}
}
}
// 中序遍历
void inorder(TreeNode* cur) {
if (cur != nullptr) {
inorder(cur->left);
cout << cur->val << " ";
inorder(cur->right);
}
}
void inorderTraversal() {
cout << "中序遍历结果:";
inorder(root);
cout << endl;
}
};
int main() {
BinaryTree bt;
bt.insert(5);
bt.insert(7);
bt.insert(2);
bt.insert(8);
bt.insert(1);
bt.inorderTraversal(); // 中序遍历结果:1 2 5 7 8
return 0;
}
```
在这个实现中,我们定义了一个二叉树节点结构体,其中包括节点的值,左子树指针和右子树指针。我们还定义了一个二叉树类,其中包括根节点指针和插入节点、中序遍历等方法。在插入节点时,我们从根节点开始遍历找到插入位置。在中序遍历时,我们先递归遍历左子树,输出当前节点的值,再递归遍历右子树。