c++类模板二叉树顺序存储
时间: 2023-10-21 16:05:44 浏览: 36
二叉树的顺序存储是将二叉树按照层次遍历的顺序存储在一个一维数组中,其中根节点存储在数组下标为1的位置,左子节点存储在2i的位置,右子节点存储在2i+1的位置(i为节点在数组中的下标)。
下面是一个使用类模板实现的二叉树顺序存储的示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
template <typename T>
class SeqBinaryTree {
public:
SeqBinaryTree() {}
SeqBinaryTree(const vector<T>& v);
~SeqBinaryTree() {}
bool empty() const { return data_.empty(); }
int size() const { return data_.size() - 1; }
T root() const { return data_.at(1); }
T parent(int i) const { return data_.at(i / 2); }
T left(int i) const { return data_.at(2 * i); }
T right(int i) const { return data_.at(2 * i + 1); }
void insert(const T& value);
void remove(int i);
void print() const;
private:
vector<T> data_;
};
template <typename T>
SeqBinaryTree<T>::SeqBinaryTree(const vector<T>& v) {
data_.resize(v.size() + 1);
for (int i = 0; i < v.size(); ++i) {
data_[i + 1] = v[i];
}
}
template <typename T>
void SeqBinaryTree<T>::insert(const T& value) {
data_.push_back(value);
}
template <typename T>
void SeqBinaryTree<T>::remove(int i) {
if (i < 1 || i > size()) {
return;
}
data_.erase(data_.begin() + i);
}
template <typename T>
void SeqBinaryTree<T>::print() const {
for (int i = 1; i <= size(); ++i) {
cout << data_[i] << " ";
}
cout << endl;
}
int main() {
vector<int> v = { 1, 2, 3, 4, 5, 6, 7 };
SeqBinaryTree<int> tree(v);
tree.insert(8);
tree.print(); // 1 2 3 4 5 6 7 8
tree.remove(2);
tree.print(); // 1 3 4 5 6 7 8
return 0;
}
```
在上面的代码中,SeqBinaryTree类模板包含了二叉树的一些基本操作,包括构造函数、判断是否为空、获取节点数目、获取根节点、获取父节点、获取左子节点、获取右子节点、插入节点、删除节点和打印二叉树。其中构造函数使用vector初始化二叉树,插入节点和删除节点都是在vector中进行操作,打印二叉树则是按照顺序输出vector中的元素。