【转载】把二元查找树转变成排序的双向链表

本文主要是介绍【转载】把二元查找树转变成排序的双向链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转自： http://blog.csdn.net/v_july_v/article/details/6870251

把二元查找树转变成排序的双向链表

 题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
    
  10
  / \
 6 14
 / \ / \
4 8 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

};

ANSWER:
This is a traditional problem that can be solved using recursion. 
For each node, connect the double linked lists created from left and right child node to form a full list.

/*** @param root The root node of the tree* @return The head node of the converted list.*/
BSTreeNode * treeToLinkedList(BSTreeNode * root) {BSTreeNode * head, * tail;helper(head, tail, root);return head;
}
void helper(BSTreeNode *& head, BSTreeNode *& tail, BSTreeNode *root) {BSTreeNode *lt, *rh;if (root == NULL) {head = NULL, tail = NULL;return;}helper(head, lt, root->m_pLeft);helper(rh, tail, root->m_pRight);if (lt!=NULL) {lt->m_pRight = root;root->m_pLeft = lt;} else  {head = root;}if (rh!=NULL) {root->m_pRight=rh;rh->m_pLeft = root;} else {tail = root;}
}

这篇关于【转载】把二元查找树转变成排序的双向链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---