-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathConvertTreeToList.cpp
More file actions
65 lines (62 loc) · 1.17 KB
/
ConvertTreeToList.cpp
File metadata and controls
65 lines (62 loc) · 1.17 KB
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
#include <iostream>
using namespace std;
typedef struct BSTreeNode
{
int m_nVal;
struct BSTreeNode *left;
struct BSTreeNode *right;
}DoubleList,*pList;
pList pHead;
pList pListIndex;
void convertToList(pList pCur);
void addBSNode(pList &pCur,int x) //pCur is reference , value can be dynamic changed
{
if(NULL==pCur) //if tree node is null, create a new node and assigned to pCur,
{
pList pNode=new DoubleList();
pNode->left=NULL;
pNode->right=NULL;
pNode->m_nVal=x;
pCur=pNode;
}else
{
if(pCur->m_nVal>x)
addBSNode(pCur->left,x);
else if(pCur->m_nVal<x)
addBSNode(pCur->right,x);
else //not allow insert the same element
return;
}
}
void InOrder(pList pCur)
{
if(pCur != NULL)
{
if(pCur->left != NULL)
InOrder(pCur->left);
convertToList(pCur);
if(pCur->right !=NULL)
InOrder(pCur->right);
}
}
void convertToList(pList pCur)
{
pCur->left=pListIndex;
if(pListIndex==NULL)
pHead=pCur;
else
pListIndex->right=pCur;
pListIndex=pCur;
cout<<pCur->m_nVal<<endl;
}
int main()
{
pList pRoot=NULL;
pListIndex=NULL;
pHead=NULL;
int a[]={10,4,6,8,12,14,15,16};
for(int i=0;i<8;i++)
addBSNode(pRoot,a[i]);
InOrder(pRoot);
return 0;
}