Home Various kinds of Tree Traversal
Post
Cancel

Various kinds of Tree Traversal

I wrote in English to avoid some nasty web scrapers.

Pre to Level

Given the preorder traversal of the tree with n nodes, the levelorder traversal of the tree is the sequence of the nodes in each level from left to right. Let’s assume that the tree is a complete tree of degree d (d>=2).

My solution is very simple: while using DFS to simulate the process of preorder traversal, increase the index number of the predorder array and store the node value at the corresponding position in levelorder array.

How to calculate the level order position? It’s better to start the array at position 0, so the node 0 is the root. If it has d children, then its children are at positions 1, 2, ..., d. If its first child viz. node 1, also has d children, then they are at positions d+1, d+2, ..., 2d. If its second child viz. node 2, also has d children, then they are at positions 2d+1, 2d+2, ..., 3d.

That is to say, we can simply obtain the index of one of node i ‘s children by calculating i*d+j, in which j is the ordinal number in the d children of node i (and j is in the range [1,d]).

The DFS function is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
int p;
void DFS(int x){
    if(x>=n) return; //here must judge x, not p
    level[x]=pre[p++];
    for(int i=1;i<=d;++i)
        DFS(x*d+i);
}
int main(){
    //...
    DFS(0);
    //...
}

If we use p>=n as the return condition, then x could be very large and getting out of bounds. This is because at the leaf level there may be less than d nodes, but in for we assume that the parent node has d children. When that occurs, p is probably less than n because it’s still in the left subtree, so it cannot guard the return condition.

Then we can easily find that parentNode = (childNode - 1) / d.

Link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int n,d,k,a,p,pre[55],level[55];
void DFS(int x){
    if(x>=n) return; //judge x, not p
    level[x]=pre[p++];
    for(int i=1;i<=d;++i)
        DFS(x*d+i);
}
int main() {
    scanf("%d%d",&n,&d);
    for(int i=0;i<n;++i)
        scanf("%d",&pre[i]);
    DFS(0);
    for(int i=0;i<n;++i){
        if(i!=0) printf(" ");
        printf("%d",level[i]);
    }
    printf("\n");
    scanf("%d",&k);
    while(k--){
        scanf("%d",&a);
        while(a){
            printf("%d ",level[a]);
            a=(a-1)/d;
        }
        printf("%d\n",level[a]);
    }
    return 0;
}

Heap to Level

Give you an inorder traversal of a heap, and you need to output its levelorder traversal.

Find the minimum node in the range [l, r] to be the root, so the left subtree is in the range [l, root-1] and the right subtree is in the range [root+1, r].

Link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int n;
queue<int>q;
struct node{
    int val,left=-1,right=-1;
}in[35];
int build(int left,int right){
    if(left>right) return -1;
    int root=left,minv=0x3f3f3f3f;
    for(int i=left;i<=right;++i)
        if(minv>in[i].val){
            minv=in[i].val;
            root=i;
        }
    in[root].left=build(left,root-1);
    in[root].right=build(root+1,right);
    return root;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&in[i].val);
    int root=build(1,n);
    q.push(root);
    while(!q.empty()){
        int top=q.front();
        q.pop();
        printf("%d",in[top].val);
        if(in[top].left!=-1) q.push(in[top].left);
        if(in[top].right!=-1) q.push(in[top].right);
        if(q.empty()) printf("\n");
        else printf(" ");
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.