按层次初始化/遍历二叉树

按层次遍历二叉树的程序网上一大把,但是自己就没真的自己亲手去实现过.导致当出现新的需求时,没法立刻写出代码来.
需求:按层次遍历二叉树,根节点为0层.偶数层从左到右输出,奇数层从右到左输出.每输出一层,就输出一个换行.

Kiss

开始拿到需求的时候,第一想法是用以前了解的方法,将节点压进队列,从队列头每弹出一个节点,就将该节点的儿子们压进队列结尾.
这里与单纯的按层次遍历的不同之处在于:

  • 每层换行
  • 奇偶层不同的打印顺序

当时是想通过循环解决这两个不同,每层节点数是2^i.输出这么多节点后就换行,同时依据i的奇偶性决定打印顺序.
按道理来说应该也可以实现,只是需要小心翼翼地处理各种细节和边界,那时我被困扰了,没有写出来.
更优雅一些,其实可以添加标志位,碰到换行标志位就换行,碰到奇偶标志位就做相应的输出处理.
具体来说:

  • 将’+’’-‘做奇偶标志,用’$’做换行标志.
  • 首先将奇偶标志压进队列,然后将root压进队列,最后是换行标志.
  • 做以下循环直到队列为空:

    • 若队头为’-‘,且队列中还有树的节点,则将’-‘变为’+’压入队列结尾.然后将队列头依次压入辅助栈中(直到队列头是’$’为止).依次打印辅助栈的元素,就完成了从左到右的打印顺序.此时队头元素是$,打印一个换行.如果队列中还有节点元素,将$压入队列末尾.继续下一次循环.
    • 若队头为’+’,出栈,将其变成’-‘,视情况将其压入队尾.
    • 若对头为’$’,出栈,打印换行符.视情况将其压入队尾.
    • 若是树的节点,则打印.
    • 若当前节点有非空的儿子节点,将儿子按从左到右的顺序压进队列.

以上的流程之所以能够实现功能,是因为交替变换奇偶标志,并利用辅助栈进行倒序输出.
而换行标志每次都恰好放置在该层最后一个节点的末尾,因此能正确换行.

实现

  • 换行打印

    void Tree::PrintByLevel()
    {
    list<Node*> nodesList;
    Node* endOfLine=new Node('$');
    nodesList.push_back(root);
    nodesList.push_back(endOfLine);
    while(!nodesList.empty())
    {
    Node* front=nodesList.front();
    if(front->data=='$')
    {
    printf(";\n");
    nodesList.pop_front();
    if(nodesList.size()>1)
    nodesList.push_back(endOfLine);
    }
    else
    {
    printf("%c", front->data);
    nodesList.pop_front();
    }
    if(front->left!=NULL)
    nodesList.push_back(front->left);
    if(front->right!=NULL)
    nodesList.push_back(front->right);
    }
    delete endOfLine;
    }
  • 按奇偶层次,不同顺序打印

    void Tree::PrintByLevelRev()
    {
    list<Node*> nodesList;
    Node* endOfLine=new Node('$');
    Node* flag=new Node('+');
    nodesList.push_back(flag);
    nodesList.push_back(root);
    nodesList.push_back(endOfLine);
    while(!nodesList.empty())
    {
    Node* front=nodesList.front();
    if(front->data=='-')
    {
    nodesList.pop_front();
    flag->data='+';
    if(nodesList.size()>2)
    nodesList.push_back(flag);
    stack<Node*> tempStack;
    while(nodesList.front()->data!='$')
    {
    Node* tempFront=nodesList.front();
    tempStack.push(tempFront);
    nodesList.pop_front();
    if(tempFront->left!=NULL)
    nodesList.push_back(tempFront->left);
    if(tempFront->right!=NULL)
    nodesList.push_back(tempFront->right);
    }
    while(!tempStack.empty())
    {
    printf("%c",tempStack.top()->data);
    tempStack.pop();
    }
    continue;
    }
    if(front->data=='+')
    {
    nodesList.pop_front();
    flag->data='-';
    if(nodesList.size()>=2)
    nodesList.push_back(flag);
    }
    if(front->data=='$')
    {
    printf(";\n");
    nodesList.pop_front();
    if(nodesList.size()>1)
    nodesList.push_back(endOfLine);
    }
    if(front->data>='A'&&front->data<='Z')
    {
    printf("%c", front->data);
    nodesList.pop_front();
    }
    if(front->left!=NULL)
    nodesList.push_back(front->left);
    if(front->right!=NULL)
    nodesList.push_back(front->right);
    }
    delete endOfLine;
    delete flag;
    }
  • 树的初始化

    为了验证打印的正确性,实现了一个初始化函数,接收一个按层次组织起来的节点的字符串表示,输出根节点.

    Node* Tree::GenTreeByArray(const char* nodes)
    {
    if(nodes==NULL)
    return NULL;
    Node* nodesArray=new Node[strlen(nodes)];
    for(int i=0;i<strlen(nodes);i++)
    {
    nodesArray[i].
    data=nodes[i];
    }
    for(int i=0;i<strlen(nodes);i++)
    {
    Node* left=NULL;
    Node* right=NULL;
    if(2*i+1<strlen(nodes)&&nodesArray[2*i+1].data!='0')
    left=&nodesArray[2*i+1];
    if(2*i+2<strlen(nodes)&&nodesArray[2*i+2].data!='0')
    right=&nodesArray[2*i+2];
    nodesArray[i].left=left;
    nodesArray[i].right=right;
    }
    return &nodesArray[0];
    }