Compte tenu d'un arbre de recherche binaire, j'ai besoin de le convertir en une liste doublement liée (en parcourant la commande Zig Zag) en utilisant uniquement des pointeurs vers des structures en C ++ comme suit,
ARBRE DONNÉE: P>
1 <-> 3 <-> 2 <-> 4 <-> 5 <-> 6 <-> 7 <-> 15 <-> ... <-> 8
11 Réponses :
Vous pouvez écrire une fonction pour ajouter des nœuds dans une liste doublement liée. Vous pouvez ensuite appeler cette fonction tout en parcourant l'arbre. De cette façon, vous devriez être capable de le faire.
@ Edison, Prabhu. Je pense que le BFS de l'arbre ne donnera pas exactement le résultat dans la question. Parce que les BFS de l'arbre produiraient soit: 1-2-3-4-5-6-7-8 -...- 15 ou 1-3-2-7-6-5-4-15- ... 8 (selon que vous êtes en train d'en faire d'abord enfant en premier ou à l'enfant gauche) ... Donc, la section médiane de votre liste ne sera pas donnée par bfs
C'est un type d'arbre maladroit. Je me demande combien de fois quelqu'un a déjà eu besoin de faire une telle chose en code réel. Néanmoins, c'est le problème d'être résolu ici ...
Voici comment j'approcherais de traiter avec ceci:
Premièrement, lorsque je comparais la sortie souhaitée à la structure de l'arborescence, je remarque que chaque "niveau" de l'arborescence est traité à son tour de haut en bas. Donc, le meilleur nœud d'abord, puis tous les nœuds d'enfants, puis tous les grands-enfants notes, etc. Donc, probablement une bonne solution impliquera une boucle qui traite un niveau et constitue en même temps une liste de nœuds au niveau suivant à utiliser dans la prochaine itération de la boucle.
Ensuite, cet ordre "Zig Zag" signifie qu'il doit alterner quelle direction les nœuds enfants sont traités. Si une itération particulière passe de gauche à droite, la prochaine itération doit passer de droite à gauche. Puis retour à gauche à droite pour l'itération ultérieure et ainsi de suite. Donc, dans mon idée d'une boucle qui traite un niveau et construit une liste du niveau suivant, il doit probablement avoir une sorte de comportement alternatif lorsqu'il construit cette liste de nœuds pour le niveau suivant. Sur des itérations même, la liste est construite d'une manière. Sur des itérations impaires, la liste est construite dans l'autre sens.
Alternativement, une autre autre façon de penser à tout cela est: concevoir une solution à qui peut construire la liste des résultats dans 1,2,3,4,5,6, etc. Order. Puis modifier cette conception pour avoir l'ordre Zig Zag.
Cela vous donne-t-il assez d'une idée sur la façon de concevoir une solution?
Faire le niveau Traversal puis modifier la liste n'est pas en général; Cela échouera pour les BST qui ne sont pas parfaitement équilibrés.
hmm ... c'est difficile. Le problème avec la traversée dans cet ordre est que vous faites beaucoup de sauter. Ceci est généralement vrai dans n'importe quel ordre Traversal d'arbre qui n'est pas une profondeur ou une largeur d'abord.
Voici comment je voudrais résoudre la situation. Commencez par un seul tableau vide de listes de nœuds et commencez à traverser la profondeur de l'arborescence en premier. Assurez-vous de garder une trace de la profondeur de votre traversée.
À chaque point de Traversal, notez la profondeur de votre traversée et choisissez la liste à l'index dans la matrice. S'il n'y en a pas un, ajoutez-le en premier. Si la profondeur est même (en supposant que la racine a une profondeur 0), ajoutez le nœud à la fin de la liste. Si c'est étrange, ajoutez-le au début.
Une fois que vous avez traversé tous les nœuds, concaténez les listes.
Ceci est un algorithme de recherche d'un premier abord. Wikipedia a une bonne explication sur la manière de la mettre en œuvre.
Après la mise en œuvre de l'algorithme, la création de votre liste liée doit être une évidence (puisqu'elle ne s'agira que d'ajouter chaque élément visité à la liste)
est venu pour poster ceci. C'est la bonne réponse (en fait, l'image dans la page wiki est presque identique à son image de son arbre!) Les arbres ne sont que des graphiques :)
Ce n'est pas vraiment zigzag. BFS passe à chaque niveau dans la même direction, tandis que la question indique explicitement que vous devez transversir chaque niveau dans la direction opposée au niveau précédent.
Je ferais une première recherche de largeur comme recommandée, puis utilisez le membre de l'épissure pour inverser toutes les autres rangées.
Cela pourrait vous aider:
Pourquoi utiliser des pointeurs ?? Vous pouvez simplement stocker votre BST comme tableau A [1 ... N]. Ainsi, un [1] aurait une racine, un [2] et un [3] auraient des nœuds de la profondeur 1, etc. Cela est possible car il s'agit d'un arbre presque complet, et vous savez combien d'éléments seront présents à une profondeur donnée - c'est-à-dire 2 ^ D à la profondeur d (sauf bien sûr à la dernière profondeur). Maintenant, tout ce que vous avez à faire est d'accéder à la matrice de manière zag-zag et de créer une nouvelle BST (tableau) de la nouvelle commande. Alors, comment allez-vous parcourir la matrice de manière zig-zag? Pour tout élément donné A [I], l'enfant gauche serait un [2i] et le bon enfant A [2i + 1]. Donc, si votre profondeur actuelle D est étrange, puis traverser 2 ^ D éléments et lorsque vous atteignez l'élément 2 ^ dth, allez à son enfant gauche. Si votre profondeur actuelle D est même, encore une fois, traverser 2 ^ D éléments, mais lorsque vous atteignez l'élément 2 ^ dth, allez à son enfant droit. Les stocker comme des matrices plutôt que des nœuds permet à votre structure de données maigre et de votre implémentation plus simple.
Ceci ( http://cslibrary.stanford.edu/109/trelistrecursion.html - a>) a la réponse avec de jolies images :)
Le lien est une transversale dans l'ordre de l'arborescence, pas un zigzag transversal.
/* * File: main.cpp * Author: viswesn * * Created on December 1, 2010, 4:01 PM */
struct node {
int item;
struct node *left;
struct node *right;
struct node *next;
struct node *prev;
};
struct node *dlist = NULL;
struct node *R = NULL;
struct node* EQueue[10] = {'\0'};
int Etop = 0;
struct node* OQueue[10] = {'\0'};
int Otop = 0;
int level=-1;
struct node *insert(struct node *R, int item)
{
struct node *temp = NULL;
if (R != NULL) {
if (item < R->item) {
R->left = insert(R->left, item);
} else {
R->right = insert(R->right, item);
}
} else {
temp = (struct node *)malloc(sizeof(struct node));
if (temp == NULL) {
return NULL;
}
temp->item = item;
temp->left = NULL;
temp->right = NULL;
temp->next = NULL;
temp->prev = NULL;
R = temp;
}
return R;
}
void print(struct node *node)
{
if (node != NULL) {
print(node->left);
printf("%d<->", node->item);
print(node->right);
}
}
void EvenEnqueue(struct node *item) {
if (Etop > 10) {
printf("Issue in EvenEnqueue\n");
return;
}
EQueue[Etop] = item;
Etop++;
}
void OddEnqueue(struct node *item)
{
if (Otop > 10){
printf("Issue in OddEnqueue\n");
return;
}
OQueue[Otop] = item;
Otop++;
}
int isEvenQueueEmpty() {
if (EQueue[0] == '\0') {
return 1;
}
return 0;
}
int isOddQueueEmpty()
{
if (OQueue[0] == '\0') {
return 1;
}
return 0;
}
void EvenDQueue()
{
int i = 0;
for(i=0; i< Etop; i++)
EQueue[i]='\0';
Etop = 0;
}
void OddDQueue()
{
int i = 0;
for(i=0; i< Otop; i++)
OQueue[i]='\0';
Otop = 0;
}
void addList() {
int counter = 0;
struct node *item = NULL;
if (level%2 == 0) {
/* Its Even level*/
while(counter < Etop)
{
struct node *t1 = EQueue[counter];
struct node *t2 = EQueue[counter+1];
if ((t1!=NULL) && (t2!=NULL)) {
t1->next = t2;
t2->prev = t1;
}
counter++;
}
item = EQueue[0];
} else {
/* Its odd level */
while(counter < Otop)
{
struct node *t1 = OQueue[counter];
struct node *t2 = OQueue[counter+1];
if ((t1!=NULL) && (t2!=NULL)) {
t2->next = t1;
t1->prev = t2;
}
counter++;
}
item = OQueue[Otop-1];
}
if(dlist !=NULL) {
dlist->next = item;
}
item->prev = dlist;
if (level%2 == 0) {
dlist = EQueue[Etop-1];
} else {
dlist = OQueue[0];
}
}
void printTree()
{
int nodeCount = 0;
int counter = 0;
if (!isEvenQueueEmpty()) {
/* If even level queue is not empty */
level++;
nodeCount = pow(2,level);
printf("[");
while(counter < nodeCount) {
if (EQueue[counter] != '\0') {
struct node *t = EQueue[counter];
printf("%d<->", t->item);
if (t->left != NULL)
OddEnqueue(t->left);
if (t->right != NULL)
OddEnqueue(t->right);
} else {
break;
}
counter++;
}
addList();
printf("]");
EvenDQueue();
}
counter = 0;
if (!isOddQueueEmpty()){
/* If odd level queue is not empty */
level++;
nodeCount = pow(2,level);
printf("[");
while(counter < nodeCount){
if (OQueue[counter] != '\0') {
struct node *t = OQueue[counter];
printf("%d<->", t->item);
if (t->left != NULL)
EvenEnqueue(t->left);
if (t->right != NULL)
EvenEnqueue(t->right);
} else {
break;
}
counter++;
}
addList();
printf("]");
OddDQueue();
}
if (isEvenQueueEmpty() && isOddQueueEmpty()){
return;
}
else {
printTree();
}
}
void printLevel(struct node *node)
{
if (node == NULL)
return;
EvenEnqueue(node);
printTree();
printf("\n");
}
void printList(struct node *item)
{
while(item!=NULL) {
printf("%d->", item->item);
item = item->next;
}
}
int main(int argc, char** argv) {
int a[]={20,30,40,12,2,15,18};
int size = sizeof(a)/sizeof(int);
int i = 0;
for(i=0; i< size; i++) {
R = insert(R, a[i]);
}
printf("Inoder traversal - Binary tree\n");
print(R);
printf("\n\n");
printf("Level traversal - Binary tree\n");
printLevel(R);
printf("\n");
printf("Double link list traversal - Binary tree\n");
printList(R);
printf("\n");
return 0;
}
Dans cette solution ci-dessous, j'ai utilisé deux piles pour stocker les niveaux alternativement. Dire des nœudes au niveau 0 stockera dans la pile 1 dont le nom est le nom de la tête1; désoportait maintenant l'élément alors qu'il ne devient pas vide et pousse les éléments dans la pile 2.Le ordre, c'est-à-dire que l'enfant à gauche ou à droite, l'enfant d'insertion dépendra du niveau.Et changera l'ordonnance d'insertion à chaque niveau.
node * convert_to_dll(node *p)
{
static int level=0;
push_in_stack(p,&head1);
printf("%d\n",p->data);
while( head1!=NULL || head2!=NULL) {
//pop_from_queue(&headq);
if(head1!=NULL && head2==NULL) {
while(head1!=NULL) {
if(level%2==0) {
node *p;
p=new node;
p=pop_from_stack(&head1);
if(p->right!=NULL) {
push_in_stack(p->right,&head2);
printf("%d\n",(p->right)->data);
}
if(p->left!=NULL)
{
push_in_stack(p->left,&head2);
printf("%d\n",(p->left)->data);
}
}
}
//traverse_stack(head2);
level++;
} else {
while(head2!=NULL) {
if(level%2!=0) {
node *q;
q=new node;
q=pop_from_stack(&head2);
if(q->left!=NULL) {
push_in_stack(q->left,&head1);
printf("%d\n",(q->left)->data);
}
if(q->right!=NULL) {
push_in_stack(q->right,&head1);
printf("%d\n",(q->right)->data);
}
}
} //traverse_stack(head2);
level++;
}
}
return p;
}
+1 Pour l'idée de la double pile, mais il y a des détails dans la mise en œuvre. Vous n'avez pas besoin de garder une trace du niveau et pouvez supprimer la variable et le si qui en dépendent. Vous avez des fuites de mémoire q = nouveau noeud; q = pop_from_stack (& tête); créera un nœud et le fuira dans la prochaine instruction.
#include<iostream>
#include<conio.h>
using namespace std;
class TreeNode
{
public:
int info;
TreeNode* right;
TreeNode* left;
//TreeNode* parent;
TreeNode()
{
info = 0;
right = left = NULL;
}
TreeNode(int info)
{
this -> info = info;
right = left = NULL;
}
};
class ListNode
{
public:
int info;
ListNode* next;
ListNode()
{
info = 0;
next = NULL;
}
ListNode(int info)
{
this -> info = info;
next = NULL;
}
};
TreeNode* root = NULL;
ListNode* start;
ListNode* end;
void addTreeNode(TreeNode*);
void convertTreeToList(TreeNode*);
void printList(ListNode*);
int findDepth(TreeNode*);
int _tmain(int argc, _TCHAR* argv[])
{
start = end = new ListNode(0);
char choice = 'y';
int info;
while(choice == 'y')
{
cout<<"Enter the info of new node:\n";
cin>>info;
addTreeNode(new TreeNode(info));
cout<<"Want to add a new node to the tree?(y/n)\n";
cin>>choice;
}
cout<<"Depth of the tree is: "<<findDepth(root);
cout<<"Converting the tree into a doubly linked list....\n";
convertTreeToList(root);
printList(start->next);
cin>>choice;
return 0;
}
void addTreeNode(TreeNode* node)
{
if(!root)
{
root = node;
}
else
{
TreeNode* currRoot = root;
while(1)
{
if(node -> info >= currRoot -> info)
{
if(!currRoot -> right)
{
currRoot -> right = node;
break;
}
else
{
currRoot = currRoot -> right;
}
}
else
{
if(!currRoot -> left)
{
currRoot -> left = node;
break;
}
else
{
currRoot = currRoot -> left;
}
}
}
}
}
void convertTreeToList(TreeNode* node)
{
if(node -> left != NULL)
{
convertTreeToList(node -> left);
}
end ->next = new ListNode(node -> info);
end = end -> next;
end -> next = start;
if(node -> right != NULL)
{
convertTreeToList(node -> right);
}
}
void printList(ListNode* start)
{
while(start != ::start)
{
cout<<start->info<<" -> ";
start = start -> next;
}
cout<<"x";
}
int findDepth(TreeNode* node)
{
if(!node)
{
return 0;
}
else
{
return (max(findDepth(node -> left), findDepth(node -> right)) + 1);
}
}
Linked list you get here is singly linked and sorted. Hope you can easily make changes in this code to get a doubly linked list. Just copy - paste this code and compile it.It will work fine.
Supposons que la racine de l'arbre binaire est au niveau 0 (un nombre pair). Les niveaux successifs peuvent être considérés comme alternatif entre impair même (les enfants de racine sont à un niveau impair, leurs enfants sont au niveau égal, etc.). Pour un nœud au niveau égal, nous poussons ses enfants sur une pile (cela permet une traversée inverse). Pour un nœud au niveau impair, nous poussons ses enfants sur une file d'attente (cela permet une traversée en avant). Strong> après la poussée des enfants, nous retirons le prochain élément disponible (haut de la pile ou la file d'attente) et appelez récursivement le fonction en changeant de niveau à impair ou même en fonction de l'emplacement de l'élément éliminé. L'élément éliminé peut être inséré à la fin de la liste doublement liée. Pseudo-code ci-dessous. bool isEven = true;
list *l = NULL;
// Before the function is called, list is initialized with root element
InsertIntoLinkedList(&l,T);
LinkNodes(T,isEven,&l);
L'ordre des nœuds dans la liste est-il important?
Est-ce que la partie "Créer une liste" suppose être la réponse? Je ne vois pas comment ils obtiendraient ou veulent cette liste. Cela fait beaucoup plus de sens si les résultats sont une liste (1 2 3 4 ... 15). Ou est-ce juste une traversée de niveau où chaque niveau commence à l'extrémité opposée?
@Nick: Oui, j'ai compris comment créer une liste triée. Mais ici, je dois créer dans cet ordre spécifique.
Cela semble être un ordre Zig Zag. Vous devriez mentionner cela dans votre question.
Vous pouvez utiliser une pile et une file d'attente lors de la mise en œuvre de BFS. Je pense que cela devrait fonctionner.