Как преобразовать двоичное дерево поиска в двусвязный список?

Question

Учитывая двоичное дерево поиска, мне нужно преобразовать его в двусвязный список (путем обхода в зигзагообразном порядке), используя только указатели на структуры в C ++ следующим образом:

Дано дерево:

                1
                |
        +-------+---------+
        |                 |
        2                 3
        |                 |
   +----+---+        +----+---+
   |        |        |        |
   4        5        6        7
   |        |        |        |
+--+--+  +--+--+  +--+--+  +--+--+
|     |  |     |  |     |  |     |
8     9  10    11 12    13 14    15

Структура узла:

struct node
{
    char * data;
    node * left;
    node * right;
};

Создать список (зигзагообразный порядок):

1 <-> 3 <-> 2 <-> 4 <-> 5 <-> 6 <-> 7 <-> 15 <-> ... <-> 8

Может кто-нибудь, пожалуйста, помогите мне.

Answer 1

Это алгоритм поиска в ширину. Википедия содержит хорошее объяснение того, как ее реализовать.

После реализации алгоритма создание связанного списка должно быть легким делом (поскольку это будет только вопрос добавления каждого посещенного элемента в список)

Answer 2

Это неуклюжий тип обхода дерева.Интересно, как часто кому-то когда-либо приходилось делать такие вещи в реальном коде?Тем не менее, это проблема, которую нужно решить здесь ...

Вот как я бы подходил к решению этой проблемы:

Во-первых, когда я сравниваю желаемый результат со структурой дерева, я замечаючто каждый «уровень» дерева обрабатывается по очереди сверху вниз.Итак, сначала верхний узел, затем все дочерние узлы, затем все примечания потомков и так далее.Поэтому, вероятно, хорошее решение будет включать цикл, который обрабатывает один уровень и в то же время создает список узлов на следующем уровне, который будет использоваться на следующей итерации цикла.

Далее этот «зиг»zag "порядок означает, что необходимо чередовать, в каком направлении обрабатываются дочерние узлы. Если конкретная итерация идет слева направо, то следующая итерация должна идти справа налево.А затем обратно слева направо для последующей итерации и так далее.Таким образом, в моей идее цикла, который обрабатывает один уровень и создает список следующего уровня, он, вероятно, должен иметь какое-то альтернативное поведение при построении этого списка узлов для следующего уровня.На четных итерациях список строится одним способом.На нечетных итерациях список строится по-другому.

В качестве альтернативы, еще один способ думать обо всем этом: разработать решение, которое может построить список результатов в 1,2,3,4,56 и т. Д. Заказ.Затем измените этот дизайн так, чтобы он имел зигзагообразный порядок.

Достаточно ли у вас идеи о том, как разработать решение?

Answer 3

В этом решении ниже я использовал два стека для альтернативного хранения уровней. скажем, узлы на уровне 0 будут храниться в стеке 1 с именем head1, теперь вытолкнуть элемент, пока он не станет пустым, и поместить элементы в стек 2. порядок, т. е. левый или правый дочерний элемент вставки, будет зависеть от уровня порядок вставки на каждом уровне.

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;
}

Answer 4

Это может помочь вам:

2. Создать отдельный список для каждого уровня дерева
3. Обход дерева и копирование значений в списки при прохождении дерева
4. Обратный порядок любого другого списка
5. Подключить списки

Answer 5

Зачем использовать указатели ??Вы можете просто сохранить свой BST в виде массива A [1 ... n].Таким образом, A [1] будет иметь корень, A [2] и A [3] будет иметь узлы глубины 1 и т. Д. Это возможно, поскольку это почти полное дерево, и вы знаете, сколько элементов будет присутствовать взаданная глубина - то есть 2 ^ d на глубине d (кроме, конечно, на последней глубине).Теперь все, что вам нужно сделать, это получить доступ к массиву в стиле zag-zag и создать новый BST (массив) нового порядка.Итак, как бы вы пересекали массив зигзагообразно?Для любого данного элемента A [i] левый потомок будет A [2i], а правый потомок A [2i + 1].Итак, если ваша текущая глубина d нечетна, то обойдите 2 ^ d элементов, а когда вы достигнете 2 ^ d-го элемента, перейдите к его левому потомку.Если текущая глубина d четная, снова пройдитесь по 2 ^ d элементам, но когда вы достигнете 2 ^ dth элемента, перейдите к его правому потомку.Хранение их в виде массивов, а не узлов, делает вашу структуру данных проще и ваша реализация проще.

Answer 6

Хм ... Это сложный вопрос. Проблема с обходом в этом порядке заключается в том, что вы много пропускаете. Это обычно верно для любого порядка обхода дерева, который не является глубиной или шириной в первую очередь.

Вот как бы я разрешил ситуацию. Начните с одного пустого массива списков узлов и начните сначала с обхода глубины дерева. Обязательно следите за глубиной вашего обхода.

В каждой точке прохождения отметьте глубину прохождения и выберите список по индексу в массиве. Если там его нет, добавьте его первым. Если глубина четна (при условии, что root имеет глубину 0), добавьте узел в конец списка. Если это странно, добавьте его в начало.

Как только вы пройдете все узлы, объедините списки.

Answer 7

вы можете написать функцию для добавления узлов в двусвязный список.Затем вы можете вызвать эту функцию при обходе дерева.Таким образом, вы должны быть в состоянии сделать это.

Answer 8

Предположим, что корень двоичного дерева находится на уровне 0 (четное число).Последовательные уровни можно рассматривать как чередующиеся с нечетным четным (дочерние элементы root находятся на нечетном уровне, их дочерние элементы находятся на четном уровне и т. Д.). Для узла на четном уровне мы помещаем его дочерние элементы в стек (это включает обратный обход).Для узла на нечетном уровне мы помещаем его дочерние элементы в очередь (это включает прямой переход). После того, как дочерние элементы были перемещены, мы удаляем следующий доступный элемент (верхнюю часть стека или начало очереди) и рекурсивно вызываем функциюизменяя уровень на нечетный или даже в зависимости от того, где находится удаленный элемент.Удаленный элемент может быть вставлен в конец двусвязного списка.Псевдокод ниже.

// S = stack [accessible globally]
// Q = queue [accessible globally]
//    
// No error checking for some corner cases to retain clarity of original idea    
void LinkNodes(Tree *T,bool isEven,list** l)
{

     if(isEven) {
        S.push(T->right);
        S.push(T->left);
        while( !S.empty() ) {
             t = S.pop();
             InsertIntoLinkedList(l,t);
             LinkNodes(t,!isEven);
        }
     } else {
        Q.enque(T->left);
        Q.enque(T->right);
        while( !Q.empty() ) {
            t = Q.deque();
            InsertIntoLinkedList(l,t);
            LinkNodes(t,isEven);
        }
     }
}

В вызывающей функции:

bool isEven = true;
list *l = NULL;           
// Before the function is called, list is initialized with root element
InsertIntoLinkedList(&l,T); 

LinkNodes(T,isEven,&l);

Answer 9

#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);
     }
 }

Связанный список, который вы получаете здесь, однократно связан и отсортирован. Надеюсь, вы можете легко внести изменения в этот код, чтобы получить двусвязный список. Просто скопируйте - вставьте этот код и скомпилируйте его. Он будет работать нормально.

Answer 10

/* * 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; 
}