1.把二元查找树转变成排序的双向链表[BST2DoubleLinkedList]

【题目】：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

比如将二元查找树。

/ \

6 14

/ \ / \

4 8 12 16

转换成双向链表

4=6=8=10=12=14=16。

【代码】：

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode -           the head of the sub tree
//        pLastNodeInList - the tail of the double-linked list
///////////////////////////////////////////////////////////////////////
void ConvertNode(BSTreeNode *pNode, BSTreeNode *&pLastNodeInList)
{
    if(pNode == NULL)
        return;

BSTreeNode *pCurrent = pNode;

// Convert the left sub-tree
if (pCurrent->m_pLeft != NULL)
ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

// Put the current node into the double-linked list
    pCurrent->m_pLeft = pLastNodeInList;
    if(pLastNodeInList != NULL)
        pLastNodeInList->m_pRight = pCurrent;

// Update the last node in list
pLastNodeInList = pCurrent;

// Convert the right sub-tree
if (pCurrent->m_pRight != NULL)
ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode *Convert_Solution1(BSTreeNode *pHeadOfTree)
{
    BSTreeNode *pLastNodeInList = NULL;
    ConvertNode(pHeadOfTree, pLastNodeInList);
    if (pLastNodeInList != NULL)
        pLastNodeInList->m_pRight = NULL;

// Get the head of the double-linked list
    BSTreeNode *pHeadOfList = pLastNodeInList;
    while(pHeadOfList && pHeadOfList->m_pLeft)
        pHeadOfList = pHeadOfList->m_pLeft;

return pHeadOfList;
}

【参考】：

http://blog.****.net/yysdsyl/article/details/1841632

http://www.cnblogs.com/wolenski/archive/2012/07/08/2581859.html

秒客网

1.把二元查找树转变成排序的双向链表[BST2DoubleLinkedList]

相关文章