-
Notifications
You must be signed in to change notification settings - Fork 0
/
ConvertBinarySearchTree.cpp
106 lines (73 loc) · 2.21 KB
/
ConvertBinarySearchTree.cpp
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <stdio.h>
#include "utils/BinaryTree.h"
void ConvertNode(BinaryTreeNode* pRootOfTree, BinaryTreeNode** pLastNodeInList);
BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree) {
BinaryTreeNode* pLastNodeInList = NULL;
ConvertNode(pRootOfTree, &pLastNodeInList);
BinaryTreeNode* pHeadOfList = pLastNodeInList;
while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)
pHeadOfList = pHeadOfList->m_pLeft;
return pHeadOfList;
}
void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList) {
if (pNode == NULL)
return;
BinaryTreeNode *pCurrent = pNode;
if (pCurrent->m_pLeft != NULL)
ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
pCurrent->m_pLeft = *pLastNodeInList;
if(*pLastNodeInList != NULL)
(*pLastNodeInList)->m_pRight = pCurrent;
*pLastNodeInList = pCurrent;
if(pCurrent->m_pRight != NULL)
ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}
void PrintDoubleLinkedList(BinaryTreeNode* pHeadOfList)
{
BinaryTreeNode* pNode = pHeadOfList;
printf("The nodes from left to right are:\n");
while(pNode != NULL)
{
printf("%d\t", pNode->m_nValue);
if(pNode->m_pRight == NULL)
break;
pNode = pNode->m_pRight;
}
printf("\nThe nodes from right to left are:\n");
while(pNode != NULL)
{
printf("%d\t", pNode->m_nValue);
if(pNode->m_pLeft == NULL)
break;
pNode = pNode->m_pLeft;
}
printf("\n");
}
void DestroyList(BinaryTreeNode* pHeadOfList)
{
BinaryTreeNode* pNode = pHeadOfList;
while(pNode != NULL)
{
BinaryTreeNode* pNext = pNode->m_pRight;
delete pNode;
pNode = pNext;
}
}
int main() {
BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
BinaryTreeNode* pNode14 = CreateBinaryTreeNode(14);
BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12);
BinaryTreeNode* pNode16 = CreateBinaryTreeNode(16);
ConnectTreeNodes(pNode10, pNode6, pNode14);
ConnectTreeNodes(pNode6, pNode4, pNode8);
ConnectTreeNodes(pNode14, pNode12, pNode16);
PrintTree(pNode10);
printf("foo\n");
BinaryTreeNode* pNode = (Convert(pNode10));
PrintDoubleLinkedList(pNode);
DestroyList(pNode4);
return 0;
}