Assume that a binary tree is drawn over a Cartesian
coordinate system (with X & Y axis) where the leftmost node is
placed at point (0,0). So, we need to traverse the nodes and print in
following manner:
For e.g., for this tree
a
b c
d e f g
Output should be:
d,0,0
b,1,1
e,2,0
a,3,2
f,4,0
c,5,1
g,6,0
the x-coordinate is its cardinal (order) in an inorder traversal; and
the y coordinate is the number of levels in the tree rooted at that node;
Using these 2 pieces you can easily get the output shown above...
For e.g., for this tree
a
b c
d e f g
Output should be:
d,0,0
b,1,1
e,2,0
a,3,2
f,4,0
c,5,1
g,6,0
Strategy:
You can easily note here that for any given node:the x-coordinate is its cardinal (order) in an inorder traversal; and
the y coordinate is the number of levels in the tree rooted at that node;
Using these 2 pieces you can easily get the output shown above...
int print(node* n, int &count) { if (!n) return -1; int height = print(n->left, count) + 1; printf("%d,%d,%d", n->data, count++, height); print(n->right, count); return height; } print(root, 0);
No comments:
Post a Comment