1 // Tree.cpp : 定义控制台应用程序的入口点。
2 //
3
4 #include
"stdafx.h"
5 #include <malloc.h>
6 #include <iostream>
7 using namespace std;
8
9 template<
class Type>
10 struct BinaryNode
11 {
12 private:
13 Type value;
14 BinaryNode<Type> *
left;
15 BinaryNode<Type> *
right;
16 public:
17 BinaryNode(Type val):left(NULL),right(NULL)
18 {
19 value =
val;
20 }
21 BinaryNode<Type> *
GetLeftBiggest();
22 BinaryNode<Type> *
GetRightSmallest();
23 void convert();
24 void Insert(BinaryNode<Type> *
ptr);
25 void Print();
26 void PrintList();
27 };
28
29 template<
class Type>
30 void BinaryNode<Type>
::Print()
31 {
32 if(
this==
NULL)
33 {
34 return;
35 }
36 cout<<value<<
endl;
37 left->
Print();
38 right->
Print();
39 }
40
41 template<
class Type>
42 void BinaryNode<Type>
::PrintList()
43 {
44 BinaryNode *l =
left;
45 BinaryNode *r =
right;
46
47 while(l->left!=
NULL)
48 {
49 l = l->
left;
50 }
51 while(l->right!=
NULL)
52 {
53 cout<<l->value<<
endl;
54 l = l->
right;
55 }
56 while(l->left !=
NULL)
57 {
58 cout<<l->value<<
endl;
59 l=l->
left;
60 }
61
62 }
63
64
65
66 template<
class Type>
67 BinaryNode<Type> * BinaryNode<Type>
::GetLeftBiggest()
68 {
69 BinaryNode<Type> *result=
NULL;
70 if(left!=
NULL)
71 {
72 result =
left;
73 while(result->right!=
NULL)
74 {
75 result = result->
right;
76 }
77 }
78 return result;
79
80 }
81
82 template<
class Type>
83 BinaryNode<Type> * BinaryNode<Type>
::GetRightSmallest()
84 {
85 BinaryNode<Type> *result=
NULL;
86 if(right!=
NULL)
87 {
88 result =
right;
89 while(result->left!=
NULL)
90 {
91 result = result->
left;
92 }
93 }
94 return result;
95 }
96
97 template<
class Type>
98 void BinaryNode<Type>
::convert( )
99 {
100 if(left!=
NULL)
101 {
102 BinaryNode<Type> *ptr =
GetLeftBiggest();
103 left->
convert();
104 ptr->right =
this;
105 this->left =
ptr;
106 }
107 if(right!=
NULL)
108 {
109 BinaryNode<Type> * ptr =
GetRightSmallest();
110 right->
convert();
111 ptr->left =
this;
112 this->right =
ptr;
113 }
114 }
115
116 template<
class Type>
117 void BinaryNode<Type>::Insert(BinaryNode<Type> *
ptr)
118 {
119 if((value>=ptr->value)&&(left ==
NULL))
120 {
121 left =
ptr;
122 return;
123 }
124 else if((value>=ptr->value)&&(left !=
NULL))
125 {
126 return left->
Insert(ptr);
127 }
128 else if((value<ptr->value)&&(right ==
NULL))
129 {
130 right =
ptr;
131 return;
132 }
133 else
134 {
135 return right->
Insert(ptr);
136 }
137 }
138
139 int _tmain(
int argc, _TCHAR*
argv[])
140 {
141 int value;
142 cout<<
"Please input the root value"<<
endl;
143 cin>>
value;
144 BinaryNode<
int> *root=
new BinaryNode<
int>
(value);;
145
146 int TreeNodeNumber;
147 cout<<
"Please input the Tree Node Numbers:"<<
endl;
148 cin>>
TreeNodeNumber;
149 BinaryNode<
int> **nodes =
new BinaryNode<
int> *
[TreeNodeNumber];
150 for(
int index=
0;index<TreeNodeNumber;index++
)
151 {
152 int value;
153 cout<<
"Please input the "<<index+
1<<
" Node"<<
endl;
154 cin>>
value;
155 nodes[index] =
new BinaryNode<
int>
(value);
156 root->
Insert(nodes[index]);
157 }
158
159 root->
Print();
160 root->
convert();
161 root->
PrintList();
162
163 return 0;
164 }
参考：
http://blog.csdn.net/anialy/article/details/7645535
