Per stampare il limite dell'albero binario

Question

Mi è stato chiesto in un'intervista di stampare il limite dell'albero binario. Per esempio.

 1 
/ \ 
    2  3 
/\ /\ 
4 5 6 7 
    / \  \ 
    8  9  10 

risposta sarà: 1, 2, 4, 8, 9, 10, 7, 3

ho proposta la seguente soluzione.

Primo metodo:

ho usato variabile Booleano per risolvere il problema di cui sopra.

void printLeftEdges(BinaryTree *p, bool print) { 
    if (!p) return; 
    if (print || (!p->left && !p->right)) 
     cout << p->data << " "; 
    printLeftEdges(p->left, print); 
    printLeftEdges(p->right, false); 
} 

void printRightEdges(BinaryTree *p, bool print) { 
    if (!p) return; 
    printRightEdges(p->left, false); 
    printRightEdges(p->right, print); 
    if (print || (!p->left && !p->right)) 
    cout << p->data << " "; 
} 

void printOuterEdges(BinaryTree *root) { 
    if (!root) return; 
    cout << root->data << " "; 
    printLeftEdges(root->left, true); 
    printRightEdges(root->right, true); 
} 

la sua risposta: Hai usato Bool variabile così tante volte. Puoi risolvere questo senza usare quello.

Secondo metodo:

ho semplicemente usato l'attraversamento di alberi per risolvere questo problema.

1. Print the left boundary in top-down manner. 
2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts: 
    2.1 Print all leaf nodes of left sub-tree from left to right. 
    2.2 Print all leaf nodes of right subtree from left to right. 
3. Print the right boundary in bottom-up manner. 

La sua risposta: Anche lui non era soddisfatto di questo metodo. Ha detto che sei attraversando l'albero 3 volte. Quello è troppo. Dare un'altra soluzione se ne avete.

Terzo Metodo: Questa volta ho andato per attraversamento livello Order (BFS).

1: Print starting and ending node of each level 
2: For each other node check if its both the children are <b>NULL</b> then print that node too. 

la sua risposta: Non era sembra contento di questo metodo anche perché questo metodo richiede memoria aggiuntiva di ordine O (n).

La mia domanda è: Dimmi un metodo che attraversa l'albero singole volte, non utilizzare alcuna variabile Bool e non utilizzare alcuna memoria aggiuntiva. È possibile?

Answer 1

Credo che questo dovrebbe fare il trucco:

traverse(BinaryTree *root) 
{ 
    if (!root) return; 
    cout << p->data << " "; 
    if (root->left) traverseL(root->left); //special function for outer left 
    if (root->right) traverseR(root->right); //special function for outer right 
} 

traverseL(BinaryTree *p) 
{ 
    cout << p->data << " "; 
    if (root->left) traverseL(root->left); //still in outer left 
    if (root->right) traverseC(root->right); 
} 

traverseR(BinaryTree *p) 
{ 
    if (root->left) traverseC(root->left); 
    if (root->right) traverseR(root->right); //still in outer right 
    cout << p->data << " "; 
} 

traverseC(BinaryTree *p) 
{ 
    if (!root->left && !root->right) //bottom reached 
    cout << p->data << " "; 
    else 
    { 
    if (root->left) traverseC(root->left); 
    if (root->right) traverseC(root->right); 
    } 
} 

Inizia con la funzione traverse. Eliminato le query null all'inizio di ogni metodo (evita una chiamata di funzione a ciascuna estremità). non ha bisogno di variabili BOOL, semplicemente utilizza tre diversi metodi di attraversamento:

• uno per il bordo sinistro, l'output del nodo prima di attraversamento
• uno per il bordo destro, in uscita il nodo dopo attraversamento
• uno per tutti gli altri nodi, emettendo il nodo se non ci sono fratelli.

Answer 2

Di seguito è una soluzione ricorsiva in Python3 con complessità temporale O (n). Algoritmo qui è quello di stampare la maggior parte dei nodi a sinistra dall'alto al basso, i nodi foglia da sinistra a destra e la maggior parte dei nodi a destra dal basso verso l'alto. L'aggiunta di flag booleani (isLeft,isRight) per l'attraversamento dell'albero sinistro e destro semplifica il codice e aumenta la complessità temporale di O (n).

#Print tree boundary nodes 
def TreeBoundry(node,isLeft,isRight): 
    #Left most node and leaf nodes 
    if(isLeft or isLeaf(node)): print(node.data,end=' ') 
    #Process next left node 
    if(node.getLeft() is not None): TreeBoundry(node.getLeft(), True,False) 
    #Process next right node 
    if(node.getRight() is not None):TreeBoundry(node.getRight(), False,True) 
    #Right most node 
    if(isRight and not isLeft and not isLeaf(node)):print(node.data,end=' ') 

#Check is a node is leaf 
def isLeaf(node): 
    if (node.getLeft() is None and node.getRight() is None): 
     return True 
    else: 
     return False 

#Get started 
#https://github.com/harishvc/challenges/blob/master/binary-tree-edge-nodes.py 
TreeBoundry(root,True,True) 

Answer 3

Metodo O(n) No extra space and single traversal of tree.

ho diviso i nodi della struttura in quattro tipi di nodi

di tipo 1 -> nodi che formano il margine sinistro (ad esempio 8)

Tipo 0 -> Nodi che non formano boundar (ad esempio 12)

Tipo 3 -> Nodi che formano il confine a destra (ad esempio 22)

Leaf nodi (ad es 4,10,14)

Nella mia metodo sto solo facendo il metodo recurrsion di albero di attraversamento (appena modificato) dove la mia funzione è di questa forma

void recFunc(btNode *temp,int type) 
    { 
     //Leaf Nodes 
    if((temp->left == NULL)&&(temp->right == NULL)) 
       cout << temp->data << " "; 
    // type -1 Nodes must be printed before their children 
    else if(type == 1)cout << temp->data << " "; 
    else {;} 


    if(type == 3) 
    { 
    if(temp->left)recFunc(temp->left,0); 
    if(temp->right)recFunc(temp->right,3); 
    //type 3 nodes must be printed after their children 
    cout << temp->data << " "; 
    } 
    else if(type == 1) 
    { 
    if(temp->left)recFunc(temp->left,1); 
    if(temp->right)recFunc(temp->right,0); 
    } 
    else if(type == 0) 
    { 
    if(temp->left)recFunc(temp->left,0); 
    if(temp->right)recFunc(temp->right,0); 
    } 
    else {;} 
    } 

dove ho modofied il

1. Nella mia funzione recurrsive nodi di tipo 1 devono rendere i loro nodi di sinistra come tipo 1 e devono essere stampati prima di chiamare i loro figli (se esistono)
2. nodi di tipo 3 devono essere stampati in retromarcia per .Quindi essi devono essere stampate dopo la chiamata alla loro children.They inoltre necessario assegnare i loro figli destra come tipo 3 nodi
3. nodi di tipo 0 non deve essere stampato e assegnare loro figli come tipo 0 nodi
4. Foglia nodi devono essere direttamente stampati solo e tornare

Link to Code