二叉树创建与遍历
- 对于每个节点来说,每个节点自身又是根结点，所以任然遍历到自身，会访问到自身值
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
using namespace std;
typedef struct Node{
Dtype data;
struct Node *LChild;
struct Node *RChild;
}Bnode,* Btree;
void visit(Bnode *root)
{
if(root != NULL){
cout << root->data << " ";
}
}
void CreateBtree(Btree &t)
{
Dtype e;
cin >> e;
if(e == '#')
t = NULL;
else
{
t = (Btree)malloc(sizeof(Bnode));
t->data = e;
CreateBtree(t->LChild);
CreateBtree(t->RChild);
}
}
void Pre_visit(Btree t) //前序遍历
{
if(t)
{
visit(t);
Pre_visit(t->LChild);
Pre_visit(t->RChild);
}
}
void In_visit(Btree t) //中序遍历
{
if(t)
{
In_visit(t->LChild);
visit(t);
In_visit(t->RChild);
}
}
void Post_visit(Btree t) //后序遍历
{
if(t)
{
Post_visit(t->LChild);
Post_visit(t->RChild);
visit(t);
}
}
void print_leaf(Btree t)
{
if(t)
{
if(!t->LChild && !t->RChild)
cout << t->data << " ";
print_leaf(t->LChild);
print_leaf(t->RChild);
}
}
int PostTreeDepth(Btree t)
{
int h1,h2,max;
if(t)
{
h1 = PostTreeDepth(t->LChild);
h2 = PostTreeDepth(t->RChild);
max = h1 > h2 ? h1 : h2;
return max+1;
}
else
return 0;
}
int main()
{
Btree t;
CreateBtree(t);
cout << "前序遍历二叉树" << endl;
Pre_visit(t);
cout << endl << "中序序遍历二叉树" << endl;
In_visit(t);
cout << endl << "后序遍历二叉树：" << endl;
Post_visit(t);
cout << endl << "输出叶子节点：" << endl;
print_leaf(t);
cout << endl << "输出树的深度：" << endl;
cout << PostTreeDepth(t) << endl;
return 0;
}
/*
a b # d f # # g # # c # e # h # #
*/
二叉树练习
先序遍历用顺序存储的二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int n;
int tree[10000];
int preorder(int a){
if(a >= n+1) return 0;
cout << tree[a] << " ";
if(2*a <= n) preorder(2*a);
if(2*a+1 <= n) preorder(2*a+1);
return 0;
}
int main(){
int i;
cin >> n;
for(i = 1; i < n+1; i++) cin >> tree[i];
tree[i] = -1;
preorder(1);
return 0;
}一维数组输树输出中序遍历
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
72580.数据结构第六章-二叉树顺序存储变链式存储 (20分)
C时间限制：3000 毫秒 | C内存限制：3000 Kb
题目内容：
一个二叉树不是完全的，也可以类似于完全二叉树存储在一维数组中，只是那些树中的空孩子
结点的所应在的数组元素也空起来。因此这种表示方法有空间的浪费。写一个算法将顺序存储的
普通二叉树转变为链式存储结构。然后输出中序遍历的结果
输入描述
先输入n，再输入n个整数到一维数组，数组中正整数表示结点值，而-1表示该处没有结点
输出描述
最后中序遍历的结果
输入样例
7
2 -1 3 -1 -1 4 2
输出样例
2 3 4 2
using namespace std;
int n;
int a[10000], k[100];
int judge(int i){
if(2*i <= n){
if(a[2*i] != -1) return 0;
}
return 1;
}
int tree(int ii){
for(int i = ii; i <= n; i++){
if(a[i] != -1){
if(2*i <= n){
if(a[2*i] != -1){
if(judge(2*i)&&k[2*i] != -1){
cout << a[2*i] << " ";
k[2*i] = -1;
}
tree(2*i);
}
if(k[i] != -1){
cout << a[i] << " ";
k[i] = -1;
}
if(2*i+1 <= n){
if(a[2*i+1] != -1){
if(judge(2*i+1)&&k[2*i+1] != -1){
cout << a[2*i+1] << " ";
k[2*i+1] = -1;
}
tree(2*i+1);
}
}
}
}
}
return 0;
}
int main(){
cin >> n;
memset(k, 0, sizeof(k));
for(int i = 1; i <= n; i++) cin >> a[i];
tree(1);
return 0;
}