很楠不爱3

这个屌丝很懒，什么也没留下！

热门标签

二叉树java实现_java 二叉树实现

作者：很楠不爱3 | 2024-05-20 16:32:54

踩

java 二叉树实现

文章目录

一、二叉树

一、二叉树

1、树的常用术语

树示意图：
结点
根节点
父节点
子节点
叶子结点（没有子节点的结点）
结点的权（结点值）
路劲（从root结点找到该节点的路线）
层
子树
树的高度（最大层数）
森林（多棵二叉树构成森林）

2、二叉树的概念

树有很多种，每个结点最多只能有两个子节点的一种形式称为二叉树。
二叉树的字子节点分为左结点和右结点
示意图：
如果该二叉树的所有叶子结点都在最后一层，并且结点总数为：2n-1,n为层数，则我们称之为满二叉树。
如果该二叉树的所有叶子结点都在最后一层或者倒数第二层，而且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续，我们称之为完全二叉树。

3、二叉树的遍历说明

使用前序,中序和后序对下面的二叉树进行遍历.
- 前序遍历：先输出父节点,再遍历左子树和右子树
- 中序遍历：先遍历左子树,再输出父节点,再遍历右子树
- 后序遍历：先遍历左子树,再遍历右子树,最后输出父节点
- 小结：看输出父节点的顺序,就确定是前序,中序还是后序

二叉树的遍历应用实例（前序，中序，后序）

应用实例的说明和思路：

在这里插入图片描述

代码实现

/* file:BinaryTreeDemo.java */
class BinaryTreeDemo{
    public static void main(String[] args){
        //先构建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建常见需要的结点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");
        binaryTree.setRoot(root);

        // 说明：这里我们先手动创建二叉树吗，后面再使用递归的方式创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);

        // 测试遍历
        System.out.println("测试遍历~~~");
        System.out.println("前序遍历：");
        binaryTree.preOder();   // 1,2,3,5,4

        System.out.println("中序遍历：");
        binaryTree.infixOrder();    // 2,1,5,3,4

        System.out.println("后序遍历：");
        binaryTree.position();  // 2,5,4,3,1
    }
} 

// 定义二叉树
class BinaryTree{
    private HeroNode root;

    public void setRoot(HeroNode root){
        this.root = root;
    }

    // 前序遍历
    public void preOder(){
        if(this.root != null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空，无法遍历!!!");
        }
    }
    
    // 中序遍历
    public void infixOrder(){
        if(this.root != null){
            this.root.infixOrder();
        }else{
            System.out.println("二叉树为空，无法遍历!!!");
        }
    }

    // 后序遍历
    public void position(){
        if(this.root != null){
            this.root.position();
        }else{
            System.out.println("二叉树为空，无法遍历!!!");
        }
    }
}

//  先创建结点
class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name){
        this.no = no;
        this.name = name;    
    } 

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode [no="+ no +",name="+ name +"]";
    }

    // 前序遍历
    public void preOrder(){
        // 输出当前结点
        System.out.println(this);

        // 遍历左子树
        if(this.left != null){
            this.left.preOrder();
        }

        // 遍历右子树
        if(this.right != null){
            this.right.preOrder();
        }
    }
    
    // 中序遍历
    public void infixOrder(){
        // 遍历左子树
        if(this.left != null){
            this.left.infixOrder();
        }

        // 输出当前结点
        System.out.println(this);

        // 遍历右子树
        if(this.right != null){
            this.right.infixOrder();
        }
    } 

    // 后序遍历
    public void position(){
        // 遍历左子节点
        if(this.left != null){
            this.left.position();
        }

        // 遍历右子节点
        if(this.right != null){
            this.right.position();
        }

        // 输出当前结点
        System.out.println(this);
    }
}
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

二叉树-查找指定结点

要求

1)请编写前序查找,中序查找和后序查找的方法。
2)并分别使用三种查找方式,查找heroNO=5的节点
3)并分析各种查找方式,分别比较了多少次
4)思路分析图解

在这里插入图片描述

5）代码实现

/* file:BinaryTreeDemo.java */
class BinaryTreeDemo{
    public static void main(String[] args){
        //先构建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建常见需要的结点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");
        binaryTree.setRoot(root);

        // 说明：这里我们先手动创建二叉树吗，后面再使用递归的方式创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);

        // // 测试遍历
        // System.out.println("测试遍历~~~");
        // System.out.println("前序遍历：");
        // binaryTree.preOder();   // 1,2,3,5,4

        // System.out.println("中序遍历：");
        // binaryTree.infixOrder();    // 2,1,5,3,4

        // System.out.println("后序遍历：");
        // binaryTree.position();  // 2,5,4,3,1

        // 测试查找
        System.out.println("测试查找~~~");
        int num = 5;    //查找目标
        HeroNode resNode;
        //中序查找
        System.out.println("前序查找：");
        resNode = binaryTree.preOrderSearch(num);
        if(resNode != null){
            System.out.printf("找到了，信息为： no = %d，name = %s\n",resNode.getNo(), resNode.getName());
        }else{
            System.out.printf("没有找到 no = %d 的英雄！\n",num);
        }

        //中序查找
        System.out.println("中序查找：");
        resNode = binaryTree.infixOrderSearch(num);
        if(resNode != null){
            System.out.printf("找到了，信息为： no = %d，name = %s\n",resNode.getNo(), resNode.getName());
        }else{
            System.out.printf("没有找到 no = %d 的英雄！\n",num);
        }

        //中序查找
        System.out.println("后续查找：");
        resNode = binaryTree.positOrderSearch(num);
        if(resNode != null){
            System.out.printf("找到了，信息为： no = %d，name = %s\n",resNode.getNo(), resNode.getName());
        }else{
            System.out.printf("没有找到 no = %d 的英雄！\n",num);
        }
    }
} 

// 定义二叉树
class BinaryTree{
    private HeroNode root;

    public void setRoot(HeroNode root){
        this.root = root;
    }

    // // 前序遍历
    // public void preOder(){
    //     if(this.root != null){
    //         this.root.preOrder();
    //     }else{
    //         System.out.println("二叉树为空，无法遍历!!!");
    //     }
    // }
    
    // // 中序遍历
    // public void infixOrder(){
    //     if(this.root != null){
    //         this.root.infixOrder();
    //     }else{
    //         System.out.println("二叉树为空，无法遍历!!!");
    //     }
    // }

    // // 后序遍历
    // public void position(){
    //     if(this.root != null){
    //         this.root.position();
    //     }else{
    //         System.out.println("二叉树为空，无法遍历!!!");
    //     }
    // }

    // 前序查找
    public HeroNode preOrderSearch(int no){
        if(root != null){
            return root.preOrderSearch(no);
        }else{
            return null;
        }
    }

    // 中序查找
    public HeroNode infixOrderSearch(int no){
        if(root != null){
            return root.infixOrderSearch(no);
        }else{
            return null;
        }
    }

    // 后续查找
    public HeroNode positOrderSearch(int no){
        if(root != null){
            return root.positOrderSearch(no);
        }else{
            return null;
        }
    } 
}

//  先创建结点
class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name){
        this.no = no;
        this.name = name;    
    } 

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode [no="+ no +",name="+ name +"]";
    }

    // // 前序遍历
    // public void preOrder(){
    //     // 输出当前结点
    //     System.out.println(this);

    //     // 遍历左子树
    //     if(this.left != null){
    //         this.left.preOrder();
    //     }

    //     // 遍历右子树
    //     if(this.right != null){
    //         this.right.preOrder();
    //     }
    // }
    
    // // 中序遍历
    // public void infixOrder(){
    //     // 遍历左子树
    //     if(this.left != null){
    //         this.left.infixOrder();
    //     }

    //     // 输出当前结点
    //     System.out.println(this);

    //     // 遍历右子树
    //     if(this.right != null){
    //         this.right.infixOrder();
    //     }
    // } 

    // // 后序遍历
    // public void position(){
    //     // 遍历左子节点
    //     if(this.left != null){
    //         this.left.position();
    //     }

    //     // 遍历右子节点
    //     if(this.right != null){
    //         this.right.position();
    //     }

    //     // 输出当前结点
    //     System.out.println(this);
    // }

    // 前序遍历查找
    /*
     * 
     * @param no 查找no
     * @return 如果找到就返回Node，如果没有找到就返回 null
    */
    public HeroNode preOrderSearch(int no){
        System.out.println("进入前序查找~");
        // 比较当前结点是不是要找的结点
        if(this.no == no){
            return this;
        }
        
        HeroNode resNode = null;
        // 1.判断当前结点的左子节是否为空，如果不为空，则递归前序查找
        // 2.如果左递归前序查找，找到结点，返回结点
        if(this.left != null){
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        // 1.左递归前序查找，找到结点，则返回，否则继续判断，
        // 2.判断当前的结点的右子结点是否为空，如果不空，则继续向右递归前序查找
        if(this.right != null){
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }

    // 中序遍历查找
    public HeroNode infixOrderSearch(int no){
        HeroNode resNode = null;
        // 1.判断当前结点的左子节是否为空，如果不为空，则递归中序查找
        if(this.left != null){
            resNode = this.left.infixOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        System.out.println("进入中序查找~");
        // 判断当前结点是否为查找结点，是返回，否则继续
        if(this.no == no){
            return this;
        }

        // 右递归中序查找
        if(this.right != null){
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    // 后续遍历查找
    public HeroNode positOrderSearch(int no){
        HeroNode resNode = null;
        // 左递归后续查找
        if(this.left != null){
            resNode = this.left.positOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        // 右递归后序查找
        if(this.right != null){
            resNode = this.right.positOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        System.out.println("进入后续查找~");
        // 判断当前结点是否为查找结点，是返回，否则继续
        if(this.no == no){
            return this;
        }

        return resNode;
    }
}
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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306

4、二叉树-删除结点

要求
- 1）如果删除的节点是叶子节点，则删除该节点
- 2）如果删除的节点是非叶子节点，则删除该子树.
- 3）测试，删除掉5号叶子节点和3号子树.
- 4）完成删除思路分析

在这里插入图片描述

5）代码实现

/* file:BinaryTreeDemo.java */
// 在 HeroNode 类中增加代码
// 递归删除指定结点
// 1.如果删除的结点为叶子结点，则删除该结点
// 2.如果删除结点不是叶子结点，则删除该子树
public void delNode(int no){
    // 思路：
    /*
     *  1.因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点，
        2.如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left=nul1；并且就返回(结束递归删除)
        3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null；并且就返回（结束递归删除）
        4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
        5.如果第4步也没有删除结点，则应当向右子树进行递归删除。
    */
    
    // 2.如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left=nul1；并且就返回(结束递归删除)
    if(this.left != null && this.left.no == no){
        this.left = null;
        return;
    }

    // 3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null；并且就返回（结束递归删除）
    if(this.right != null && this.right.no == no){
        this.right = null;
        return;
    }

    // 4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
    if(this.left != null){
        this.left.delNode(no);
    }

    // 5.如果第4步也没有删除结点，则应当向右子树进行递归删除。
    if(this.right != null){
        this.right.delNode(no);
    }
}

// 在 BinaryTree 类中增加代码
// 删除结点
public void delNode(int no){
    // 判断root结点是否为空
    if(this.root != null){
        // 这里马上就要判断删除结点是否为root结点，否则后面就没机会了
        if(this.root.getNo() == no){
            this.root = null;
            return;
        }else{
            this.root.delNode(no);
        }
    }else{
        System.out.println("空树，无法进行删除结点操作！！！");
    }
}


// 在 BinaryTreeDemo类 main方法中增加代码
// 测试删除结点
System.out.println("删除前，进行前序遍历");
binaryTree.preOder();
// binaryTree.delNode(5);
binaryTree.delNode(3);
System.out.println("删除后，前序遍历：");
binaryTree.preOder();

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

5、顺序存储二叉树

概念

基本说明
- 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换为二叉树，树也可以转换为数组，看下面的示意图。
要求
- 右图的二叉树的结点要求以数组的方式来存放 arr：[1,2,3,4,5,6,7]
- 要求在遍历数组arr时，仍然可以前序遍历，中序遍历和后序遍历的方式来完成结点的遍历。
二叉树存储的特点：
- 顺序书通常只会考虑二叉树
- 第n个元素的左子节点为 2*n+1
- 第n个元素的右子节点为 2*n+2
- 第n个元素的父节点为 (n-1)/2
- n:表示二叉树中的第几个元素（按0开始编号如下图所示）
顺序存储二叉树的遍历
- 要求：给你一个数组{1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。
- 前序遍历的结构应该为：1,2,4,5,3,6,7
- 中序遍历的结点应该为：4,2,5,1,6,3,7
- 后序遍历的结点应该为：4,5,2,6,7,3,1
- 代码实现：

/* file:ArrBinaryTreeDemo.java */
public class ArrBinaryTreeDemo{
    public static void main(String[] args){
        int[] arr = {1,2,3,4,5,6,7};
        // 创建一个ArrBinaryTree
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        System.out.print("前序遍历：");
        // arrBinaryTree.preOrder(0);	//1,2,4,5,3,6,
        //使用重载的前序遍历方法，这样可以省去传0参的步骤，使代码更加整洁
        arrBinaryTree.preOrder();   
        System.out.println();
        System.out.print("中序遍历：");
        // arrBinaryTree.infixOrder(0);	//4,2,5,1,6,3,7
        arrBinaryTree.infixOrder();
        System.out.println();
        System.out.print("后续遍历：");
        // arrBinaryTree.followUp(0);	//4,5,2,6,7,3,1
        arrBinaryTree.followUp();
        System.out.println();
    }
}

class ArrBinaryTree{
    private int[] arr; //存储二叉树数据结点的数组

    public ArrBinaryTree(int[] arr){
        this.arr = arr;
    }


    // 重载 preOder()
    public void preOrder(){
        this.preOrder(0);
    }

    // 重载 infixOrder()
    public void infixOrder(){
        this.infixOrder(0);
    }

    // 重载 followUp()
    public void followUp(){
        this.followUp(0);
    }

    //编写一个方法完成顺序存储二叉树的前序遍历
    /**
	*
	* @param index 数组的下标
	*/
    public void preOrder(int index){
        // 如果数组为空，或者arr.length = 0
        if(arr == null || arr.length == 0){
            System.out.println("数组为空，不能按照二叉树的前序遍历！！！");
        }
        //输出当前这个元素
        System.out.print(arr[index]);
        //向左递归遍历
        if(index * 2 + 1 < arr.length){
            preOrder(index * 2 + 1);
        }
        //向右递归遍历
        if(index * 2 + 2 < arr.length){
            preOrder(index * 2 + 2);
        }
        return;
    }

    //编写一个方法完成顺序存储二叉树的中序遍历
    /**
	*
	* @param index 数组的下标
	*/
    public void infixOrder(int index){
        if(arr == null && arr.length == 0){
            System.out.println("数组为空，不能按照二叉树的中序遍历！！！");
        }
        if(index * 2 + 1 < arr.length){
            infixOrder(index * 2 + 1);
        }
        System.out.print(arr[index]);

        if(index * 2 + 2 < arr.length){
            infixOrder(index * 2 + 2);
        }
        return;
    }

    //编写一个方法完成顺序存储二叉树的后续遍历
    /**
	*
	* @param index 数组的下标
	*/
    public void followUp(int index){
        if(arr == null && index == arr.length){
            System.out.println("数组为空，不能按照二叉树的中序遍历！！！");
        }
        if(index * 2 + 1 < arr.length){
            followUp(index * 2 + 1);
        }
        if(index * 2 + 2 < arr.length){
            followUp(index * 2 + 2);
        }
        System.out.print(arr[index]);
    }
}
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

6、线索化二叉树

先看一个问题
- 将数列{1,3,6,8,10,14}构建成一颗二叉树. n+1=7

在这里插入图片描述

问题分析:
1. 当我们对上面的二叉树进行中序遍历时,数列为(8,3, 10, 1, 6, 14)
2)但是6,8, 10, 14这几个节点的左右指针，并没有完全的利用上.
3)如果我们希望充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点,怎么办?
4)解决方案-线索二叉树

线索化二叉树基本介绍

1. n个结点的二叉链表中含有n+1 【公式2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")
2)这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
1. 一个结点的前一个结点,称为前驱结点
4)一个结点的后一个结点，称为后继结点

线索化二叉树应用案例

应用案例说明:将下面的二叉树，进行中序线索二叉树。中序遍历的数列为{8,3,10,1,14,6}

在这里插入图片描述

思路分析：中序遍历的结果：{8,3,10,1,14,6}

在这里插入图片描述

说明：当线索化二叉树后，Node节点的属性left和right，有如下情况：
- 1）left指向的是左子树，也可能是指向的前驱节点.比如①节点left指向的左子树，而 ⑩节点的left指向的就是前驱节点.
- 2）right指向的是右子树，也可能是指向后继节点，比如①节点right 指向的是右子树，而①节点的right 指向的是后继节点.
代码实现

/* file:ThreadedBinaryTreeDemo.java */

public class ThreadedBinaryTreeDemo{
    public static void main(String[] args){
        // 测试二叉树中序线索化功能
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");

        extracted(root, node2);
        root.setRight(node3);
        extracted(node2, node4);
        node2.setRight(node5);
        extracted(node3, node6);

        //测试线索化
        ThreadeBinaryTree threadeBinaryTree = new ThreadeBinaryTree();
        threadeBinaryTree.setRoot(root);
        threadeBinaryTree.threadedNodes();

        // 测试：以10号结点测试
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是= " + leftNode);    //3
        System.out.println("10号结点的后继结点是= " + rightNode);   //1

        // 当线索化二叉树后，再用原来的遍历方式会出现问题
        // 因为原来的二叉树遍历是通过结点左右子节点为空来进行的
        // 线索化后的二叉树将结点的左右指针都有值了
        // threadeBinaryTree.infixOrder();
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadeBinaryTree.threadedList();   // 8,3,10,1,14,6

    }

    private static void extracted(HeroNode node2, HeroNode node4) {
        node2.setLeft(node4);
    }
}

// 定义 ThreadeBinaryTree 实现了线索化功能的二叉树
class ThreadeBinaryTree{
    private HeroNode root;

    // 为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
    // 在递归进行线索化时，pre 总是保留前一个结点
    private HeroNode pre = null;

    public void setRoot(HeroNode root){
        this.root = root;
    }

    // 重载 threadedNodes 方法
    public void threadedNodes(){
        this.threadedNodes(root);
    }

    // 遍历线索化二叉树的方法
    public void threadedList(){
        // 定义一个变量，临时存储当前遍历的结点，从root开始
        HeroNode node = root;
        while(node != null){
            // 循环遍历找到leftType = 1 的这个结点，第一个找到的就是 8 结点
            // 后面随着遍历而变化，因当leftType = 1 时，说明该结点是按照线索化
            // 处理后的有效结点
            while(node.getleftType() == 0){
                node = node.getLeft();
            }
            // 打印当前结点
            System.out.println(node);
            // 如果当前结点的右指针指向的是后继结点，就一直输出
            while(node.getRitghtType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            // 替换这个遍历的结点
            node = node.getRight();
        }
    }

    // 编写对二叉树进行对中序线索化的方法
    /*
     * 
     * @param node 就是当前需要线索化的结点
    */
    public void threadedNodes(HeroNode node) {
        // 如果node == null,就不能线索化
        if(node == null){ 
            return;
        }

        // (一)先线索化左子树
        threadedNodes(node.getLeft());
        // (二)线索化当前结点
        
        // 处理当前结点的前驱结点
        if(node.getLeft() == null){
            // 让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            // 修改当前结点的左指针类型，指向前驱结点
            node.setleftType(1);
        } 

        // 处理后继结点
        if(pre != null && pre.getRight() == null){
            // 让前驱结点的右指针指向当前结点
            pre.setRight(node);
            // 修改前驱结点的右指针类型
            pre.setRitghtType(1);
        }
        // !!! 没处理一个结点后，让当前结点是下一个结点的前驱结点
        pre = node;

        // (三)在线索化右子树
        threadedNodes(node.getRight());
    }

    // 删除结点
    public void delNode(int no){
        // 判断root结点是否为空
        if(this.root != null){
            // 这里马上就要判断删除结点是否为root结点，否则后面就没机会了
            if(this.root.getNo() == no){
                this.root = null;
                return;
            }else{
                this.root.delNode(no);
            }
        }else{
            System.out.println("空树，无法进行删除结点操作！！！");
        }
    }

    // 前序遍历
    public void preOder(){
        if(this.root != null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空，无法遍历!!!");
        }
    }
    
    // 中序遍历
    public void infixOrder(){
        if(this.root != null){
            this.root.infixOrder();
        }else{
            System.out.println("二叉树为空，无法遍历!!!");
        }
    }

    // 后序遍历
    public void position(){
        if(this.root != null){
            this.root.position();
        }else{
            System.out.println("二叉树为空，无法遍历!!!");
        }
    }

    // 前序查找
    public HeroNode preOrderSearch(int no){
        if(root != null){
            return root.preOrderSearch(no);
        }else{
            return null;
        }
    }

    // 中序查找
    public HeroNode infixOrderSearch(int no){
        if(root != null){
            return root.infixOrderSearch(no);
        }else{
            return null;
        }
    }

    // 后续查找
    public HeroNode positOrderSearch(int no){
        if(root != null){
            return root.positOrderSearch(no);
        }else{
            return null;
        }
    } 
}

//  先创建结点
class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    // 说明
    // 1.如果leftType == 0 表示指向的是左子树，如果1则表示指向前驱结点
    // 2.如果rightType == 0 表示指向的是右子树，如果为1表示指向后继结点
    private int leftType;
    private int ritghtType;
 
    public int getleftType(){
        return leftType;
    }

    public void setleftType(int leftType){
        this.leftType  = leftType;
    }

    public int getRitghtType() {
        return ritghtType;
    }

    public void setRitghtType(int ritghtType) {
        this.ritghtType = ritghtType;
    }

    public HeroNode(int no, String name){
        this.no = no;
        this.name = name;    
    } 

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode [no="+ no +",name="+ name +"]";
    }

    // 递归删除指定结点
    // 1.如果删除的结点为叶子结点，则删除该结点
    // 2.如果删除结点不是叶子结点，则删除该子树
    public void delNode(int no){
        // 思路：
        /*
         *  1.因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点，
            2.如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left=nul1；并且就返回(结束递归删除)
            3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null；并且就返回（结束递归删除）
            4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
            5.如果第4步也没有删除结点，则应当向右子树进行递归删除。
        */
        
        // 2.如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left=nul1；并且就返回(结束递归删除)
        if(this.left != null && this.left.no == no){
            this.left = null;
            return;
        }

        // 3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null；并且就返回（结束递归删除）
        if(this.right != null && this.right.no == no){
            this.right = null;
            return;
        }

        // 4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
        if(this.left != null){
            this.left.delNode(no);
        }

        // 5.如果第4步也没有删除结点，则应当向右子树进行递归删除。
        if(this.right != null){
            this.right.delNode(no);
        }
    }

    // 前序遍历
    public void preOrder(){
        // 输出当前结点
        System.out.println(this);

        // 遍历左子树
        if(this.left != null){
            this.left.preOrder();
        }

        // 遍历右子树
        if(this.right != null){
            this.right.preOrder();
        }
    }
    
    // 中序遍历
    public void infixOrder(){
        // 遍历左子树
        if(this.left != null){
            this.left.infixOrder();
        }

        // 输出当前结点
        System.out.println(this);

        // 遍历右子树
        if(this.right != null){
            this.right.infixOrder();
        }
    } 

    // 后序遍历
    public void position(){
        // 遍历左子节点
        if(this.left != null){
            this.left.position();
        }

        // 遍历右子节点
        if(this.right != null){
            this.right.position();
        }

        // 输出当前结点
        System.out.println(this);
    }

    // 前序遍历查找
    /*
     * 
     * @param no 查找no
     * @return 如果找到就返回Node，如果没有找到就返回 null
    */
    public HeroNode preOrderSearch(int no){
        System.out.println("进入前序查找~");
        // 比较当前结点是不是要找的结点
        if(this.no == no){
            return this;
        }
        
        HeroNode resNode = null;
        // 1.判断当前结点的左子节是否为空，如果不为空，则递归前序查找
        // 2.如果左递归前序查找，找到结点，返回结点
        if(this.left != null){
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        // 1.左递归前序查找，找到结点，则返回，否则继续判断，
        // 2.判断当前的结点的右子结点是否为空，如果不空，则继续向右递归前序查找
        if(this.right != null){
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }

    // 中序遍历查找
    public HeroNode infixOrderSearch(int no){
        HeroNode resNode = null;
        // 1.判断当前结点的左子节是否为空，如果不为空，则递归中序查找
        if(this.left != null){
            resNode = this.left.infixOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        System.out.println("进入中序查找~");
        // 判断当前结点是否为查找结点，是返回，否则继续
        if(this.no == no){
            return this;
        }

        // 右递归中序查找
        if(this.right != null){
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    // 后续遍历查找
    public HeroNode positOrderSearch(int no){
        HeroNode resNode = null;
        // 左递归后续查找
        if(this.left != null){
            resNode = this.left.positOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        // 右递归后序查找
        if(this.right != null){
            resNode = this.right.positOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        System.out.println("进入后续查找~");
        // 判断当前结点是否为查找结点，是返回，否则继续
        if(this.no == no){
            return this;
        }

        return resNode;
    }
}
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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429

遍历线索化二叉树

1）说明：对前面的中序线索化的二叉树，进行遍历
2）分析：因为线素化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历

线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。

3）代码

/* file:ThreadedBinaryTreeDemo.java */
// 在 ThreadeBinaryTree类 添加代码

// 遍历线索化二叉树的方法
public void threadedList(){
    // 定义一个变量，临时存储当前遍历的结点，从root开始
    HeroNode node = root;
    while(node != null){
        // 循环遍历找到leftType = 1 的这个结点，第一个找到的就是 8 结点
        // 后面随着遍历而变化，因当leftType = 1 时，说明该结点是按照线索化
        // 处理后的有效结点
        while(node.getleftType() == 0){
            node = node.getLeft();
        }
        // 打印当前结点
        System.out.println(node);
        // 如果当前结点的右指针指向的是后继结点，就一直输出
        while(node.getRitghtType() == 1){
            node = node.getRight();
            System.out.println(node);
        }
        // 替换这个遍历的结点
        node = node.getRight();
    }
}

// 在 main方法中添加代码

// 当线索化二叉树后，再用原来的遍历方式会出现问题
// 因为原来的二叉树遍历是通过结点左右子节点为空来进行的
// 线索化后的二叉树将结点的左右指针都有值了
// threadeBinaryTree.infixOrder();
System.out.println("使用线索化的方式遍历 线索化二叉树");
threadeBinaryTree.threadedList();   // 8,3,10,1,14,6
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/598423