假设以顺序表ST表示一棵完全二叉树,ST.data[ST.last]中存放二叉树中各结点的数据元素。试设计算法由此顺序存储结构建立该二叉树的二叉链表LT。
时间: 2024-05-10 11:14:17 浏览: 147
算法如下:
1. 初始化二叉链表LT和顺序表ST,分别用指针和数组表示。
2. 如果ST为空,则返回空链表。
3. 从ST的第一个元素开始遍历,对于每个元素,先将其存入新建的二叉树结点中。
4. 如果该结点是根节点,则直接将其插入到LT中。
5. 否则,找到该结点的双亲结点p,将该结点作为p的左孩子或右孩子插入到LT中。
6. 重复步骤3-5,直到遍历完ST中所有元素。
7. 返回二叉链表LT。
算法描述中用到了二叉树结点的双亲结点,因此需要先定义一个二叉树结点的数据类型,包含数据元素、左孩子指针、右孩子指针和双亲结点指针。具体实现代码如下:
```
typedef struct BiTNode {
ElemType data; // 数据元素
struct BiTNode *lchild, *rchild, *parent; // 左孩子、右孩子、双亲结点指针
} BiTNode, *BiTree;
// 初始化二叉链表LT和顺序表ST
BiTree LT = NULL;
ElemType ST[MAXSIZE];
// 建立二叉链表LT
void CreateBiTree(BiTree &T, int i) {
if (ST[i] == NULL) {
T = NULL;
} else {
T = (BiTree)malloc(sizeof(BiTNode));
T->data = ST[i];
CreateBiTree(T->lchild, 2 * i); // 左孩子结点在数组中的下标为 2i
CreateBiTree(T->rchild, 2 * i + 1); // 右孩子结点在数组中的下标为 2i+1
if (T->lchild != NULL) {
T->lchild->parent = T; // 左孩子结点的双亲结点为 T
}
if (T->rchild != NULL) {
T->rchild->parent = T; // 右孩子结点的双亲结点为 T
}
}
}
// 主函数
int main() {
// 读入顺序表ST和最后一个元素的下标last
int last;
scanf("%d", &last);
for (int i = 1; i <= last; i++) {
scanf("%d", &ST[i]);
}
// 建立二叉链表LT
CreateBiTree(LT, 1);
// 输出二叉链表LT
printf("二叉链表LT:\n");
PrintBiTree(LT, 0);
return 0;
}
```
其中,CreateBiTree函数用于建立二叉链表LT,PrintBiTree函数用于输出二叉链表LT,具体实现代码见下:
```
// 输出二叉链表LT
void PrintBiTree(BiTree T, int depth) {
if (T == NULL) {
return;
}
// 先输出右子树
PrintBiTree(T->rchild, depth + 1);
// 再输出根节点
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", T->data);
// 最后输出左子树
PrintBiTree(T->lchild, depth + 1);
}
```
这样,就可以通过顺序表ST构建二叉链表LT了。
阅读全文