-
Notifications
You must be signed in to change notification settings - Fork 251
Expand file tree
/
Copy pathbinary_tree.cpp
More file actions
161 lines (152 loc) · 4.49 KB
/
binary_tree.cpp
File metadata and controls
161 lines (152 loc) · 4.49 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
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
//二叉树的链表实现
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;//左子树
TreeNode* right;//右子树
TreeNode* parent;//可以不用
};
class BinaryTree{
//TreeNode* root;//二叉树的根节点
//vector<int> tree;//二叉树的数组表示-1表示不存在的值
public:
// 创建二叉树
void build(TreeNode* &node,vector<int> &vec,int i){
if(i>vec.size() || vec[i]<0){
return ;
}
node =new TreeNode();
node->val = vec[i];
build(node->left,vec,2*i+1);
build(node->right,vec,2*i+2);
return;
}
//可视化二叉树
void display(TreeNode*node){
queue<TreeNode*> que;
que.push(node);
int i=1;
int j=0;
TreeNode* temp;
while(!que.empty()){
if(que.front()==nullptr){
que.pop();
cout<<"\t";
continue;
}
temp=que.front();
que.pop();
cout<<temp->val<<"\t";
que.push(temp->left);
que.push(temp->right);
j++;
if(j==i){
j=0;
i=2*i;
cout<<endl;
}
}
}
//处理节点值
void process(TreeNode * node){
cout<<node->val<<" ";
}
//前序遍历
void pre_order(TreeNode*node){
if(node == nullptr){
return;
}
process(node);
pre_order(node->left);
pre_order(node->right);
return;
}
//中序遍历
void mid_order(TreeNode*node){
if(node == nullptr){
return;
}
mid_order(node->left);
process(node);
mid_order(node->right);
return;
}
//后续遍历
void lst_order(TreeNode* node){
if(node == nullptr){
return;
}
lst_order(node->left);
lst_order(node->right);
process(node);
}
// 层序遍历
void layer_order(TreeNode*node){
queue<TreeNode*> que;
que.push(node);
while(!que.empty()){
if(que.front()==nullptr){
continue;
}
process(que.front());
que.push(que.front()->left);
que.push(que.front()->right);
que.pop();
}
}
//重建二叉树-前中
/*
* pre 前序遍历的数组
* mid 中序遍历的数组
* root 前序遍历中的第一个数的坐标。也就是说，该子树的根节点。
* beg2 中序遍历的起始位置。
* end2 中序遍历的结束位置。
* 问题分析：二叉树遍历问题，递归与分治的思想。创建一个树，可以分解为创建左子树和右子树两个子问题。问题的规模缩小。具有最优子结构性质，每一个子问题解法一致。子问题最终可以合并为问题的解。各个子问题相互独立。
* 选择策略：使用链表数据结构存储结果。采用递归思想递归创建。
* 算法技术：递归技术。算法流程，设计输入参数，界定本层处理范围。设计返回值即提供给上层的值。确定递归结构，分别调用左子树和右子树。确定递归的终止条件。确定递归前和递归后需要处理的内容。
* 正确性证明。
*/
TreeNode* rebuild(vector<int> pre,vector<int> mid,int root,int beg2,int end2){
if(end2<beg2){
return nullptr;
}
int i=0;
TreeNode* node= new TreeNode();
node->val=pre[root];
for(i=beg2;i<=end2;i++){
if(mid[i]==pre[root]){
break;
}
}
int dis = i-beg2;//左树的长度
node->left=rebuild(pre,mid,root+1,beg2,beg2+dis-1);
node->right=rebuild(pre,mid,root+dis+1,beg2+dis+1,end2);
return node;
}
TreeNode* rebuild2();
//重建二叉树-中后
};
int main(){
//数组表示的树
vector<int> vec{9,8,7,6,-1,4,3};
TreeNode n;
TreeNode* node=&n;
BinaryTree tree;
// tree.build(node,vec,0);
// tree.display(node);
// cout<<endl;
// tree.pre_order(node);
// cout<<endl;
// tree.mid_order(node);
// cout<<endl;
// tree.lst_order(node);
// 数组表示的前序遍历和后续遍历
vector<int> pre{3,9,20,15,7};
vector<int> mid{9,3,15,20,7};
TreeNode* node2 = tree.rebuild(pre,mid,0,0,mid.size()-1);
tree.display(node2);
return 0;
}