假设以顺序表ST表示一棵完全二叉树,ST.data[ST.last]中存放二叉树中各结点的数据元素。试设计算法由此顺序存储结构建立该二叉树的二叉链表LT。
时间: 2024-05-03 13:16:39 浏览: 74
可以按照以下步骤来实现该算法:
1. 定义二叉树结点类型
```
typedef struct BiTNode {
ElemType data; // 数据元素
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
```
2. 初始化一个空的二叉树链表LT
```
void InitBiTree(BiTree *LT) {
*LT = NULL;
}
```
3. 逐个将顺序表中的元素插入到二叉链表中
```
void CreateBiTree(BiTree *LT, ElemType *data, int i, int n) {
if (i <= n) {
*LT = (BiTree)malloc(sizeof(BiTNode)); // 分配结点空间
(*LT)->data = data[i]; // 存储数据元素
CreateBiTree(&((*LT)->lchild), data, 2*i, n); // 递归构建左子树
CreateBiTree(&((*LT)->rchild), data, 2*i+1, n); // 递归构建右子树
} else {
*LT = NULL;
}
}
```
4. 调用函数建立二叉链表
```
BiTree LT;
InitBiTree(<); // 初始化空链表
CreateBiTree(<, ST.data, 1, ST.last); // 从第一个元素开始构建二叉树
```
这样就可以将顺序表ST表示的完全二叉树转换为二叉链表LT表示的二叉树了。
阅读全文