이 진 트 리 의 m 층 K 번 째 노드 인쇄 (재 귀 + 비 재 귀)

앞의 글 에서 '이 진 트 리 가 지정 한 한 층 을 층 차 로 옮 겨 다 니 기' 문 제 를 토론 한 적 이 있 습 니 다. 이 를 바탕 으로 코드 를 조금 만 수정 하면 '이 진 트 리 에서 m 층 의 k 번 째 노드 인쇄' 를 완성 할 수 있 습 니 다. 구체 적 으로 다음 과 같 습 니 다.
설명: 뿌리 노드 는 0 층 에 있 고 각 층 의 첫 번 째 노드 의 아래 표 시 는 0 이다.따라서 이 진 트 리 의 m 층 k 번 째 노드 를 인쇄 하려 면 (들 어 갈 매개 변 수 는 각각: (m - 1) 과 (k - 1) 입 니 다.

#include 
using namespace std;
#include 
#include 


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


//         （   ，               ,  #       ）
BiTree createBiTree()
{
    BiTree T;

    char c;
    scanf("%c", &c);

    if (c == '#')
        T = NULL;
    else
    {
        T = new BiNode;  //   T = (BiTree)malloc(sizeof(BiNode));
        T->data = c;

        T->lchild = createBiTree();
        T->rchild = createBiTree();
    }

    return T;

}


//   ，  level    k   。
//   level    （     ），k                ；（  3 ， 2         (2, 1)）
int k = 1; // k=1      level   2   
int num = 0; //    num，       level  ，num             ， num==k ，       。
void PrintNodeAtLevel(BiTree T , int level)
{
    if(T == NULL || level < 0) return;

    if(level == 0)
    {
        if (num == k)
            printf("%c
", T->data);

        num++;

    }
    PrintNodeAtLevel(T->lchild , level - 1);
    PrintNodeAtLevel(T->rchild , level - 1);
}


//    （ ），    vector   ，  level    k   。
//   level    （     ），k                ；（  3 ， 2         (2, 1)）
void printNodeAtLevel2(BiTree T, int level, int k) //   level    （     ）
{
    if (T == NULL) return;

    vector vec;
    vec.push_back(T);

    int curLevel = 0; //       ；（     ，     ；  ，     0 ，  1 ）

    int cur = 0;
    int last = 1;
    while (cur < vec.size() && curLevel < level)
    {
        last = (int)vec.size();

        while (cur < last)
        {
            if (vec[cur]->lchild)
                vec.push_back(vec[cur]->lchild);

            if (vec[cur]->rchild)
                vec.push_back(vec[cur]->rchild);

            cur++;
        }

        curLevel++; //      1
    }


    //      while   ，curLevel == level；               [cur + k]       。
    printf("%c
", vec[cur + k]->data);

}



//    （ ），    queue   ，  level    k   。
//   level    （     ），k                ；（  3 ， 2         (2, 1)）
void printNodeAtLevel3(BiTree T, int level, int k)
{
    if(T == NULL) return;

    deque q;
    q.push_back(T);

    int curLevelNum; //        

    int curLevel = 0; //       

    while (q.size() && curLevel < level)
    {
        curLevelNum = (int)q.size(); //         ，  size()    size_type  ；

        while(curLevelNum-- > 0) //                
        {
            BiTree tmp = q.front();

            q.pop_front();

            if(tmp->lchild)
                q.push_back(tmp->lchild);
            if(tmp->rchild)
                q.push_back(tmp->rchild);

        }

        curLevel++; //      1
    }


    //      while   ，curLevel == level；              k       。
    printf("%c
", q[k]->data);
}



int main(int argc, const char * argv[]) {

    BiTree T = createBiTree(); //   

    PrintNodeAtLevel(T, 2); //     ( 3  2   )(  ：       ，    int k = 1    )

//    printNodeAtLevel2(T, 2, 1); //    
//
//    printNodeAtLevel3(T, 2, 1); //    


    return 0;
}