C语言实现）设计一个算法将二叉树的顺序存储结构转换成二叉链存储结构。

以下是C语言实现将二叉树的顺序存储结构转换成二叉链存储结构的算法：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

typedef struct {
    BiTree data[MAXSIZE];
    int front, rear;
} SqQueue;

void InitQueue(SqQueue *Q) {
    Q->front = Q->rear = 0;
}

int QueueEmpty(SqQueue Q) {
    if (Q.front == Q.rear) {
        return 1;
    } else {
        return 0;
    }
}

int EnQueue(SqQueue *Q, BiTree e) {
    if ((Q->rear + 1) % MAXSIZE == Q->front) {
        return 0;
    }
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return 1;
}

int DeQueue(SqQueue *Q, BiTree *e) {
    if (Q->front == Q->rear) {
        return 0;
    }
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return 1;
}

void CreateBiTree(BiTree *T) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

void PreOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    printf("%c ", T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

void InOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    InOrderTraverse(T->lchild);
    printf("%c ", T->data);
    InOrderTraverse(T->rchild);
}

void PostOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ", T->data);
}

void LevelOrderTraverse(BiTree T) {
    SqQueue Q;
    BiTree p;
    InitQueue(&Q);
    if (T != NULL) {
        EnQueue(&Q, T);
    }
    while (!QueueEmpty(Q)) {
        DeQueue(&Q, &p);
        printf("%c ", p->data);
        if (p->lchild != NULL) {
            EnQueue(&Q, p->lchild);
        }
        if (p->rchild != NULL) {
            EnQueue(&Q, p->rchild);
        }
    }
}

void PreInCreateBiTree(BiTree *T, char *pre, char *in, int len) {
    int i, j;
    char *p;
    if (len <= 0) {
        *T = NULL;
        return;
    }
    *T = (BiTree)malloc(sizeof(BiTNode));
    (*T)->data = *pre;
    for (i = 0; i < len; i++) {
        if (*(in + i) == *pre) {
            break;
        }
    }
    p = pre + 1;
    j = i;
    while (j--) {
        p++;
    }
    PreInCreateBiTree(&(*T)->lchild, pre + 1, in, i);
    PreInCreateBiTree(&(*T)->rchild, p, in + i + 1, len - i - 1);
}

void PreInOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    printf("%c ", T->data);
    PreInOrderTraverse(T->lchild);
    PreInOrderTraverse(T->rchild);
}

void InPostCreateBiTree(BiTree *T, char *in, char *post, int len) {
    int i, j;
    char *p;
    if (len <= 0) {
        *T = NULL;
        return;
    }
    *T = (BiTree)malloc(sizeof(BiTNode));
    (*T)->data = *(post + len - 1);
    for (i = 0; i < len; i++) {
        if (*(in + i) == *(post + len - 1)) {
            break;
        }
    }
    p = post;
    j = i;
    while (j--) {
        p++;
    }
    InPostCreateBiTree(&(*T)->lchild, in, p - i, i);
    InPostCreateBiTree(&(*T)->rchild, in + i + 1, post + i, len - i - 1);
}

void InPostOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    InPostOrderTraverse(T->lchild);
    InPostOrderTraverse(T->rchild);
    printf("%c ", T->data);
}

void PreInPostCreateBiTree(BiTree *T, char *pre, char *in, char *post, int len) {
    int i, j;
    char *p;
    if (len <= 0) {
        *T = NULL;
        return;
    }
    *T = (BiTree)malloc(sizeof(BiTNode));
    (*T)->data = *pre;
    for (i = 0; i < len; i++) {
        if (*(in + i) == *pre) {
            break;
        }
    }
    p = post;
    j = i;
    while (j--) {
        p++;
    }
    PreInPostCreateBiTree(&(*T)->lchild, pre + 1, in, post, i);
    PreInPostCreateBiTree(&(*T)->rchild, p - len + i, in + i + 1, p - 1, len - i - 1);
}

void PreInPostOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    PreInPostOrderTraverse(T->lchild);
    printf("%c ", T->data);
    PreInPostOrderTraverse(T->rchild);
}

void PreOrderTraverse2(BiTree T) {
    SqQueue Q;
    BiTree p;
    InitQueue(&Q);
    if (T != NULL) {
        EnQueue(&Q, T);
    }
    while (!QueueEmpty(Q)) {
        DeQueue(&Q, &p);
        printf("%c ", p->data);
        if (p->lchild != NULL) {
            EnQueue(&Q, p->lchild);
        }
        if (p->rchild != NULL) {
            EnQueue(&Q, p->rchild);
        }
    }
}

void InOrderTraverse2(BiTree T) {
    SqQueue Q;
    BiTree p;
    InitQueue(&Q);
    p = T;
    while (p != NULL || !QueueEmpty(Q)) {
        if (p != NULL) {
            EnQueue(&Q, p);
            p = p->lchild;
        } else {
            DeQueue(&Q, &p);
            printf("%c ", p->data);
            p = p->rchild;
        }
    }
}

void PostOrderTraverse2(BiTree T) {
    SqQueue Q;
    BiTree p, r;
    InitQueue(&Q);
    p = T;
    do {
        while (p != NULL) {
            EnQueue(&Q, p);
            p = p->lchild;
        }
        r = NULL;
        while (!QueueEmpty(Q)) {
            DeQueue(&Q, &p);
            if (p->rchild == r) {
                printf("%c ", p->data);
                r = p;
            } else {
                EnQueue(&Q, p);
                p = p->rchild;
                break;
            }
        }
    } while (!QueueEmpty(Q));
}

void Convert(BiTree T, BiTree *pre) {
    if (T == NULL) {
        return;
    }
    Convert(T->lchild, pre);
    T->lchild = *pre;
    if (*pre != NULL) {
        (*pre)->rchild = T;
    }
    *pre = T;
    Convert(T->rchild, pre);
}

BiTree ConvertBiTree(BiTree T) {
    BiTree pre = NULL;
    Convert(T, &pre);
    while (T != NULL && T->lchild != NULL) {
        T = T->lchild;
    }
    return T;
}

int main() {
    BiTree T, p;
    printf("请按先序输入二叉树(如:'ABD##E##CF##G##')\n");
    CreateBiTree(&T);
    printf("先序遍历：");
    PreOrderTraverse(T);
    printf("\n中序遍历：");
    InOrderTraverse(T);
    printf("\n后序遍历：");
    PostOrderTraverse(T);
    printf("\n层序遍历：");
    LevelOrderTraverse(T);
    printf("\n");
    p = ConvertBiTree(T);
    printf("双向链表：");
    while (p != NULL) {
        printf("%c ", p->data);
        p = p->rchild;
    }
    printf("\n");
    return 0;
}