/*!\author LiuBao\date 2011/2/25\brief 把二元查找树转变成排序的双向链表输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16转换成双向链表：4=6=8=10=12=14=16。*/#include <stdio.h>#include <stdlib.h>struct BSTreeNode /// 二元查找树/双向链表节点
{int m_nValue; ///< 节点值
struct BSTreeNode *m_pLeft; ///< 左儿子指针/前节点指针
struct BSTreeNode *m_pRight; ///< 右儿子指针/后节点指针
};
enum ChildPosition /// 儿子节点插入位置
{ Left, ///< 插入为左儿子 Right ///< 插入为右儿子};
/*!创建值为child_value的节点，并插入为parent的pos儿子\param parent 待插入儿子节点的父节点指针\param pos 儿子节点插入位置\param child_value 儿子节点的值\return 返回新插入的儿子节点的指针*/struct BSTreeNode *add_child_to_tree(struct BSTreeNode *parent,
enum ChildPosition pos, int child_value){ struct BSTreeNode *retVal = NULL; if(parent) {struct BSTreeNode *child = malloc(sizeof(struct BSTreeNode));
if(child) {child->m_nValue = child_value;
child->m_pLeft = NULL;
child->m_pRight = NULL;
if(pos == Left)parent->m_pLeft = child;
elseparent->m_pRight = child;
retVal = child;
}
}
return retVal;}
/*!创建一个二元查找树，并返回树根指针\return 二元查找树的根指针*/struct BSTreeNode *create_tree(){struct BSTreeNode *root = malloc(sizeof(struct BSTreeNode));
if(root) {root->m_nValue = 10;
root->m_pLeft = NULL;
root->m_pRight = NULL;
}
{ struct BSTreeNode *lChild = add_child_to_tree(root, Left, 6); struct BSTreeNode *rChild = add_child_to_tree(root, Right, 14); (void)add_child_to_tree(lChild, Left, 4); (void)add_child_to_tree(lChild, Right, 8); (void)add_child_to_tree(rChild, Left, 12); (void)add_child_to_tree(rChild, Right, 16);}
return root;}
/*!从二元查找树根开始，递归中根遍历转换其为有序双向链表（不可重入）\param root 二元查找树根*/void change_ptr(struct BSTreeNode *root)
{static struct BSTreeNode *last = NULL;
if(root) {change_ptr(root->m_pLeft);
if(last) {last->m_pRight = root;
root->m_pLeft = last;
}
last = root;
change_ptr(root->m_pRight);
}
}
/*!从curr节点找到头结点，并返回头结点指针\param curr 当前节点\return 双向链表头结点指针*/struct BSTreeNode *find_head(struct BSTreeNode *curr)
{ struct BSTreeNode *head = NULL; while(curr) {head = curr;
curr = curr->m_pLeft;
}
return head;}
/*!把根节点为root的二元查找树转换为有序双向链表，并返回链表头指针\param root 二元查找树的根节点\return 转换为的双向有序链表头指针*/struct BSTreeNode *to_link_list(struct BSTreeNode *root)
{change_ptr(root);
return find_head(root);}
int main(){ struct BSTreeNode *bTree = create_tree(); struct BSTreeNode *head = to_link_list(bTree); /* 测试双向有序链表 */ { struct BSTreeNode *tail = NULL; while(head) { printf("%d\n", head->m_nValue);tail = head;
head = head->m_pRight;
}
printf("reverse iterate:\n"); while(tail) { printf("%d\n", tail->m_nValue);tail = tail->m_pLeft;
}
}
return 0;}
联系客服
