求一个二叉树的M层的第K个节点的值

首先，先看百度笔试的这道原题

2．给定以下二叉树:

struct node_t

{

   node_t *left, *right;

   int value;

};

要求编写函数 node_t* foo(node_t *node, unsigned int m, unsigned int k);

输出以 node 为根的二叉树第 m 层的第 k 个节点值.

(level, k 均从 0 开始计数)

注意：

1）  此树不是完全二叉树；

2）  所谓的第K个节点，是本层中从左到右的第K个节点

我写过这样的程序，比较符合这个题目的意思。不过我的那个结构体是对题目中给定的结构体的一个封装，

先看我的程序：

/*
 * Copyright (c) 2010-~ zhouyongfei
 *
 * The source code is released for free distribution under the terms of the GNU General Public License
 *
 *
 * Author: alen Chou
 * Created Time: 2010年05月31日 星期一 18时37分59秒
 * File Name: test.c
 * Description: 这个程序用于遍历二叉树M层第K个元素的值

 × 示例：输入124..56..7..3..

 × 输出：result is 7
 *
 */

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


typedef struct Node{
    char data;
    struct Node * Lchild;
    struct Node * Rchild;
    int level;
}BiTNode,*BiTree;//二叉树节点，二叉链表


typedef struct QueueNode{
    BiTree data;
    struct QueueNode *next;
}LinkQueueNode;//队列中的每个节点


typedef struct
{
    LinkQueueNode *front;
    LinkQueueNode *rear;
}LinkQueue;//队列


/*
 * 队列的初始化
 *
 * */
void InitQueue(LinkQueue *Q)
{
    Q->front = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    if(Q->front != NULL){
        Q->rear = Q->front;
        Q->front->next = NULL;
    }else printf("分配空间失败!\n");
}
/*
 * 入队
 *
 * */
void EnterQueue(LinkQueue *Q,BiTree x)
{
    LinkQueueNode *NewNode;
    NewNode = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    if(NewNode != NULL){
        NewNode->data = x;
        NewNode->next = NULL;
        Q->rear->next = NewNode;
        Q->rear = NewNode;
    }
}

/*
 *    队列判空
 *
 * */
int QueueIsEmpty(LinkQueue *Q)
{
    if(Q->front == Q->rear)
        return 1;
    else return 0;
}

/*
 * 出队
 *
 * */
void DeleteQueue(LinkQueue *Q,BiTree *x)
{
    LinkQueueNode *p;
    if(Q->front == Q->rear)
        return ;
    p = Q->front->next;
    Q->front->next = p->next;
    if(Q->rear == p)
        Q->rear = Q->front;
    *x = p->data;
    free(p);
}


/*
 * 利用扩展先序遍历序列
 * 创建二叉链表
 */
void CreateBiTree(BiTree *bt)
{
    char ch;
    ch = getchar();
    if(ch == '.') *bt = NULL;
    else
    {
        *bt = (BiTree)malloc (sizeof(BiTNode));
        (*bt)->data = ch;
        (*bt)->level = 0;
        CreateBiTree(&((*bt)->Lchild));
        CreateBiTree(&((*bt)->Rchild));
    }
}

/*
 *    层序遍历
 *     对给定的二叉树进行层序遍历
 *
 * */
char LayerOrder(BiTree root,int m,int k)
{    
    char result[20];
    int i = 0;
    BiTree *x;
    //这里要记得申请空间

    x = (BiTree *)malloc(sizeof(BiTree));
    if(x == NULL){
        printf("内存分配失败!\n");
    }
    LinkQueue *Q;
    Q = (LinkQueue *)malloc(sizeof(LinkQueue));
    InitQueue(Q);
    EnterQueue(Q,root);
    while(!QueueIsEmpty(Q)){
        DeleteQueue(Q,x);
        if((*x)->Lchild) (*x)->Lchild->level = (*x)->level + 1;
        if((*x)->Rchild) (*x)->Rchild->level = (*x)->level + 1;
        if((*x)->level == m){
            result[i] = (*x)->data;
            i++;
        }
        if((*x)->Lchild)EnterQueue(Q,(*x)->Lchild);
        if((*x)->Rchild)EnterQueue(Q,(*x)->Rchild);
    }
    return result[k];
}

int main(int argc , char **argv)
{
    BiTree root;
    CreateBiTree(&root);
    printf("层序遍历:\n");
    char result=LayerOrder(root,3,1);
    printf("result is %c",result);
    printf("\n");
}

编译运行过程如下

zhou@zhou:~/DateStructure/bitree2$ gcc -g bitree.c -o main

zhou@zhou:~/DateStructure/bitree2$ ./main 

124..56..7..3..

层序遍历:

result is 7

zhou@zhou:~/DateStructure/bitree2$ 

其实大家都知道，对二叉树的层序遍历或者图的广度优先遍历，都应当采用队列这个数据结构能方便

一些，对于这道题，主要是由于二叉树不一定是一个完全二叉树，所以我加了一个层的标志位，用于

方便解题。其他的问题可以留言讨论，谢谢