假设以顺序表ST表示一棵完全二叉树,ST.data[ST.last]中存放二叉树中各结点的数据元素。试设计算法由此顺序存储结构建立该二叉树的二叉链表LT。
时间: 2024-05-14 10:17:09 浏览: 26
算法如下:
1. 初始化二叉链表LT为空。
2. 从根节点开始,依次遍历顺序表ST中的每一个元素,并将其插入到LT中。
3. 对于每一个非叶子节点,其左孩子节点在ST中的位置为2i,右孩子节点在ST中的位置为2i+1(i为该节点在ST中的位置除以2向下取整)。
4. 对于每一个叶子节点,其没有左右孩子节点。
5. 遍历完所有元素后,二叉链表LT即为所求。
具体实现如下(假设ST和LT已经定义好):
```
void createBinaryTree(SeqList ST, BinTree <) {
int i, n = ST.last;
LT = NULL;
for (i = 1; i <= n; i++) {
BinTree p = (BinTree)malloc(sizeof(BinNode));
p->data = ST.data[i];
p->lchild = p->rchild = NULL;
if (i == 1) {
LT = p;
} else {
int parent = i / 2;
if (i % 2 == 0) {
LT[parent]->lchild = p;
} else {
LT[parent]->rchild = p;
}
}
LT[i] = p;
}
}
```
其中,LT[i]表示ST中第i个节点对应的二叉链表LT中的位置。这里采用数组来保存LT,可以方便地根据ST中的位置找到对应的节点在LT中的位置。
阅读全文
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![text/x-c](https://img-home.csdnimg.cn/images/20250102104920.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20241231044901.png)
![docx](https://img-home.csdnimg.cn/images/20241231044901.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)