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;
}
}
The above posted code is my level order traversal code. This code works fine for me but One thing I dont like is I am explicitly initializing temp_node = NULL or I use break. But it does not seem to be a good code to me.Is there a neat implementation than this or how can I make this code better?
8 Réponses :
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);
}
}
}
La première version (avec pendant ) peut avoir un problème lorsque root == null .
Mais si je veux imprimer comme ceci: 1 2 3 4 5 6 ....... actuellement, il donne une sortie en ligne verticale unique: 1 2 3 ... 5
@CHANDRASHEKHARRAM - Ce que vous voulez, c'est "Traversal dans l'ordre". Ce code peut être adapté pour faire une traversée dans l'ordre, mais cela dépasse la portée de la question initiale.
Essayez:
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);
}
}
Un problème sérieux avec votre code existant est-il en train de se bloquer lorsqu'il est appelé sur un arbre vide ( Vous devez décider si vous voulez avoir SI N'AVEZ-VOUS NE PEUX PEUX ENQUEUE ENQUEUE NON- root = null code>). null code> Pointeurs dans la file d'attente ou non. p> NULL CODE> Valeurs. P> 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);
}
}
}
Vous pouvez essayer de cette façon:
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();
}
}
Je pense que ci-dessus, les extraits de code permettent d'imprimer le format TRAVERSAL de la commande de niveau de niveau. Ce code peut aider à écrire la solution sous forme de commande de niveau.
[ [1], [2,3], [4,5] ]
Ma solution Java à l'aide de la structure de données de la file d'attente et de l'algorithme 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;
}
class Node():
def __init__(self,value):
self.value=value
self.left_node=None
self.right_node=None
class BTree():
def __init__(self):
self.root_node=None
self.pre_order_list=[]
def push_element(self,value):
node=Node(value)
if self.root_node is None:
self.root_node=node
return
else:
self.recursion_insert(value,self.root_node)
def recursion_insert(self,value,crnt_node):
node=Node(value)
if node.value<crnt_node.value:
if crnt_node.left_node is None:
crnt_node.left_node=node
elif crnt_node.left_node is not None and node.value>crnt_node.left_node.value:
crnt_node.left_node.right_node=node
else:
self.recursion_insert(value,crnt_node.left_node)
elif node.value>crnt_node.value:
if crnt_node.right_node is None:
crnt_node.right_node=node
elif crnt_node.right_node is not None and node.value<crnt_node.right_node.value:
crnt_node.right_node.left_node=node
else:
self.recursion_insert(value,crnt_node.right_node)
else:
print('Duplicate Values')
def print_preorder_traversal(self):
self.preOrder(self.root_node)
for i in self.pre_order_list:
print(i,end='->')
print('None')
def print_inorder_traversal(self):
self.in_order(self.root_node)
def print_post_order_traversal(self):
self.post_order(self.root_node)
def print_level_order_traversal(self):
self.level_order(self.root_node)
def preOrder(self,crnt_node):
if crnt_node:
self.pre_order_list.append(crnt_node.value)
#print(crnt_node.value,end='->')
self.preOrder(crnt_node.left_node)
self.preOrder(crnt_node.right_node)
def in_order(self,crnt_node):
if crnt_node:
self.in_order(crnt_node.left_node)
print(crnt_node.value,end='->')
self.in_order(crnt_node.right_node)
def post_order(self,crnt_node):
if crnt_node :
self.post_order(crnt_node.left_node)
self.post_order(crnt_node.right_node)
print(crnt_node.value)
def level_order(self,crnt_node):
queue_list=[]
queue_list.append(crnt_node.value)
while queue_list:
if crnt_node.left_node:
queue_list.append(crnt_node.left_node)
if crnt_node.right_node:
queue_list.append(crnt_node.right_node)
queue_list.pop(0)
print(crnt_node.value,end='->')
if queue_list:
crnt_node=queue_list[0]
tree_obj=BTree()
tree_obj.push_element(70)
tree_obj.push_element(31)
tree_obj.push_element(93)
tree_obj.push_element(34)
tree_obj.push_element(14)
tree_obj.push_element(23)
tree_obj.push_element(73)
tree_obj.push_element(94)
#tree_obj.print_preorder_traversal()
#tree_obj.print_inorder_traversal()
#tree_obj.print_post_order_traversal()
tree_obj.print_level_order_traversal()
Pouvez-vous s'il vous plaît expliquer qu'avez-vous changé et pourquoi cela fonctionne?
Bonjour, mon code est à Python. Dans lequel j'ai écrit un code selon les valeurs de tri. Pour les commandes de niveau Traversal Je viens d'utiliser et assurez-vous que le premier nœud pénètre dans la file d'attente, avec ce nœud que leur enfant gauche et droit est en train d'ajouter, après cela, je supprime la valeur du nœud, la valeur du nœud gauche puis une valeur de nœud droit. [70,31,93 .....], [31 93,14,34]. [93,14,34,73,94]
Enfin, il imprimera comme 70-> 31-> 93-> 14-> 34-> 73-> 94-> 23. Laissez-moi savoir si vous ne faites pas référence à la traversée des commandes de niveau
Veuillez éditer votre réponse et ajouter votre explication, merci :)
Bonjour, pouvez-vous être plus précis, ce que vous voulez comprendre, je pense avoir expliqué ce que je faisais dans mon code. Si vous avez une préoccupation, écrivez-le ici, je vais essayer d'expliquer
Indent avec tabulation pour la cohérence.
Oh, ce n'est pas non plus généralement appelé "ordre de niveau". Il est généralement appelé «la largeur d'abord» par opposition à la «profondeur d'abord».
@OMnifarieux IMHO,
Level-Order est beaucoup plus expressif et succinct quePremière recherche d'une première recherche (BFS) Terminologie. Juste aller au niveau par niveau tout en traversant. Aussi simple que cela sonne!