二叉树，先序遍历序列

Question

假设二叉树中每个节点值为单个字符，采用二叉链存储结构存储。设计一个算法，求二叉树b的先序遍历序列中第k（1<=k<=二叉树中结点个数）个结点的值

#include<stdio.h>
typedef char ElemType;
typedef struct node
{
    ElemType data;
    struct node *lchild;
    struct node *rchild;
}BINode;
int n=1;
ElemType PreNode(BINode *b,int k)   //a指向二叉树的根结点 
{
    if(b==NULL)
        return ' ';
    if(n==k)
        return b->data;
    n++;
    ElemType ch;
    ch=PreNode(b->lchild,k);    //遍历左子树
    if(ch!=NULL)                //如果左子树没有返回空，那么一定是所求的答案 
        return ch;
    ch=PreNode(b->rchild,k);    //如果左子树返回空，则要遍历右子树 
    return ch; 
}

int main()
{
    BINode *node1,*node2,*node3;
    node1->data='a';
    node2->data='b';
    node3->data='c';
    node1->lchild=node2;
    node1->rchild=node3;
    node2->lchild=NULL;
    node2->rchild=NULL;
    node3->lchild=NULL;
    node3->rchild=NULL;
    printf("%c",PreNode(node1,2));
    return 0;
} 

为什么我的输出结果什么都没有啊？

Answer 1

【以下回答由 GPT 生成】

问题的关键在于没有正确初始化二叉树的节点。

在main()函数中，创建了三个BINode类型的指针node1、node2和node3，但是没有为这些指针分配内存空间。因此，在对这些指针进行赋值之前，需要使用malloc()函数分配内存。

此外，在给节点指针赋值后，还需要将节点的左右子节点指针设置为NULL，表示空。

以下是修正后的代码：

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

typedef char ElemType;
typedef struct node
{
    ElemType data;
    struct node *lchild;
    struct node *rchild;
} BINode;

int n = 1;

ElemType PreNode(BINode* b, int k)
{
    if (b == NULL)
        return ' ';
    if (n == k)
        return b->data;
    n++;
    ElemType ch;
    ch = PreNode(b->lchild, k);
    if (ch != NULL)
        return ch;
    ch = PreNode(b->rchild, k);
    return ch;
}

int main()
{
    BINode* node1 = (BINode*)malloc(sizeof(BINode));
    BINode* node2 = (BINode*)malloc(sizeof(BINode));
    BINode* node3 = (BINode*)malloc(sizeof(BINode));

    node1->data = 'a';
    node2->data = 'b';
    node3->data = 'c';

    node1->lchild = node2;
    node1->rchild = node3;
    node2->lchild = NULL;
    node2->rchild = NULL;
    node3->lchild = NULL;
    node3->rchild = NULL;

    printf("%c", PreNode(node1, 2));

    free(node1);
    free(node2);
    free(node3);

    return 0;
}

在修正后的代码中，我们使用malloc()函数为每个节点指针分配了内存空间，并将左右子节点指针设置为NULL，避免了悬空指针的问题。同时，在代码结束前，我们还使用free()函数释放了节点的内存空间。

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7466478
• 你也可以参考下这篇文章：求二叉树先序序列中第k个结点的值

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^