用顺序存储实现二叉树的遍历与操作
时间: 2023-06-23 19:09:00 浏览: 53
二叉树的顺序存储是指将二叉树中的节点按照从上到下、从左到右的顺序依次存储到一个数组中。对于一个具有 n 个节点的二叉树,其顺序存储形式需要使用一个长度为 n+1 的数组,其中下标为 0 的位置留空,从下标为 1 的位置开始存储二叉树的根节点。
下面以前序遍历为例,介绍如何用顺序存储实现二叉树的遍历与操作。
首先,定义一个长度为 n+1 的数组 `tree` 来存储二叉树。数组的下标从 1 开始,对于节点 i,其左子节点的下标为 2*i,右子节点的下标为 2*i+1,父节点的下标为 i/2。
1. 前序遍历
前序遍历的顺序是先遍历根节点,再遍历左子树,最后遍历右子树。使用递归方式实现前序遍历:
```c++
void preOrder(int i) {
if (i > n) return; // 递归结束条件
cout << tree[i] << " "; // 输出节点
preOrder(i*2); // 遍历左子树
preOrder(i*2+1); // 遍历右子树
}
```
2. 中序遍历
中序遍历的顺序是先遍历左子树,再遍历根节点,最后遍历右子树。使用递归方式实现中序遍历:
```c++
void inOrder(int i) {
if (i > n) return; // 递归结束条件
inOrder(i*2); // 遍历左子树
cout << tree[i] << " "; // 输出节点
inOrder(i*2+1); // 遍历右子树
}
```
3. 后序遍历
后序遍历的顺序是先遍历左子树,再遍历右子树,最后遍历根节点。使用递归方式实现后序遍历:
```c++
void postOrder(int i) {
if (i > n) return; // 递归结束条件
postOrder(i*2); // 遍历左子树
postOrder(i*2+1); // 遍历右子树
cout << tree[i] << " "; // 输出节点
}
```
4. 层序遍历
层序遍历是按照二叉树的层次顺序依次遍历每个节点。使用队列实现层序遍历:
```c++
void levelOrder() {
queue<int> q;
q.push(1); // 将根节点入队
while (!q.empty()) {
int i = q.front();
q.pop();
cout << tree[i] << " "; // 输出节点
if (i*2 <= n) q.push(i*2); // 将左子节点入队
if (i*2+1 <= n) q.push(i*2+1); // 将右子节点入队
}
}
```
5. 插入节点
对于顺序存储的二叉树,插入节点的操作需要先找到一个空的位置,将新节点插入到该位置。如果该节点已经存在,则无法插入。
```c++
bool insert(int x) {
int i = 1;
while (i <= n && tree[i] != 0) {
if (x == tree[i]) return false; // 节点已经存在,插入失败
if (x < tree[i]) i = i*2; // 插入到左子树
else i = i*2+1; // 插入到右子树
}
if (i > n) return false; // 插入失败,二叉树已满
tree[i] = x; // 插入节点
return true;
}
```
6. 删除节点
对于顺序存储的二叉树,删除节点的操作需要将该节点以及其子树全部删除。具体操作为:将该节点的值置为 0,然后递归删除其左子树和右子树。
```c++
bool remove(int x) {
int i = 1;
while (i <= n && tree[i] != x) {
if (x < tree[i]) i = i*2; // 查找左子树
else i = i*2+1; // 查找右子树
}
if (i > n) return false; // 节点不存在,删除失败
tree[i] = 0; // 删除节点
remove(i*2); // 递归删除左子树
remove(i*2+1); // 递归删除右子树
return true;
}
```