写代码:定义顺序存储的二叉树(数组实现,树的结点从数组下标1开始存储)
时间: 2023-06-01 11:02:20 浏览: 262
二叉树-使用数组方式存储
### 回答1:
这道题目要求我们用数组实现一个二叉树,并按照定义顺序存储。具体实现可以参考树的定义,将树的结点从数组下标1开始存储,然后按照父节点、左子树、右子树的顺序存储。这样可以保证能够快速访问到任意一个结点的信息。
### 回答2:
顺序存储的二叉树也叫做完全二叉树,又叫满二叉树,因为在一颗完全二叉树中,除了底层节点可能有一些空缺外,其他每一层的节点都是满的。下面是一种基于数组的完全二叉树的定义方式,每个结点都包含一个值和两个子节点。
```c++
#include<iostream>
#include<cstring>
using namespace std;
const int MAXSIZE = 100; // 数组的最大长度
class ArrayBinaryTree{
private:
int* _array; // 动态分配内存的数组
int _capacity; // 数组的最大容量
public:
ArrayBinaryTree(int capacity = MAXSIZE){ // 构造函数
_array = new int[capacity+1]; // 动态分配内存
memset(_array, 0, sizeof(int)*(capacity+1)); // 初始化数组为0
_capacity = capacity; // 记录数组的最大容量
}
~ArrayBinaryTree(){ // 析构函数
delete[] _array;
}
void setValue(int i, int value){ // 设置某个结点的值
if(i<1 || i>=MAXSIZE) // 校验数组下标的合法性
return;
_array[i] = value;
}
int getValue(int i){ // 获取某个结点的值
if(i<1 || i>=MAXSIZE) // 校验数组下标的合法性
return -1;
return _array[i];
}
int leftChild(int i){ // 获取某个结点的左子节点下标
if(i<1 || i>=MAXSIZE) // 校验数组下标的合法性
return -1;
int left = i*2;
if(left>_capacity) // 左子节点位置超出数组范围,表示该结点没有左子节点
return -1;
return left;
}
int rightChild(int i){ // 获取某个结点的右子节点下标
if(i<1 || i>=MAXSIZE) // 校验数组下标的合法性
return -1;
int right = i*2+1;
if(right>_capacity) // 右子节点位置超出数组范围,表示该结点没有右子节点
return -1;
return right;
}
};
// 测试代码
int main(){
ArrayBinaryTree tree(10);
tree.setValue(1, 10);
tree.setValue(2, 20);
tree.setValue(3, 30);
tree.setValue(4, 40);
tree.setValue(5, 50);
cout<<tree.getValue(1)<<" "<<tree.getValue(2)<<" "<<tree.getValue(3)<<" "<<tree.getValue(4)<<" "<<tree.getValue(5)<<endl;
cout<<tree.leftChild(1)<<" "<<tree.rightChild(1)<<endl; // 2 3
cout<<tree.leftChild(2)<<" "<<tree.rightChild(2)<<endl; // 4 5
return 0;
}
```
在上面的代码中,树的结点从数组下标1开始存储,因此我们需要处理一些下标的边界情况,例如,获取某个结点的左子节点下标时,如果该结点的下标为i,那么它的左子节点下标应该是2*i,但是如果2*i超出了数组的范围,就表示该结点没有左子节点,因此需要返回-1。类似的,获取右子节点下标时,应该返回2*i+1。这种方式实现的完全二叉树,可以很方便地进行遍历、查找、插入和删除等操作,但是需要注意数组的大小限制,如果需要存储太多的结点,就需要使用其他的数据结构,例如链式存储的二叉树。
### 回答3:
顺序存储的二叉树是一种利用数组实现树形结构的方法,每个节点的位置与数组下标一一对应,且根节点存储在数组下标1的位置上。它的一些基本特点包括:
1. 在顺序存储的二叉树中,每个节点都必须按照某种顺序存储,否则节点之间的关系将无法正确建立。
2. 顺序存储的二叉树在自身结构上没有链式存储的灵活,但由于沿用了数组的部分特性,对于访问整个树而言,要比链式存储的树更方便。
下面我们可以定义一个简单的顺序存储二叉树的数据结构:
```
#define MAXSIZE 100 //定义二叉树节点最多个数
typedef int ElementType; //定义元素类型
typedef struct TreeNode *BinTree; //定义指向二叉树节点的指针
struct TreeNode{
ElementType Data;
int Left;
int Right;
}T1[MAXSIZE]; //定义数组存储二叉树,T1[0]表示空节点
BinTree CreateBinTree(){
BinTree T;
T = (BinTree)malloc(sizeof(struct TreeNode));
return T;
}
```
在这里,我们首先定义了一个二叉树节点的结构体,其中包含了节点中存储的元素类型、左右节点的数组下标信息。接着,结合宏定义的最大节点数和二叉树节点指针的定义,我们将其一并存储在了数组中,这样就完成了顺序存储的二叉树的初始化。
为了方便使用,我们还可以定义节点插入的操作:
```
BinTree Insert(ElementType X){
int i;
for(i = 1;i<MAXSIZE;i++){
if(T1[i].Data == NULL){
T1[i].Data = X;
T1[i].Left = 0;
T1[i].Right = 0;
return &T1[i];
}
}
printf("\nerror: over maxsize\n");
return NULL;
}
```
需要注意的是,这里插入的节点并未指定其父节点等信息,因此对于这一类操作的实现,需要通过数组下标定位父节点所在的位置。此外,在每个节点的数组位置上我们可以存储更多的节点信息,如节点度数、高度、颜色、等等。这样,在实际应用中,可能会根据具体问题进行修改和扩充。
总之,顺序存储的二叉树是一种巧妙的数据结构实现,相比链式存储的树具有更为便捷的查询等优点,在某些场合下能够发挥其应用价值。
阅读全文