1127 ZigZagging on a Tree （30 分）树的层次遍历-白红宇

1127 ZigZagging on a Tree （30 分）树的层次遍历

阅读量：4350 次

发布时间：2019-06-07

本文共 3008 字，大约阅读时间需要 10 分钟。

1127 ZigZagging on a Tree （30 分）

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in "zigzagging order" -- that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (

Output Specification:

For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

812 11 20 17 1 15 8 512 20 17 11 15 8 5 1

Sample Output:

1 11 5 8 17 12 20 15 思路： 　　我是先根据后序遍历和中序遍历序列建立这个二叉树使用的是二叉链表，然后进行层序遍历。因为题目要求进行“Z"字形层次遍历， 所以不能在遍历中直接输出，而应该每遍历完一层再输出，比如第一层是顺序输出，第二次就逆序输出。那么怎么知道一层遍历结束了呢？ 使用last变量指向每层最后一个元素的下标，当front等于last的时候，一层就结束了。这种方法在求二叉树的宽度的时候也有用到。

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               using namespace std;bool flag=true;vector
               
                 path;//对树进行深度遍历struct Node{ int data; Node *lchild,*rchild;};//Node *tree=nullptr;void create(int in[],int il,int ir,int po[],int pl,int pr,Node* &root){ if(root==nullptr) { root=new Node; root->data=po[pr]; root->lchild=root->rchild=nullptr; } int i=0; while(in[i]!=po[pr]) i++; int len=i-il;//减去中心点坐标才对 int rlen=ir-i; if(len>0) create(in,il,il+len-1,po,pl,pl+len-1,root->lchild); if(rlen>0) create(in,il+len+1,ir,po,pl+len,pr-1,root->rchild);}void print(Node *tree){ if(tree) { print(tree->lchild); cout<
                
                 data<
                 
                  rchild); }}void level(Node *tree,int n){ vector
                  
                    print; int front=0; int rail=0; Node* queue[n+10]; int odd=1; queue[rail++]=tree; cout<
                   
                    data; //print.push_back(tree->data); //front++; int last=1; while(front
                    
                     data<
                     
                      lchild!=nullptr) { queue[rail++]=temp->lchild; if(temp->lchild) print.push_back(temp->lchild->data); } if(temp->rchild!=nullptr) { queue[rail++]=temp->rchild; if(temp->rchild) print.push_back(temp->rchild->data); } if(front==last) { last=rail; if(odd==2) { reverse(print.begin(),print.end()); odd=1; } else odd=2; for(auto num:print) cout<<" "<
                      
                       >n; int in[n]; int po[n]; for(int i=0;i
                       
                        >in[i]; for(int j=0;j
                        
                         >po[j]; Node* tree=nullptr; create(in,0,n-1,po,0,n-1,tree); //print(tree); level(tree,n); return 0;}

转载于:https://www.cnblogs.com/zhanghaijie/p/10303188.html

你可能感兴趣的文章