Livello ordine di attraversamento di un albero binario
-
01-10-2019 - |
Domanda
void traverse(Node* root)
{
queue<Node*> q;
Node* temp_node= root;
while(temp_node)
{
cout<<temp_node->value<<endl;
if(temp_node->left)
q.push(temp_node->left);
if(temp_node->right)
q.push(temp_node->right);
if(!q.empty())
{
temp_node = q.front();
q.pop();
}
else
temp_node = NULL;
}
}
Il codice postato sopra è il mio codice attraversamento ordine di livello. Questo codice funziona bene per me, ma una cosa non mi piace è che io sono in fase di inizializzazione in modo esplicito o temp_node = NULL
io uso pausa. Ma non sembra essere un codice di buona con me.
C'è un'implementazione ordinata di questo o come posso fare questo codice migliore?
Soluzione
void traverse(Node* root)
{
queue<Node*> q;
if (root) {
q.push(root);
}
while (!q.empty())
{
const Node * const temp_node = q.front();
q.pop();
cout<<temp_node->value<<"\n";
if (temp_node->left) {
q.push(temp_node->left);
}
if (temp_node->right) {
q.push(temp_node->right);
}
}
}
, nessun caso ci più speciale. E il rientro è ripulito in modo che possa essere compreso più facilmente.
In alternativa:
void traverse(Node* root)
{
queue<Node*> q;
if (!root) {
return;
}
for (q.push(root); !q.empty(); q.pop()) {
const Node * const temp_node = q.front();
cout<<temp_node->value<<"\n";
if (temp_node->left) {
q.push(temp_node->left);
}
if (temp_node->right) {
q.push(temp_node->right);
}
}
}
Fatto come un loop for
. Personalmente, mi piace la variabile supplementare. Il nome della variabile è una scorciatoia più bello di dire 'q.front () `per tutto il tempo.
Altri suggerimenti
Si può provare in questo modo:
struct Node
{
char data;
Node* left;
Node* right;
};
void LevelOrder(Node* root)
{
if(root == NULL) return;
queue<Node*> Q;
Q.push(root);
while(!Q.empty())
{
Node* current = Q.front();
cout<< current->data << " ";
if(current->left != NULL) Q.push(current->left);
if(current->right != NULL) Q.push(current->right);
Q.pop();
}
}
Un problema serio con il codice esistente è si blocca quando viene chiamato su un albero vuoto (root = NULL
).
È necessario decidere se si vuole avere puntatori NULL
nella coda o meno.
Se non li si può solo valori enqueue non NULL
.
void traverse(Node* root) {
queue<Node*> q;
// no tree no level order.
if(root == NULL) {
return;
}
// push the root to start with as we know it is not NULL.
q.push(root);
// loop till there are nodes in the queue.
while(!q.empty()) {
// dequeue the front node.
Node *tmpNode = q.front();
q.pop();
// print it..we are sure it is not NULL.
cout<<tmpNode->value<<" ";
// enqueue left child if it exists.
if(tmpNode->left) {
q.push(tmpNode->left);
}
// enqueue right child if it exists.
if(tmpNode->right) {
q.push(tmpNode->right);
}
}
}
In alternativa, se si decide di avere NULL
nella coda che si può fare:
void traverse(Node* root) {
queue<Node*> q;
// push the root..even if it is NULL.
q.push(root);
// loop till the queue is not empty.
while(!q.empty()) {
// dequeue the front node.
Node *tmpNode = q.front();
q.pop();
// the dequeued pointer can be NULL or can point to a node.
// process the node only if it is not NULL.
if(tmpNode) {
cout<<tmpNode->value<<" ";
q.push(tmpNode->left);
q.push(tmpNode->right);
}
}
}
Il primo metodo è preferito come un grande albero ha un sacco di bambini NULL
(bambini di nodi foglia) e non v'è alcun punto di avere loro accodati nella coda quando abbiamo poi appena non li processiamo.
Prova:
void traverse(Node* root)
{
queue<Node*> q;
q.push(root);
while(!q.empty())
{
Node* temp_node = q.front();
q.pop();
if (temp_node == NULL)
{ continue;
}
cout << temp_node->value << endl;
q.push(temp_node->left);
q.push(temp_node->right);
}
}
Credo che frammenti di codice di cui sopra consentono di stampare l'attraversamento ordine di livello in formato array. Questo codice può aiutare a scrivere la soluzione in forma di ordine di livello.
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> a ;
vector<int> b;
if (root == NULL) return a;
std::queue<TreeNode *> q;
q.push(root);
int nodeCount ;
TreeNode* temp;
while(true){
nodeCount = q.size();
if (nodeCount == 0) break;
while(!nodeCount){
temp = q.front();
b.push_back(temp->val);
q.pop();
if(temp->left != NULL) q.push(temp->left);
if(temp->right!= NULL) q.push(temp->right);
nodeCount-- ;
}
a.push_back(b);
b.resize(0);
}
return a;
}
Output:
[ [1],
[2,3],
[4,5]
]
La mia soluzione Java utilizzando struttura dati della coda e l'algoritmo BFS:
void levelOrder(Node root) {
//LinkedList is class of Queue interface
Queue<Node> queue=new LinkedList<>();
queue.add(root);
//Using BFS algorithm and queue used in BFS solution
while(!queue.isEmpty()) {
Node node=queue.poll();
System.out.print(node.data+" ");
if(node.left!=null)
queue.add(node.left);
if(node.right!=null)
queue.add(node.right);
}
}
#include<iostream>
#include<queue>
using namespace std;
struct node{
int data;
node *left,*right;
};
// function for creating nodes of the tree dynamically...
node * new_node(int item){
node *temp = new node();
temp->data = item;
temp->left = NULL;
temp->right = NULL;
}
//function to perform the level order tree traversal...
void level_order(node *temp){
queue <node*> q;
q.push(temp);
while(q.empty() == false){
temp = q.front();
cout<<temp->data<<endl;
if(temp->left != NULL ){
q.push(temp->left);
}
if(temp->right !=NULL){
q.push(temp->right);
}
q.pop();
}
}
int main(){
node *root = new node(); //Creating object of the structure node...
root = NULL;
root = new_node(4);
root->left = new_node(3);
root->right = new_node(2);
root->left->left = new_node(1);
level_order(root);
return 0;
}