二叉树增删改查操作

数据结构
字数统计: 2.3k   |   阅读时长≈ 11 分钟

问题描述

通过代码实现下面二叉树的构建，并且实现二叉树的增删改查操作。
二叉树

代码实现

定义二叉树结构：

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
/**
 * 二叉树结构
 */
public class TreeNode {
  /** 数据 */
	private char data;
  /** 左子树节点 */
	private TreeNode left;
  /** 右子树节点 */
	private TreeNode right;

	public TreeNode() {
		this.data = ' ';
		this.left = null;
		this.right = null;
	}

	public TreeNode(char data, TreeNode left, TreeNode right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}

	public void setData(char data) {
		this.data = data;
	}

	public char getData() {
		return data;
	}

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

	public TreeNode getLeft() {
		return left;
	}

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

	public TreeNode getRight() {
		return right;
	}
}

二叉树操作类：

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
/**
* 二叉树相关操作，增删改查
*/
public class BinaryTreeOptional {
	// 前序遍历 根左右  
	// 时间复杂度O(2n) => O(n)
	public void pre(TreeNode root) {
		if (root != null) {
			print(root);
			if (root.getLeft() != null) {
				pre(root.getLeft());
			}
			if (root.getRight() != null) {
				pre(root.getRight());				
			}
		}
	}

	// 中序遍历 左根右
	public void mid(TreeNode root) {
		if(root != null) {
			if(root.getLeft() != null) {
				mid(root.getLeft());
			}
			print(root);
			if (root.getRight() != null) {
				mid(root.getRight());
			}
		}
	}

	// 后序遍历 左右根
	public void post(TreeNode root) {
		if(root != null) {
			if(root.getLeft() != null) {
				post(root.getLeft());
			}
			if(root.getRight() != null) {
				post(root.getRight());
			}
			print(root);
		}
	}

	// 添加节点
	public void add(TreeNode root, TreeNode node) {
		Assert.notNull(root, "二叉树不能为空");
		Assert.notNull(node, "添加的节点不能为空");
		if(node.getData() <= root.getData()) {
			if(root.getLeft() == null) {
				root.setLeft(node);
			} else {
				add(root.getLeft(),node);
			}
		} else {
			if(root.getRight() == null) {
				root.setRight(node);
			} else {
				add(root.getRight(),node);
			}
		}

	}

	// 删除节点
	public void remove(TreeNode root,TreeNode rmNode) {
		if (rmNode.getLeft() == null && rmNode.getRight() == null) {
			rmLeafNode(root,rmNode);
		} else if (rmNode.getLeft() == null && rmNode.getRight() != null) {
			rmNodeWithRightNode(root,rmNode);
		} else if (rmNode.getLeft() != null && rmNode.getRight() == null) {
			rmNodeWithLeftNode(root,rmNode);
		} else if (rmNode.getLeft() != null && rmNode.getRight() != null) {
			rmNode(root,rmNode);
		}
		
	}

	// 寻找当前节点的父节点
	private TreeNode getParentNode(TreeNode root,TreeNode node) {
		TreeNode treeNode = root;
		if(root != null && root.getLeft() != null && root.getLeft().getData() == node.getData()) {
			System.out.println("left = " + root);
			return treeNode;
		}
		if(root != null && root.getRight() != null && root.getRight().getData() == node.getData()) {
			System.out.println("Right = " + root.getData());
			return treeNode;
		}
		return root.getData() >= node.getData() ? getParentNode(root.getLeft(), node) : getParentNode(root.getRight(), node);
	}

	// 删除叶子节点
	private boolean rmLeafNode(TreeNode root,TreeNode rmNode) {

		TreeNode parentNode = getParentNode(root,rmNode);
		if (parentNode.getLeft() != null && parentNode.getLeft().getData() == rmNode.getData()) {
			parentNode.setLeft(null);
			return true;
		}
		if (parentNode.getRight() != null && parentNode.getRight().getData() == rmNode.getData()) {
			parentNode.setRight(null);
			return true;
		}
		return false;
	}

	// 删除节点，该节点只有左子树有叶子节点，右子树没有节点
	private boolean rmNodeWithLeftNode(TreeNode root, TreeNode rmNode) {
		TreeNode leftNode = rmNode.getLeft();
		rmNode.setData(leftNode.getData());
		rmNode.setLeft(null);
		rmNode.setRight(null);
		return true;
	}

	// 删除节点，该节点只有右子树有叶子节点，左子树为空
	private boolean rmNodeWithRightNode(TreeNode root, TreeNode rmNode) {
		TreeNode rightNode = rmNode.getRight();
		rmNode.setData(rightNode.getData());
		rmNode.setLeft(null);
		rmNode.setRight(null);
		return true;
	}

	// 删除节点，该节点既有左子树又有右子树
	private boolean rmNode(TreeNode root, TreeNode rmNode) {
		TreeNode parentNode = getParentNode(root, rmNode);
		TreeNode firstMaxNode = findFirstMax(rmNode);
		TreeNode firstMaxParentNode = getParentNode(rmNode, firstMaxNode);
		if (parentNode.getLeft().getData() == rmNode.getData()) {
			parentNode.setLeft(firstMaxNode);
			firstMaxNode.setLeft(rmNode.getLeft());
			firstMaxNode.setRight(rmNode.getRight());
			firstMaxParentNode.setLeft(null);
			return true;
		}
		if (parentNode.getRight().getData() == rmNode.getData()) {
			parentNode.setRight(firstMaxNode);
			firstMaxNode.setLeft(rmNode.getLeft());
			firstMaxNode.setRight(rmNode.getRight());
			firstMaxParentNode.setLeft(null);
			return true;
		}
		return false;
	}
	// 添加节点
	public void add(TreeNode root, TreeNode node) {
		Assert.notNull(root, "二叉树不能为空");
		Assert.notNull(node, "添加的节点不能为空");
		if(node.getData() <= root.getData()) {
			if(root.getLeft() == null) {
				root.setLeft(node);
			} else {
				add(root.getLeft(),node);
			}
		} else {
			if(root.getRight() == null) {
				root.setRight(node);
			} else {
				add(root.getRight(),node);
			}
		}

	}

	// 寻找当前节点的父节点
	public TreeNode getParentNode(TreeNode root,TreeNode node) {
		TreeNode treeNode = root;
		if(root != null && root.getLeft() != null && root.getLeft().getData() == node.getData()) {
			System.out.println("left = " + root);
			return treeNode;
		}
		if(root != null && root.getRight() != null && root.getRight().getData() == node.getData()) {
			System.out.println("Right = " + root.getData());
			return treeNode;
		}
		return root.getData() >= node.getData() ? getParentNode(root.getLeft(), node) : getParentNode(root.getRight(), node);
	}
    /**
     * 层次遍历
     * @param root
     */
    private void levelTraverse(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        Queue<TreeNode> tree = new LinkedList<>();
        tree.add(root);
        while (!tree.isEmpty()) {
            TreeNode remove = tree.remove();
            list.add(remove);
            if (remove.getLeft() != null) {
                tree.add(remove.getLeft());
            }
            if (remove.getRight() != null) {
                tree.add(remove.getRight());
            }
        }
        System.out.println(list);
    }
	// 删除叶子节点
	public boolean rmLeafNode(TreeNode root,TreeNode rmNode) {

		TreeNode parentNode = getParentNode(root,rmNode);
		if (parentNode.getLeft() != null && parentNode.getLeft().getData() == rmNode.getData()) {
			parentNode.setLeft(null);
			return true;
		}
		if (parentNode.getRight() != null && parentNode.getRight().getData() == rmNode.getData()) {
			parentNode.setRight(null);
			return true;
		}
		return false;
	}

	// 找到第一个大于要删除节点的那个节点
	private TreeNode findFirstMax(TreeNode rmNode) {
		TreeNode firstMaxNode = rmNode.getRight();
		while(firstMaxNode != null && firstMaxNode.getLeft() != null) {
			if(firstMaxNode.getLeft().getData() < firstMaxNode.getData()) {
				firstMaxNode = firstMaxNode.getLeft();
			}
		}
		return firstMaxNode;
	}

	public void print(TreeNode node) {
		if (node != null) {
			System.out.print(node.getData());	
		}
	}
}

测试主类：

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
public class TreeMain {
	public static void main(String[] args) {
		TreeNode node_D = new TreeNode('D',null,null);
		TreeNode node_F = new TreeNode('F',null,null);
		TreeNode node_G = new TreeNode('G',node_F,null);
		TreeNode node_B = new TreeNode('B',null,null);
		TreeNode node_L = new TreeNode('L',null,null);
		TreeNode node_M = new TreeNode('M',node_L,null);
		TreeNode node_A = new TreeNode('A',null,node_B);
		TreeNode node_C = new TreeNode('C',node_A,node_D);
		TreeNode node_E = new TreeNode('E',node_C,node_G);
		TreeNode root_H = new TreeNode('H',node_E,node_M);

		BinaryTreeOptional treeOption = new BinaryTreeOptional();
		// 前序遍历
		System.out.print("前序遍历：");
		treeOption.pre(root_H);
		System.out.println();
		// 中序遍历
		System.out.print("中序遍历：");
		treeOption.mid(root_H);
		System.out.println();
		// 后序遍历
		System.out.print("后序遍历: ");
		treeOption.post(root_H);
		System.out.println();
		// 添加节点
		TreeNode node_K = new TreeNode('K',null,null);
		TreeNode node_I = new TreeNode('I',null,null);
		TreeNode node_N = new TreeNode('N',null,null);
		TreeNode node_W = new TreeNode('W',node_N,null);
		TreeNode node_X = new TreeNode('X',null,null);
		TreeNode node_Y = new TreeNode('Y',null,null);
		System.out.println("添加节点: " + node_K.getData() + "," + node_I.getData());
		treeOption.add(root_H, node_K);
		treeOption.add(root_H, node_W);
		treeOption.add(root_H, node_X);
		treeOption.add(root_H, node_Y);
		System.out.print("添加节点后的前序遍历是：");
		treeOption.mid(root_H);
		System.out.println();
		// 删除叶子节点
		// treeOption.remove(root_H, node_G);
		// System.out.print("前序遍历：");
		// treeOption.pre(root_H);
		// System.out.println();

		TreeNode s = treeOption.findFirstMax(node_E);
		System.out.println("第一个比根节点大的数： " + s.getData());
		treeOption.rmLeafNode(root_H, node_G);
		System.out.print("前序遍历：");
		treeOption.pre(root_H);
		System.out.println();

		// 删除中间节点
		treeOption.remove(root_H, node_M);
		System.out.print("删除中间节点后的前序遍历是：");
		treeOption.pre(root_H);
		System.out.println();
		System.out.print("删除中间节点后的中序序遍历是：");
		treeOption.mid(root_H);
	}
}

在删除二叉树的节点是需要注意的是，二叉树节点删除有四种情况，分别是：

  1. 要删除的节点是叶子节点
  2. 要删除的节点左子树为空，右子树不为空
  3. 要删除的节点左子树不为空，右子树为空
  4. 要删除的节点左子树不为空，右子树也不为空

第一种情况比较简单，直接删除节点即可。如下图，如果删除叶子节点B，则直接将节点A的右子树设置为null

1
A.right = null;

删除叶子节点

删除叶子节点代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 删除叶子节点
private boolean rmLeafNode(TreeNode root,TreeNode rmNode) {

	TreeNode parentNode = getParentNode(root,rmNode);
	if (parentNode.getLeft() != null && parentNode.getLeft().getData() == rmNode.getData()) {
		parentNode.setLeft(null);
		return true;
	}
	if (parentNode.getRight() != null && parentNode.getRight().getData() == rmNode.getData()) {
		parentNode.setRight(null);
		return true;
	}
	return false;
}

第二种：“要删除的节点左子树为空，右子树不为空”。

删除节点G，因为节点G只有右子树节点，所以删除G节点时，需要将G的右节点F设置到G节点位置，删除G节点。

1
2
E.right = G.right;
G.right = null;

要删除的节点左子树为空，右子树不为空

删除节点G完整代码如下：

1
2
3
4
5
6
7
8
// 删除节点，该节点只有右子树有叶子节点，左子树为空
private boolean rmNodeWithRightNode(TreeNode root, TreeNode rmNode) {
	TreeNode rightNode = rmNode.getRight();
	rmNode.setData(rightNode.getData());
	rmNode.setLeft(null);
	rmNode.setRight(null);
	return true;
}

第三种：“要删除的节点左子树不为空，右子树为空”

例如删除节点L，删除步骤和第二种情况步骤基本一样；将L节点的左子树与K节点的连接断开，并且将M节点（L节点的父节点）的左子树节点设置为K，即可删除L节点。

要删除的节点左子树不为空，右子树为空

删除节点完整代码：

1
2
3
4
5
6
7
8
// 删除节点，该节点只有左子树有叶子节点，右子树没有节点
private boolean rmNodeWithLeftNode(TreeNode root, TreeNode rmNode) {
	TreeNode leftNode = rmNode.getLeft();
	rmNode.setData(leftNode.getData());
	rmNode.setLeft(null);
	rmNode.setRight(null);
	return true;
}

第四种：“要删除的节点左子树和右子树都不为空”

例如删除节点M，因为节点M既有左子树，又有右子树。所以在删除节点M的时候需要在M节点的右子树下找到地第一个大于M节点的节点，即N节点。然后将N节点放在M节点的位置，删除M节点。

左子树不为空，右子树不为空

删除代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 删除节点，该节点既有左子树又有右子树
private boolean rmNode(TreeNode root, TreeNode rmNode) {
	TreeNode parentNode = getParentNode(root, rmNode);
	TreeNode firstMaxNode = findFirstMax(rmNode);
	TreeNode firstMaxParentNode = getParentNode(rmNode, firstMaxNode);
	if (parentNode.getLeft().getData() == rmNode.getData()) {
		parentNode.setLeft(firstMaxNode);
		firstMaxNode.setLeft(rmNode.getLeft());
		firstMaxNode.setRight(rmNode.getRight());
		firstMaxParentNode.setLeft(null);
		return true;
	}
	if (parentNode.getRight().getData() == rmNode.getData()) {
		parentNode.setRight(firstMaxNode);
		firstMaxNode.setLeft(rmNode.getLeft());
		firstMaxNode.setRight(rmNode.getRight());
		firstMaxParentNode.setLeft(null);
		return true;
	}
	return false;
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

请我喝杯咖啡吧~

支付宝
微信