目录
一：需求分析
三：二叉排序树的介绍
特点：二叉排序树的中序遍历是
递增
的
3.1 二叉排序树的生成
左小右大一次插入就行
//添加结点
public void add(N node) {
if(node == null) {
return;
}
if(node.value < this.value) {
if(this.left == null) {
this.left = node;
}else {
this.left.add(node);
}
}else {
if(this.right == null) {
this.right = node;
}else {
this.right.add(node);
}
}
}
3.2 二叉排序树的删除
任务：找到要删除的目标结点和目标的父亲结点
//目标结点
public N selectByVal(int val) {
if(this.value == val) {
return this;
}else if(val < this.value) {
if(this.left == null) {
return null;
}else {
return this.left.selectByVal(val);
}
}else {
if(this.right == null) {
return null;
}else {
return this.right.selectByVal(val);
}
}
}
//父节点
public N selectByParent(int val) {
if(this.left != null && this.left.value == val || this.right != null && this.right.value == val) {
return this;
}else {
if(val < this.value && this.left != null) {
return this.left.selectByParent(val);
}else if(val > this.value && this.right != null) {
return this.right.selectByParent(val);
}else {
return null;
}
}
}
3.2.1 删除叶子结点
删除叶子节点需要判断是父亲结点的左结点还是右结点
N pn = target.selectByParent(val);
if(target.getLeft() == null && target.getRight() == null) {
if(pn.getLeft() != null && pn.getLeft().getValue() == val) {
pn.setLeft(null);
}else if(pn.getRight() != null && pn.getRight().getValue() == val) {
pn.setRight(null);
}
3.2.2 删除带有双亲结点的结点
需要找到左子树的最大值，右子树的最小值
else if(target .getLeft() != null && target.getRight() != null) {
N n = rightTreeMin(target.getRight());
target.setValue(n.getValue());
target.setRight(null);
}
3.3.3 删除只带有左子树的结点
需要考虑父亲结点的是否为空
if(target.getLeft() != null) {
if(pn != null) {
if(pn.getLeft().getValue() == val) {
pn.setLeft(target.getLeft());
}
}else {
root = target.getLeft();
}
}
3.3.4 删除只带有右子树的结点
需要考虑父亲结点的是否为空
else if(target.getRight() != null){
if(pn != null) {
if(pn.getRight().getValue() == val) {
pn.setRight(target.getRight());
}
}else {
root = target.getRight();
}
}
四：二叉排序树的全部代码展示
package tree;
public class N {
private int value;
private N left;
private N right;
public N(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public N getLeft() {
return left;
}
public void setLeft(N left) {
this.left = left;
}
public N getRight() {
return right;
}
public void setRight(N right) {
this.right = right;
}
@Override
public String toString() {
return "N [value=" + value + "]";
}
//添加结点
public void add(N node) {
if(node == null) {
return;
}
if(node.value < this.value) {
if(this.left == null) {
this.left = node;
}else {
this.left.add(node);
}
}else {
if(this.right == null) {
this.right = node;
}else {
this.right.add(node);
}
}
}
//中序遍历
public void indexSelect() {
if(this.left != null) {
this.left.indexSelect();
}
System.out.println(this);
if(this.right != null) {
this.right.indexSelect();
}
}
//目标结点
public N selectByVal(int val) {
if(this.value == val) {
return this;
}else if(val < this.value) {
if(this.left == null) {
return null;
}else {
return this.left.selectByVal(val);
}
}else {
if(this.right == null) {
return null;
}else {
return this.right.selectByVal(val);
}
}
}
//父节点
public N selectByParent(int val) {
if(this.left != null && this.left.value == val || this.right != null && this.right.value == val) {
return this;
}else {
if(val < this.value && this.left != null) {
return this.left.selectByParent(val);
}else if(val > this.value && this.right != null) {
return this.right.selectByParent(val);
}else {
return null;
}
}
}
}
package tree;
public class T {
private N root;
//查询
public N selelctByVal(int val) {
if(root == null) {
return null;
}else {
return root.selectByVal(val);
}
}
//查询父节点
public N selectByParent(int val) {
if(root == null) {
return null;
}else {
return root.selectByParent(val);
}
}
public void add(N node) {
if(root == null) {
root = node;
}else {
root.add(node);
}
}
//中序遍历
public void indexSelect() {
if(root != null) {
root.indexSelect();
}else {
System.out.print("空树...");
}
}
//删除结点
public N rightTreeMin(N node) {
N target = node;
while(target.getLeft() != null) {
target = target.getLeft();
}
return target;
}
public void delNode(int val) {
if(root == null || root.getLeft() == null && root.getRight() == null) {
return;
}else {
N target = selelctByVal(val);
if(target == null) {
return;
}
N pn = target.selectByParent(val);
if(target.getLeft() == null && target.getRight() == null) {
if(pn.getLeft() != null && pn.getLeft().getValue() == val) {
pn.setLeft(null);
}else if(pn.getRight() != null && pn.getRight().getValue() == val) {
pn.setRight(null);
}
}else if(target .getLeft() != null && target.getRight() != null) {
N n = rightTreeMin(target.getRight());
target.setValue(n.getValue());
target.setRight(null);
}else {
//左子树
if(target.getLeft() != null) {
if(pn != null) {
if(pn.getLeft().getValue() == val) {
pn.setLeft(target.getLeft());
}
}else {
root = target.getLeft();
}
}
//右子树
else if(target.getRight() != null){
if(pn != null) {
if(pn.getRight().getValue() == val) {
pn.setRight(target.getRight());
}
}else {
root = target.getRight();
}
}
}
}
}
}
package tree;
public class Test {
public static void main(String[] args) {
int[] array = {7,3,10,12,5,1,9,2};
T t = new T();
for(int i = 0; i < array.length; i++){
t.add(new N(array[i]));
}
t.indexSelect();
t.delNode(3);
System.out.println("排序树的删除--------------------");
t.indexSelect();
}
}
版权声明：本文为qq_56127002原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。