当前位置： 文江博客话题详情

如何将二叉搜索树转换为双向链表？

发布于 2024-09-19 13:35:06 字数 772 浏览 8 评论 0原文

给定一个二叉搜索树，我需要仅使用指向 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

有人可以吗请帮帮我。

原文

Given a binary search tree, i need to convert it into a doubly linked list(by traversing in zig zag order) using only pointers to structures in C++ as follows,

Given Tree:

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

Node Structure:

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

Create List(zig zag order):

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

Could someone please help me out.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（11）

折戟 2024-09-26 13:40:53
/* * 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; 
}

/* * 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; 
}
回复 原文
可爱咩 2024-09-26 13:40:33

假设二叉树的根位于第 0 层（偶数）。连续的级别可以被认为是奇偶之间交替的（根的子代处于奇数级别，其子代处于偶数级别等）。 对于偶数层的节点，我们将其子节点压入堆栈（这可以实现反向遍历）。对于奇数级别的节点，我们将其子节点推送到队列中（这可以实现前向遍历）。在子节点被推送后，我们删除下一个可用元素（堆栈顶部或队列前端）并递归调用通过根据删除的元素所在的位置将级别更改为奇数或偶数来发挥作用。被移除的元素可以插入到双向链表的末尾。下面的伪代码。

// 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);

Let us assume that the root of the binary tree is at level 0(an even number). Successive levels can be considered as alternating between odd even (children of root are at odd level, their children are at even level etc.). For a node at even level, we push its children onto a stack(This enables reverse traversal). For a node at odd level, we push its children onto a queue(This enables forward traversal). After children have been pushed, we remove the next available element (top of stack or front of queue) and recursively call the function by changing level to odd or even depending on where the removed element lies. The removed element can be inserted at the end of the doubly linked list. Pseudo-code below.

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

In the calling function:

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

LinkNodes(T,isEven,&l);
回复 原文
不必了 2024-09-26 13:40:12
#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);
     }
 }

您在此处获得的链接列表是单链接且排序的。希望您可以轻松地更改此代码以获得双向链表。只需复制-粘贴此代码并编译它即可。它会正常工作。

#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.

回复 原文
魔法唧唧 2024-09-26 13:39:51

这个（http://cslibrary.stanford.edu/109/TreeListRecursion.html）有漂亮图片的答案:)

This ( http://cslibrary.stanford.edu/109/TreeListRecursion.html) has the answer with pretty pictures :)

回复 原文
ぶ宁プ宁ぶ 2024-09-26 13:39:28

为什么要用指针？？您可以将 BST 存储为数组 A[1...n]。因此，A[1] 将有根，A[2] 和 A[3] 将有深度为 1 的节点，等等。这是可能的，因为它是一个几乎完整的树，并且您知道在给定深度 - 即深度 d 处的 2^d （当然最后一个深度除外）。现在您所要做的就是以锯齿状方式访问数组，并根据新顺序创建一个新的 BST（数组）。那么，如何以之字形方式遍历数组？对于任何给定元素 A[i]，左子元素为 A[2i]，右子元素为 A[2i + 1]。所以，如果你当前的深度 d 是奇数，那么遍历 2^d 个元素，当到达第 2^d 个元素时，转到它的左子元素。如果当前深度 d 是偶数，则再次遍历 2^d 个元素，但是当到达第 2^d 个元素时，转到其右子元素。将它们存储为数组而不是节点可以使您的数据结构更精简，并且实现更简单。

Why use pointers?? You could just store your BST as an array A[1...n]. So, A[1] would have root, A[2] and A[3] would have nodes of the depth 1, etc. This is possible since it is an almost complete tree, and you know how many elements will be present at a given depth - i.e. 2^d at depth d (except of course at the last depth). Now all you've got to do is access the array in a zag-zag manner, and create a new BST (array) of the new order. So, how would you traverse the array in a zig-zag manner?? For any given element A[i], the left child would be A[2i] and the right child A[2i + 1]. So, if your current depth d is odd, then traverse 2^d elements, and when you reach the 2^dth element, go to its left child. If your current depth d is even, again traverse 2^d elements, but when you reach the 2^dth element, go to its right child. Storing them as arrays rather than nodes makes your data structure leaner, and your implementation simpler.

回复 原文
权谋诡计 2024-09-26 13:39:07

嗯……这很难。按此顺序遍历的问题是您会进行大量跳跃。这对于任何非深度或广度优先的树遍历顺序通常都是正确的。

以下是我解决这种情况的方法。从一个空的节点列表数组开始，首先开始遍历树深度。请务必记录您的遍历深度。

在遍历的每个点，记下遍历的深度并选择数组中索引处的列表。如果那里没有，请先添加。如果深度是偶数（假设根的深度为0），则将该节点添加到列表的末尾。如果奇怪，请将其添加到开头。

遍历完所有节点后，连接列表。

Hmm... This is a tough one. The problem with traversal in this order is that you are doing a lot of skipping around. This is generally true in any tree traversal order that is not depth or breadth first.

Here's how I would resolve the situation. Start with a single, empty array of lists of nodes and begin traversing the tree depth first. Be sure to keep track of the depth of your traversal.

At each point in traversal, note the depth of your traversal and pick the list at the index in the array. If there isn't one there, add it first. If the depth is even (Assuming root has depth 0), add the node to the end of the list. If it's odd, add it to the beginning.

Once you've traversed all nodes, concatenate the lists.

回复 原文
冰雪之触 2024-09-26 13:38:44

您可以编写一个函数来在双向链表中添加节点。然后您可以在遍历树时调用此函数。这样你应该就可以做到了。

you can write a function to add nodes in a doubly linked list. You can then call this function while traversing the tree. In this way you should be able to do it.

回复 原文
☆獨立☆ 2024-09-26 13:38:14

在下面的解决方案中，我使用了两个堆栈来交替存储级别。
假设级别 0 的节点将存储在名称为 head1 的堆栈 1 中；现在在元素未变空时弹出该元素并将元素推入堆栈 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;
}

In this solution below I have used two stacks to store Levels alternatively.
say nodes at level 0 will be store in stack 1 whose name is head1;now pop the element while it not become empty and push the elements in stack 2.the order i.e left or right child of insertion will depend on the level.and change the insertion order at each level.

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;
}
回复 原文
ζ澈沫 2024-09-26 13:37:49

这可能会帮助您：

  1. 为树的每个级别创建一个单独的列表
  2. 遍历树并在遍历树时将值复制到列表
  3. 反转每个其他列表的顺序
  4. 连接列表

This might help you:

  1. Create a separate list for every level of the tree
  2. Traverse the tree and copy the values to the lists as you traverse the tree
  3. Reverse the order of every other list
  4. Connect the lists
回复 原文
乖乖兔^ω^ 2024-09-26 13:37:15

这是一种尴尬的树遍历类型。我想知道有多少人实际上需要在实际代码中做这样的事情。然而，这是这里要解决的问题......

这是我处理这个问题的方法：

首先，当我将所需的输出与树的结构进行比较时，我注意到树的每个“级别”都是依次处理的从上到下。因此，首先是顶部节点，然后是所有子节点，然后是所有孙节点，依此类推。因此，一个好的解决方案可能会涉及一个处理一个级别的循环，同时在下一个级别中构建一个节点列表，以便在循环的下一次迭代中使用。

接下来，这种“锯齿形”顺序意味着它需要交替处理子节点的方向。如果特定迭代从左到右，则下一次迭代必须从右到左。然后从左到右进行后续迭代，依此类推。因此，在我对处理一个级别并构建下一个级别的列表的循环的想法中，当它为下一个级别构建节点列表时，它可能需要具有某种交替行为。在偶数迭代中，列表以一种方式构建。在奇数迭代中，列表以另一种方式构建。

或者，思考整个问题的另一种方法是：设计一个可以按 1、2、3、4、5、6 等顺序构建结果列表的解决方案。然后修改该设计以具有之字形顺序。

这是否让您对如何设计解决方案有了足够的了解？

That's an awkward type of tree traversal. I wonder how often anyone has ever actually needed to do such a thing in real code. Nevertheless, it's the problem to be solved here...

Here's how I would approach dealing with this:

First, when I compare the desired output to the structure of the tree, I notice that each "level" of the tree is processed in turn from top to bottom. So top node first, then all child nodes, then all grand-child notes, and so on. So probably a good solution will involve a loop that processes one level and at the same time builds up a list of nodes in the next level to be used in the next iteration of the loop.

Next, this "zig zag" order means it needs to alternate which direction the child nodes are processed in. If a particular iteration goes from left to right, then the next iteration must go from right to left. And then back to left to right for the subsequent iteration and so on. So in my idea of a loop that processes one level and builds a list of the next level, it probably needs to have some sort of alternating behavior when it builds that list of nodes for the next level. On even iterations the list is built one way. On odd iterations the list is built the other way.

Alternatively, another other way to think about this whole thing is: Design a solution to that can build the result list in 1,2,3,4,5,6,etc order. Then modify that design to have the zig zag order.

Does this give you enough of an idea on how to design a solution?

回复 原文
听，心雨的声音 2024-09-26 13:36:16

这是一种广度优先搜索算法。 维基百科对如何实现它有很好的解释。

实现算法后，创建链接列表应该是轻而易举的事（因为只需将每个访问过的元素附加到列表中即可）

This is a Breadth-first search algorithm. Wikipedia has a good explanation on how to implement it.

After implementing the algorithm, creating your linked list should be a no-brainer (since it will only be a matter of appending each visited element to the list)

回复 原文
~没有更多了~

关于作者

青柠芒果

暂无简介

0 文章
0 评论
21 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

linfzu01

文章 0 评论 0

§对你不离不弃

文章 0 评论 0

可遇━不可求

文章 0 评论 0

枕梦

文章 0 评论 0

qq_3LFa8Q

文章 0 评论 0

JP

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文