论坛 › 技巧探讨 › 算法题-二叉树转双向链表

元始天尊 发表于 2014-4-17 17:50:38

算法题-二叉树转双向链表

1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
   10
    / \
   614
/ \ / \
48 12 16
转换成双向链表
4=6=8=10=12=14=16。

首先我们定义的二元查找树 节点的数据结构如下：struct BSTreeNode
{
    int m_nValue; // value of node
    BSTreeNode *m_pLeft; // left child of node
    BSTreeNode *m_pRight; // right child of node
};我的解法#include <stdio.h>

struct BSTreeNode
{
    int m_nValue;
    BSTreeNode* m_pLeft;//prev
    BSTreeNode* m_pRight;//next
};

BSTreeNode* addnode(int value,BSTreeNode* left=NULL,BSTreeNode* right=NULL)
{
    BSTreeNode* newone=new BSTreeNode;
    newone->m_pLeft=NULL;
    newone->m_pRight=NULL;
    newone->m_nValue=value;
    if(left)
    {
      newone->m_pLeft=left;
    }
    if(right)
    {
      newone->m_pRight=right;
    }
    return newone;
}

BSTreeNode* prevone=NULL;

void findone(BSTreeNode* curone)//中序遍历
{
    if(curone->m_pLeft)
    {
      findone(curone->m_pLeft);
    }

    prevone->m_pRight=curone;
    curone->m_pLeft=prevone;
    prevone=curone;

    if(curone->m_pRight)
    {
      findone(curone->m_pRight);
    }
}

void deletelist(BSTreeNode* head)
{
    if(head->m_pRight)
    {
      deletelist(head->m_pRight);
    }
    delete head;
}

void showlist(BSTreeNode* head)
{
    while(head->m_pRight)
    {
      printf("%d ",head->m_pRight->m_nValue);
      head=head->m_pRight;
    }
    printf("\n");
}

int main(int argc, char* argv[])
{
    BSTreeNode* head=addnode(-1);
    head->m_pLeft=NULL;
    prevone=head;

    BSTreeNode* root=addnode(10,addnode(6,addnode(4),addnode(8)),addnode(14,addnode(12),addnode(16)));
    findone(root);

    prevone->m_pRight=NULL;
    showlist(head);

    return 0;
}

0xAA55 发表于 2014-4-17 21:03:08

每次都是我来排版。。。

查看完整版本: 算法题-二叉树转双向链表