Per un albero binario definiamo la distanza orizzontale come segue:
Horizontal distance(hd) of root = 0
If you go left then hd = hd(of its parent)-1, and
if you go right then hd = hd(of its parent)+1.
La vista dal basso di un albero è quindi composta da tutti i nodi dell'albero, in cui non vi è alcun nodo con lo stesso hd
e un livello superiore. (Potrebbero esserci più nodi di questo tipo per un dato valore di hd
. In questo caso, tutti appartengono alla vista inferiore.) Sto cercando un algoritmo che emetta la vista dal basso di un albero.
Esempi:
Supponiamo che l'albero binario sia:
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
La vista inferiore dell'albero è: 4 2 5 6 8 7
Ok so for the first example,
Horizontal distance of node with value 1: 0, level = 1
Horizontal distance of node with value 2: 0 - 1 = -1, level = 2
Horizontal distance of node with value 3: 0 + 1 = 1, level = 2
Horizontal distance of node with value 4: -1 - 1 = -2, level = 3
Horizontal distance of node with value 5: -1 + 1 = 0, level = 3
Horizontal distance of node with value 6: 1 - 1 = 0, level = 3
Horizontal distance of node with value 7: 1 + 1 = 2, level = 3
Horizontal distance of node with value 8: 0 + 1 = 1, level = 4
So for each vertical line that is for hd=0, print those nodes which appear in the last level of that line.
So for hd = -2, print 4
for hd = -1, print 2
for hd = 0, print 5 and 6 because they both appear in the last level of that vertical line
for hd = 1, print 8
for hd = 2, print 7
Un altro esempio di riferimento:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
Quindi l'output per questo sarà: 8 4 9 10 12 5 6 11 13 14 7 15
Similarly for this example
hd of node with value 1: 0, , level = 1
hd of node with value 2: -1, level = 2
hd of node with value 3: 1, level = 2
hd of node with value 4: -2, level = 3
hd of node with value 5: 0, , level = 3
hd of node with value 6: 0, level = 3
hd of node with value 7: 2, level = 3
hd of node with value 8: -3, level = 4
hd of node with value 9: -1, level = 4
hd of node with value 10: -1, level = 4
hd of node with value 11: 1, level = 4
hd of node with value 12: -1, level = 4
hd of node with value 13: 1, level = 4
hd of node with value 14: 1, level = 4
hd of node with value 15: 3, level = 4
So, the output will be:
hd = -3, print 8
hd = -2, print 4
hd = -1, print 9 10 12
hd = 0, print 5 6
hd = 1, print 11 13 14
hd = 2, print 7
hd = 3, print 15
So the ouput will be:
8 4 9 10 12 5 6 11 13 14 7 15
Conosco già un metodo in cui posso farlo usando molto spazio extra (una mappa e un array 1-D per memorizzare il livello dell'ultimo elemento in quella linea verticale) e con la complessità temporale di $ O (N \ log N) $. E questa è l'implementazione di questo metodo:
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
struct Node{
int data;
struct Node *left, *right;
};
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int height(Node *node)
{
if(node == NULL)
return 0;
else{
int lh = height(node->left);
int rh = height(node->right);
if(lh > rh)
return (lh+1);
else
return (rh+1);
}
}
void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[], int l)
{
if(node == NULL)
return;
if(level == 1){
if(lev[hd-min] == 0 || lev[hd-min] == l){
lev[hd-min] = l;
visited[hd-min].push_back(node->data);
}
}
else if(level > 1)
{
printBottom(node->left, level-1, hd-1, min, visited, lev, l);
printBottom(node->right, level-1, hd+1, min, visited, lev, l);
}
}
void findMinMax(Node *node, int *min, int *max, int hd)
{
if(node == NULL)
return;
if(hd < *min)
*min = hd;
else if(hd > *max)
*max = hd;
findMinMax(node->left, min, max, hd-1);
findMinMax(node->right, min, max, hd+1);
}
int main()
{
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->left->left->left = newNode(8);
root->left->left->right = newNode(9);
root->left->right->left = newNode(10);
root->left->right->right = newNode(11);
root->right->left->left = newNode(12);
root->right->left->right = newNode(13);
root->right->right->left = newNode(14);
root->right->right->right = newNode(15);
int min = 0, max = 0;
findMinMax(root, &min, &max, 0);
int lev[max-min+1];
map < int, vector<int> > visited;
map< int,vector<int> > :: iterator it;
for(int i = 0; i < max-min+1; i++)
lev[i] = 0;
int h = height(root);
for (int i=h; i>0; i--){
printBottom(root, i, 0, min, visited, lev, i);
}
for(it = visited.begin() ; it != visited.end() ; it++) {
for(int i=0 ; i < it->second.size() ; i++) {
cout << it->second[i] << " ";
}
}
return 0;
}
Sto cercando aiuto per farlo in modo più ottimizzato, che ha usato meno spazio o tempo. C'è qualche altro metodo efficace per questo problema?