144-10 感觉有点难-526互联

二叉树使用二叉链表存储，求先序序列中第k个结点的值

首先明确先序遍历是根-左-右，使用递归算法，先左子树，后右子树。

为了防止在找到第k个结点之前就进入右子树的遍历，可以在递归调用时，将左子树的返回值存储在一个变量中，并进行判断。

如果左子树的返回值不等于特定的值（例如-1），则表示已经找到第k个结点，可以直接返回该值，不再进入右子树的遍历。

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

typedef struct node{
    int data;
    struct node *lchild,*rchild;
}TreeNode,*Tree;

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;    
    }
    else
    {
        T=(TreeNode*)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild);
    }
}

int count=0;
int Kdata(Tree T,int k)
{
    if(T==NULL)
        return -1;
    count++;
    if(count==k)
        return T->data;
    int data=Kdata(T->lchild,k);
    if(data!=-1)
        return data;
    return Kdata(T->rchild,k);
}

int main()
{
    Tree T;
    CreateTree(T);
    printf("先序序列中第K个结点值为:%d",Kdata(T,5));
    return 0;
}