代码之家 › 专栏 › 技术社区 › josh

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

linked-list data-structures c++

josh · 技术社区 · 14 年前

给定一个二进制搜索树,我需要将它转换成一个双链表(通过遍历Zigg ZAG顺序),只使用C++中的结构指针,如下所示,

给定树:

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

节点结构:

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

创建列表(Z字形顺序):

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

有人能帮帮我吗。

11 回复 | 直到 14 年前

Gustavo Muenz 14 年前

Wikipedia 对如何实现它有很好的解释。

在实现了该算法之后,创建链表应该是一件轻而易举的事情(因为它只需要将每个访问的元素附加到列表中)

TheUndeadFish 14 年前

这是一种笨拙的树遍历类型。我想知道有多少人真的需要在真实的代码中做这样的事情。然而,这里要解决的问题是。。。

下面是我处理这个问题的方法:

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

或者,考虑这整件事的另一种方法是:设计一个可以按1、2、3、4、5、6等顺序构建结果列表的解决方案。然后修改该设计,使其具有之字形顺序。

Gabriel Schreiber 14 年前

这可能会帮助您:

为树的每个级别创建一个单独的列表
颠倒其他列表的顺序
连接列表

David Rodríguez - dribeas 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;
}

easysid 14 年前

SingleNegationElimination 14 年前

隐马尔可夫模型。。。这是一个艰难的时刻。以这种顺序遍历的问题是,您需要进行大量的跳转。这通常适用于任何不是深度或宽度优先的树遍历顺序。

下面是我将如何解决这个问题。从一个节点列表的空数组开始,首先遍历树的深度。确保跟踪遍历的深度。

在遍历的每个点上,注意遍历的深度,并在数组的索引处选取列表。如果没有,请先添加。如果深度为偶数(假设根的深度为0),则将节点添加到列表的末尾。如果很奇怪,就把它加到开头。

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

Chandini David 14 年前

Rohan Monga 14 年前

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

Bo Persson Touseef 14 年前

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

这里的链表是单独链接和排序的。希望您可以轻松地在这段代码中进行更改,以获得双链接列表。只要复制粘贴这个代码并编译它。它会很好的。

curryage 13 年前

假设二叉树的根在0级(偶数)。连续的层次可以被认为是奇偶交替的(根的子层次是奇数层次,它们的子层次是偶数层次等等)。在推送子元素之后,我们移除下一个可用的元素(栈顶或队列前面),并根据移除的元素所在的位置将level更改为奇数或偶数,从而递归地调用函数。删除的元素可以插入到双链表的末尾。下面是伪代码。

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

-1

SheetJS 11 年前

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