touge 二叉树的顺序存储及基本操作
时间: 2023-09-13 11:08:27 浏览: 47
二叉树的顺序存储也叫做顺序表存储,指的是将二叉树的结点按照某种顺序存储在一维数组中,然后通过数组下标来访问结点。假设二叉树的深度为d,那么顺序存储需要的数组大小为$2^d-1$,其中,下标为i的结点的左孩子结点下标为$2i+1$,右孩子结点下标为$2i+2$,父结点下标为$(i-1)/2$。
下面是二叉树的顺序存储实现及基本操作的代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 二叉树结点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 二叉树的顺序存储
class SeqBinaryTree {
public:
SeqBinaryTree(vector<int>& nums) {
int n = nums.size();
if (n == 0) return;
data_ = vector<TreeNode*>(n, NULL);
for (int i = 0; i < n; i++) {
if (nums[i] != -1) {
data_[i] = new TreeNode(nums[i]);
}
}
for (int i = 0; i < n; i++) {
if (data_[i] != NULL) {
int left = i * 2 + 1, right = i * 2 + 2;
if (left < n) data_[i]->left = data_[left];
if (right < n) data_[i]->right = data_[right];
}
}
}
// 获取根结点
TreeNode* getRoot() {
return data_[0];
}
// 获取结点数
int size() {
return data_.size();
}
private:
vector<TreeNode*> data_;
};
int main() {
vector<int> nums = {1, 2, 3, -1, -1, 4, 5};
SeqBinaryTree tree(nums);
cout << "size: " << tree.size() << endl;
cout << "root: " << tree.getRoot()->val << endl;
return 0;
}
```
上述代码中,我们通过一个vector来存储二叉树的结点,其中,如果某个结点为空,我们用NULL表示。在构造函数中,我们遍历vector,将不为空的结点存储在数组中,并为每个结点的左右孩子指针赋值。在getroot()函数中,我们返回数组的第一个元素,即根结点。在size()函数中,我们返回数组的大小,即为二叉树的结点数。
除了上述基本操作外,我们还可以实现其他操作,比如获取某个结点的左孩子、右孩子、父结点等,这些操作的实现方法与普通二叉树类似。