Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1063602
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-04-11 20:07:23

二叉搜索树转换为排序的双向链表

如果允许使用额外的空间,中序遍历二叉搜索树即可,每遍历到一个节点,就把其插入到双向链表中。

这里要讲的是无需额外空间的方法。

   
                                       20
                                          /    \
                                        10     30
                                      /  \     /  \
                                    8    15 24  32
转换成双向链表

8--10--15--20--24--30--32

先定义一个二叉搜索树的结构和其上的插入操作,在其中加入上述节点,
然后定义函数BST2DLL(),将二叉搜索树转换为排序的双向链表。

struct node {     //二叉搜索树节点定义
    int data;
    struct node* left;
    struct node* right;
};

void tree_insert(struct node * root, struct node * new_node){ //插入节点的方法

struct node * curr1 = root;
struct node * curr2 = curr1;
while(curr1 != NULL){ //curr1沿路径下降,而curr2始终指向curr1的父节点。
curr2 = curr1;
if(new_node->data <= curr->data)
curr1 = curr1->left;
else
curr1 = curr1->right;
}
if(curr2 == NULL){ //这说明root本来就是NULL
root = new_node;
}else{
if(new_node->data < curr2->data)
curr2->left = new_node;
else
curr2->right = new_node;
}
}

int main(){
struct node * BSTree;
int array[7] = {15,20,10,8,30,24,32};
for(int i=0; i<7; i++){
struct node *new_node = (struct node *)malloc(sizeof(struct node));
new_node->data = array[i];
new_node->left = new_node->right = NULL;
tree_insert(BSTree, new_node);

struct node * DLL = BST2DLL(BSTree,1);
//BST2DLL执行后,效果还不完全是双向链表, 8=10=15=20=24=30=32,但是8和32之间还没连接。
//可通过一次遍历构造8和32直接的连接。
struct node * tmp = DLL;
while(tmp->right != NULL)
tmp++;
DLL->left = tmp;
tmp->right = DLL;
//此时DLL指向的才是一个真正的双向链表


}
//引入is_right_flag的作用:is_right_flag为1,返回的是指向链表最左端的元素的指针;
// is_right_flag为0,返回的是指向链表最右端的元素的指针;
//这是为了红色部分执行合并时的正确性
struct node * BST2DLL(struct node * root,int is_right_flag){
    if(root == NULL)
        return root;

    if(root->left != NULL)
        left_tree = BST2DLL(root->left, 0);
    if(left_tree != NULL){
        left_tree->right = root;
        root->left = left_tree;
    }

    if(root->right != NULL)
        right_tree = BST2DLL(root->right, 1);
    if(right_tree != NULL){
        right_tree->left = root;
        root->right = right_tree;
    }

    struct node * ptmp = root;
    if(is_right_flag)
        while(ptmp->left != NULL)
            ptmp = ptmp->left;
    else
         while(ptmp->right != NULL)
             ptmp = ptmp->right;

    return ptmp;
}
阅读(732) | 评论(0) | 转发(0) |
0

上一篇:转载 最长递增字串LIS问题

下一篇:B-Tree

给主人留下些什么吧!~~