Stampa la vista dal basso di un albero binario

0

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?

    
posta shalki 19.03.2014 - 11:49
fonte

3 risposte

0

In primo luogo, puoi ridurre la complessità del tempo a O (n), mantenendo la stessa complessità spaziale. Puoi farlo sommando visited in una singola esecuzione di printBottom :

void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] < level){
         lev[hd-min] = level;
         visited[hd-min] = new vector<int>; //erase old values, they are hidden by the current node
     }
     if(lev[hd-min] <= level){
         visited[hd-min].push_back(node->data);
     }
     printBottom(node->left, level+1, hd-1, min, visited, lev);
     printBottom(node->right, level+1, hd+1, min, visited, lev);
}

con la chiamata iniziale printBottom(root, 1, 0, min, visited, lev);

Se insisti sull'uscita beig dei nodi in ordine di aumento del valore di hd , non penso che tu possa migliorare il consumo di spazio. Tuttavia, se si consente un diverso ordine di output, è possibile eliminare visited , determinando prima per ciascun valore di 'hd', quale livello deve essere emesso e quindi eseguire un ulteriore passaggio, stampando i valori corrispondenti:

void fillLev(Node *node, int level, int hd, int min, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] < level){
         lev[hd-min] = level;
     }
     fillLev(node->left, level+1, hd-1, min, lev);
     fillLev(node->right, level+1, hd+1, min, lev);
}
void printBottom(Node *node, int level, int hd, int min, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] == level){
         cout << node->data;
     }
     printBottom(node->left, level+1, hd-1, min, lev);
     printBottom(node->right, level+1, hd+1, min, lev);
}

con chiamate fillLev(root, 1, 0, min, lev); e printBottom(root, 1, 0, min, lev); .

    
risposta data 21.03.2014 - 17:08
fonte
1

Per prima cosa crea una lista, indicizzata per linea verticale, registrando il livello massimo trovato su quella linea. Cammina l'albero una volta per compilare questo elenco.

A questo punto ogni voce [verticale] contiene il livello che può essere visto nella vista inferiore dell'albero.

Quindi cammina di nuovo sull'albero, stampando ogni nodo il cui livello corrisponde al massimo trovato sulla sua linea.

int MaxLvl[];

void printBotOne( node *qNode, int Level, int Column ) {
  if qNode then {
    printBotOne(qNode->left, Level+1, Column-1);
    if MaxLvl[Column]<Level then MaxLvl[Column] = Level;
    printBotOne(qNode->right, Level+1, Column+1);
  }
}

void printBotTwo( node *qNode, int Level, int Column ) {
  if qNode then {
    printBotTwo(qNode->left, Level+1, Column-1);
    if MaxLvl[Column]==Level then cout << qNode->data << " ";
    printBotTwo(qNode->right, Level+1, Column+1);
  }
}

void printBottom( node *qNode ) {
  for(int II = 0; II<nodecount; II++) MaxLvl[II] = 0;
  printBotOne(qNode, 0, nodecount/2);
  printBotTwo(qNode, 0, nodecount/2);
}

Ciò richiede un array 1D e viene eseguito in O (N).

    
risposta data 20.03.2014 - 06:56
fonte
0

Ci sono ancora alcune cose sulla tua domanda che non sono chiare, ma sembra che la tua regola per "bottom" sia un nodo che non ha nipoti. La seguente funzione stamperà tutti i nodi che soddisfano questa definizione di fondo:

// Print out nodes that don't have grandchildren
void printBottom2(Node *root)
{
    if (root->left) {
        // recursive call for left child
        printBottom2(root->left);
    }

    // check for grand children of this node:
    if (
         // left isn't present or has no children
         ( !root->left || ( !root->left->left && !root->left->right ) ) 
         &&
         // right isn't present or has no children
         ( !root->right || ( !root->right->left && !root->right->right) )
       )
    {
        // Since there is no child of left or right, print data:
        cout << root->data << " ";
    }

    if (root->right) {
        // recursive call for right child
        printBottom2(root->right);
    }
}

Puoi visualizzare il fondo completo di un albero chiamando printBottom2 con il solo nodo root: printBottom2(root); nel tuo codice qui sopra.

    
risposta data 19.03.2014 - 20:53
fonte

Leggi altre domande sui tag