将顺序存储二叉树，转换成二叉链表


/*5.18设计算法将一棵以顺序存储方式存储在数组A[]中的二叉树
（已转换为完全二叉树，补充的虚拟结点为值为’#’）转换为二叉链表存储形式。
*/
#include 
using namespace std;
#define max 100
typedef char element;
typedef struct lBNode {
    element data;
    struct lBNode* lChild, * rChild;
}BiNode, * BiTree;
typedef struct sList {
    element  data[100];
    int listLen;//定义表长度分量
}seqList;
void initiList(seqList* L) {
    L->listLen = 0;
}
int listLenth(seqList*& T) {
    return T->listLen;
}
//交互输入创建顺序存储二叉树
void createBTNode(seqList*& T) {
    int i = 1;
    element  x;
    cout << "请从根结点开始按完全二叉树层次输入结点，缺少结点输入'#'，输入'!'结束。" << endl;
    cin >> x;
    while (x != '!')
    {
        T->data[i] = x;
        T->listLen++;
        i++;
        cin >> x;
    }
}
//转换函数
void  trans(BiNode* T,seqList* a, int i) {
    if (a->data[i] != '#') {
        BiNode* b = new BiNode;
        b->data = a->data[i];
        b->lChild = NULL;
        b->rChild = NULL;
        T = b;
          trans( T->lChild, a, 2 * i);
          trans(T->rChild, a, 2 * i + 1);
    }
    else {
        T = NULL;
    }
}
//先序遍历二叉链表
void preTraverse(BiNode* T)
{
    if (T)
    {
        cout << T->data << " ";         //访问根结点。打印当前结点元素值，替代visit(T)函数
        preTraverse(T->lChild);     //先序遍历左子树
        preTraverse(T->rChild);     //先序遍历右子树
    }
}
int main() {
    seqList *L=new seqList;
    initiList(L);
    BiNode* T=NULL;
    createBTNode(L);
    trans(T,L, 1);
    preTraverse(T);
    return 0;
 }

为什么输完顺序表里的数程序九崩了，编译是没有问题的

img

在程序中出现了指针传参的问题，即在转换函数 trans() 中，应该传入指向指针的指针，以便在函数内部改变指针的指向。同时，在调用 trans() 函数时，应该传入指向指针的指针，而不是指向指针的普通指针。
具体地，修改 trans() 函数定义如下：
c++

void trans(BiNode*& T, seqList* a, int i)
修改 main() 函数调用 trans() 函数的语句如下：
c++

trans(T, L, 1);
这样修改之后，程序应该就能正确运行了。

代码中创建了一个指向 NULL 的指针 BiNode* T，但是在 trans 函数中，将参数 T 当作递归函数的参数传递，这样并不会改变 T 的值，也就是说，无法将递归函数中创建的结点赋值给 T，最终返回的仍然是一个指向 NULL 的指针。

为了解决这个问题，可以将 trans 函数的参数改为指向指针的指针（即 BiNode** T），这样就能够将新建的结点的地址赋值给 T，最终返回的就是一个指向二叉链表根结点的指针。

另外，需要注意的是，在 trans 函数中，应该先创建结点，再将结点的地址赋值给 T，否则 T 的值将始终为 NULL。

修改后的完整函数代码如下：

#include <iostream>
using namespace std;
#define max 100
typedef char element;
typedef struct lBNode {
    element data;
    struct lBNode* lChild, * rChild;
}BiNode, * BiTree;
typedef struct sList {
    element  data[100];
    int listLen;//定义表长度分量
}seqList;
void initiList(seqList* L) {
    L->listLen = 0;
}
int listLenth(seqList*& T) {
    return T->listLen;
}
//交互输入创建顺序存储二叉树
void createBTNode(seqList*& T) {
    int i = 1;
    element  x;
    cout << "请从根结点开始按完全二叉树层次输入结点，缺少结点输入'#'，输入'!'结束。" << endl;
    cin >> x;
    while (x != '!')
    {
        T->data[i] = x;
        T->listLen++;
        i++;
        cin >> x;
    }
}
//转换函数
void  trans(BiNode** T, seqList* a, int i) {
    if (a->data[i] != '#') {
        BiNode* b = new BiNode;
        b->data = a->data[i];
        b->lChild = NULL;
        b->rChild = NULL;
        *T = b;
        trans(&((*T)->lChild), a, 2 * i);
        trans(&((*T)->rChild), a, 2 * i + 1);
    }
    else {
        *T = NULL;
    }
}
//先序遍历二叉链表
void preTraverse(BiNode* T)
{
    if (T)
    {
        cout << T->data << " ";         //访问根结点。打印当前结点元素值，替代visit(T)函数
        preTraverse(T->lChild);     //先序遍历左子树
        preTraverse(T->rChild);     //先序遍历右子树
    }
}
int main() {
    seqList *L=new seqList;
    initiList(L);
    BiNode* T=NULL;
    createBTNode(L);
    trans(&T, L, 1);
    preTraverse(T);
    return 0;
 }

以上两个机器人，全部都是刷的GPT，可是也不标，csdn现在不管了么

img