本文实例讲述了java实现二叉树的建立、计算高度与递归输出操作。分享给大家供大家参考，具体如下：
1. 建立 递归输出 计算高度 前中后三种非递归输出
|
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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
public class tree_link {
private int save = 0;
private int now = 0;
scanner sc = new scanner(system.in);
/*
* 构造函数
*/
tree_link(){
}
/*
* 链表建立
*/
public tree link_build(tree head){
// tree head = new tree();//头节点
system.out.println("继续code：1");
int flag = sc.nextint();
if(flag != 1){
return head;
}else{
system.out.println("\n\n\n输入 节点信息：");
head.setcode(sc.nextint());
system.out.println("\n建立 左 子树code：1 否则：0");
flag = sc.nextint();
if(flag == 1){
now++;
tree ltree = new tree();
head.setltree(ltree);
ltree.setfronttree(head);//设置父母节点
link_build( head.getltree() );
}
system.out.println("\n当前位置：" + head.getcode());
system.out.println("\n建立 右 子树code：1 否则：0");
flag = sc.nextint();
if(flag == 1){
now++;
tree rtree = new tree();
head.setrtree(rtree);
rtree.setfronttree(head);//设置父母节点
link_build( head.getrtree() );
}
if( now > save ){
save = now;
}
now--;
}
return head;
}
/*
* 输出树
*/
public tree output(tree head){
int flag;
if(head.getcode() == -1){
return head;
}else{
system.out.println("\n当前位置：" + head.getcode());
system.out.println(head.getltree() != null);
if(head.getltree() != null){
system.out.println("\n访问 左子树:");
output( head.getltree() );
}
if(head.getrtree() != null){
system.out.println("\n访问 右子树:");
output( head.getrtree() );
}
}
return head;
}
/*
* 获得高度
*/
public int getsave(){
return this.save;
}
/*
* 非递归 前序遍历
*/
public void front_traverse(tree head){
tree star = head;//退出标记
int choose = 1; //左
int flag = 1; //右
system.out.println( "<---前序遍历--->" + head.getcode() );//先访问根
while(true){
if( head.getltree() != null && choose != 0 ){
head = head.getltree();
system.out.println( "<---前序遍历--->" + head.getcode() );//获得信息
flag = 1;
}else if( head.getrtree() != null && flag != 0 ){
head = head.getrtree();
system.out.println( "<---前序遍历--->" + head.getcode() );
choose = 1;
}else if( flag == 0 && choose == 0 && head == star){
break;
}else{
if(head == head.getfronttree().getrtree()){
flag = 0;
choose = 0;
}
if(head == head.getfronttree().getltree()){
choose = 0;
flag = 1;
}
head = head.getfronttree();
system.out.println("获得 父母" + head.getcode());
system.out.println( "\n\n\n" );
}
}
}
/*
* 非递归 中序遍历
*/
public void center_traverse(tree head){
tree star = head;//退出标记
int choose = 1; //左
int flag = 1; //右
while(true){
if( head.getltree() != null && choose != 0 ){
head = head.getltree();
flag = 1;
}else if( head.getrtree() != null && flag != 0 ){
if(head.getltree() == null){//因为左边为空而返回
system.out.println( "<-1--中序遍历--->" + head.getcode());
}
head = head.getrtree();
choose = 1;
}else if( flag == 0 && choose == 0 && head == star){
break;
}else{
int area = 0;//判断哪边回来
flag = 1;
choose = 1;
if(head == head.getfronttree().getrtree()){
area = 1;//右边回来
flag = 0;
choose = 0;
}
if(head == head.getfronttree().getltree()){
area = 2;//左边回来
choose = 0;
flag = 1;
}
if( head.getltree() == null && head.getrtree() == null ){//因为左边为空而返回
system.out.println( "<-2--中序遍历--->" + head.getcode());
}
head = head.getfronttree();
if( area == 2){//因为左边访问完返回
system.out.println( "<-3--中序遍历--->" + head.getcode());
}
system.out.println("获得 父母" + head.getcode());
system.out.println( "\n\n\n" );
}
}
}
/*
* 非递归 后续遍历
*/
public void bottom_traverse(tree head){
tree star = head;//退出标记
int choose = 1; //左
int flag = 1; //右
while(true){
if( head.getltree() != null && choose != 0 ){
head = head.getltree();
flag = 1;
}else if( head.getrtree() != null && flag != 0 ){
head = head.getrtree();
choose = 1;
}else if( flag == 0 && choose == 0 && head == star){
break;
}else{
int area = 0;//判断哪边回来
flag = 1;
choose = 1;
if(head == head.getfronttree().getrtree()){
area = 1;//右边回来
flag = 0;
choose = 0;
}
if(head == head.getfronttree().getltree()){
choose = 0;
flag = 1;
}
if(head.getrtree() == null){//因为右边为空而返回
system.out.println( "<-1--后序遍历--->" + head.getcode());
}
head = head.getfronttree();
if( area == 1){
system.out.println( "<-2--后序遍历--->" + head.getcode());
}
system.out.println("获得 父母" + head.getcode());
system.out.println( "\n\n\n" );
}
}
}
}
|
2. tree 类实现：
|
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
|
public class tree {
private int code = -1;
private tree fonttree;
private tree ltree;
private tree rtree;
tree(){
this.code = -1;
this.ltree = null;
this.rtree = null;
}
/*
* 树内容查看方法：
*/
public void setcode(int code){//设置编号
this.code = code;
}
public int getcode(){ //获取编号
return this.code;
}
/*
* 设置父母指针：
*/
public void setfronttree(tree front){
this.fonttree = front;
}
public tree getfronttree(){
system.out.println("获得 父母");
return this.fonttree;
}
/*
* 设置左子女：
*/
public void setltree(tree ltree){
this.ltree = ltree;
}
public tree getltree(){
system.out.println("获得左子树");
return this.ltree;
}
/*
* 设置右子女：
*/
public void setrtree(tree rtree){
this.rtree = rtree;
}
public tree getrtree(){
system.out.println("获得右子树");
return this.rtree;
}
}
|
3. 主函数测试：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public class mainactivity {
scanner sc = new scanner(system.in);
public static void main(string[] args) {
tree head = new tree();
tree_link link_1st = new tree_link();
head = link_1st.link_build(head);
system.out.println("build succeed !");
system.out.println("\n二叉树高度-->" + link_1st.getsave());
link_1st.output(head);
system.out.println("output over !");
system.out.println("\n\n<----------------前------------------>\n前序访问根：");
link_1st.front_traverse(head);
system.out.println("\n\n<----------------中------------------>\n中序访问根：");
link_1st.center_traverse(head);
system.out.println("\n\n<----------------后------------------>\n后序访问根：");
link_1st.bottom_traverse(head);
system.out.println("\n\n\n\ntext over !\n\n\n");
}
}
|
希望本文所述对大家java程序设计有所帮助。
原文链接：https://blog.csdn.net/qq_43377749/article/details/83475907