1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 class BiTree
6 {
7 private:
8 struct NODE
9 {
10 int data;
11 NODE* left_child;
12 NODE* right_child;
13
14 NODE(int data, NODE* left, NODE* right)
15 {
16 this->data = data;
17 this->left_child = left;
18 this->right_child = right;
19 }
20 };
21
22 NODE* root;
23
24 //first 和 middle 分别是同一颗二叉树的先序遍历和中序遍历 first和middle不能为空
25 NODE* getRootNode(const vector<int> &first, const vector<int> &middle )
26 {
27 vector<int> left_child_of_first;
28 vector<int> left_child_of_middle;
29 vector<int> right_child_of_first;
30 vector<int> right_child_of_middle;
31
32 int data_ = first[0];
33
34 vector<int>::const_iterator iter_target;
35 for (iter_target = middle.begin(); iter_target != middle.end(); ++iter_target)
36 if (data_ == (*iter_target))
37 break;
38
39 for (vector<int>::const_iterator it = middle.begin(); it != iter_target; ++it)
40 left_child_of_middle.push_back(*it);
41 for (vector<int>::const_iterator it = iter_target+1; it != middle.end(); ++it)
42 right_child_of_middle.push_back(*it);
43
44 vector<int>::const_iterator it = first.begin() + 1;
45 while (left_child_of_first.size() < left_child_of_middle.size())
46 {
47 left_child_of_first.push_back(*it);
48 it++;
49 }
50
51 while (right_child_of_first.size() < right_child_of_middle.size())
52 {
53 right_child_of_first.push_back(*it);
54 it++;
55 }
56
57 NODE* ptr;
58 if (1 == first.size())
59 return ptr = new NODE(data_, 0, 0);
60
61 if ((0 == left_child_of_first.size())&&(0 != right_child_of_first.size()))
62 return ptr = new NODE(data_, 0 ,getRootNode(right_child_of_first, right_child_of_middle));
63 else if ((0 != left_child_of_first.size())&&(0 == right_child_of_first.size()))
64 return ptr = new NODE(data_, getRootNode(left_child_of_first, left_child_of_middle), 0);
65 else
66 return ptr = new NODE(data_, getRootNode(left_child_of_first, left_child_of_middle), getRootNode(right_child_of_first, right_child_of_middle));
67 //等效于上面的return语句,不过对于上面的语句，不同的编译器，getRootNode的计算顺序并不相同 ，在VS2003上，先调用后面的getRootNode函数
68 /*
69 {
70 NODE* p_left;
71 NODE* p_right;
72 p_left = getRootNode(left_child_of_first, left_child_of_middle);
73 p_right = getRootNode(right_child_of_first, right_child_of_middle);
74
75 return ptr = new NODE(data_, p_left, p_right);
76 }
77 */
78 }
79
80 //释放内存
81 void delete_ptr(NODE* p)
82 {
83 if (p->left_child)
84 delete p->left_child;
85 if (p->right_child)
86 delete p->right_child;
87 delete p;
88 }
89
90 //打印后序遍历
91 void last_display(NODE* p)
92 {
93 if (p->left_child && p->right_child)
94 {
95 last_display(p->left_child);
96 last_display(p->right_child);
97 cout << (p->data) << "----";
98 }
99 if (p->left_child && (!p->right_child))
100 {
101 last_display(p->left_child);
102 cout << (p->data) << "----";
103 }
104 if (! p->left_child && (p->right_child))
105 {
106 last_display(p->right_child);
107 cout << (p->data) << "----";
108 }
109 if (!(p->left_child) && !(p->right_child))
110 cout << (p->data) << "----";
111 }
112
113 public:
114
115 //构造函数(用先序遍历和中序遍历构造一个二叉树)
116 BiTree()
117 {
118 cout << "input the number of the bitree:";
119 int n=0;
120 cin >> n;
121
122 cout << "input first sort:";
123 vector<int> first;
124 int data_;
125 for (int i=0; i < n; ++i)
126 {
127 cin >> data_;
128 first.push_back(data_);
129 }
130
131 cout << "input middle sort";
132 vector<int> middle;
133 for (int i=0; i < n; ++i)
134 {
135 cin >> data_;
136 middle.push_back(data_);
137 }
138
139 root = getRootNode(first, middle);
140 }
141
142 void display()
143 {
144 NODE* p = root;
145 last_display(p);
146 }
147
148 //析构函数
149 ~BiTree()
150 {
151 delete_ptr(root);
152 }
153 };
154
155 int main()
156 {
157 BiTree bitree;
158 bitree.display();
159 system("PAUSE");
160 return 0;
161 }
posted on 2009-02-10 22:22
Jiggy.Stone 阅读(1177)
评论(0) 编辑 收藏 引用 所属分类:
C++ Zealot!