二叉排序树结合了数组和链表的优点
查询和添加都很快相对来说数组的头插需要往后移动整个数组而链表查找数据则需要迭代
但是二叉排序树截然不同
二叉排序树相同的数据对应的二叉排序树不一样
就是一样的数据排序方式是不一样的，二叉排序树的中序遍历得到的值都是一个递增的序列
假如说中序添加二叉排序树：取得一个值作为根结点，那么将要插入的数据和根结点进行对比
如果数据要比它小那就把数据放到结点的左子树如果左子树有数据那么继续和左子树进行比较
再决定放到左子树的左边还是右边
创建一个二叉排序树：
先创建一个树的结点
public class Node {
private int value;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
}
public void add(Node node){
if(node == null) return;//判断结点是否为空 作为递归的结束条件
if(node.valuethis.value){
return this.right.ParentSelect(val);
}
//如果左右子树判断完都没找到那就返回空
//还有根结点也是没有父结点的
return null;
}
public int getValue() {return value;}
public void setValue(int value) {this.value = value;}
public Node getLeft() {return left;}
public void setLeft(Node left) {this.left = left;}
public Node getRight() {return right;}
public void setRight(Node right) {this.right = right;}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
在创建一个二叉排序树：
public class BinaryTree {
private Node root;
public BinaryTree() {
}
public void setRoot(Node root) {
this.root = root;
}
public Node SelectVal(int val){
if(this.root==null){
return null;
}else{
return this.root.SelectVal(val);
}
}
public Node ParentSelect(int val){
if(this.root==null) return null;
return this.root.ParentSelect(val);
}
public void add(Node node){
if(this.root==null) return;
this.root.add(node);
}
public void InfixSelect(){
if(this.root==null) return;
this.root.preSelect();
}
public int FindMinNode(Node node){
Node target = node;//创建一个迭代结点
while(target.getLeft()!=null){//循环迭代找到一棵树的最左结点叶子结点
target=target.getLeft();
}
//找到了结点需要把这个结点的值赋值到下面方法要删除的值 那这个结点就需要删除了
this.DelNode(target.getValue());
//返回该结点的值
return target.getValue();
}
public void DelNode(int val){
if(this.root==null) {//先判断根结点是否为空 防止出错
return;
}
//拿到这个val值在树中的结点
Node target = this.SelectVal(val);
//判断这个结点是否为空
if(target==null){
return;
}else if(this.root.getLeft()==null&&this.root.getRight()==null){
this.root=null;
return;
}
Node ParentNode = this.ParentSelect(val);
//到这里判断他是否为叶子结点 没有左右子树
if(target.getLeft()==null&&target.getRight()==null){
if(ParentNode.getLeft()!=null&&ParentNode.getLeft()==target){
//如果他是叶子结点那就判断这个结点是他父结点的左或右结点
//如果父结点的左子树有东西并且==target这个结点那就把它父结点的左子树置为空即可删除成功
ParentNode.setLeft(null);
}else if (ParentNode.getRight()!=null&&ParentNode.getRight()==target){
//想对如果是父结点的右子树是它那就把父结点的右子树置为空即可
ParentNode.setRight(null);
}
}else if(target.getLeft()!=null&&target.getRight()!=null){//如果该结点的左右子树都存在那就删除
//那就找到他的右子树的最小值 来替代这个结点即可完成删除
int Min = this.FindMinNode(target.getRight());//寻找子树左子树最小值的方法，注意传入的是该结点的右子树
target.setValue(Min);//将最小结点的值赋值给这个结点即可完成替换
}else{
if(target.getLeft()!=null){//判断左子树不为空说明有左子树
if(ParentNode!=null) {//判断是否为根结点 根结点是没有父结点的直接把根结点的左子树赋值给根结点就可以了
if(ParentNode.getLeft().getValue()==val){//判断父结点的左子树的值等于这个值吗 如果等于 说明这个结点是一个左子树
ParentNode.setLeft(target.getLeft());//那就把父结点的左子树改为要删除的结点的左子树
}else if(ParentNode.getRight().getValue()==val){//如果这个结点是它父结点的右子树 就把父结点的右子树设置为这个结点的左子树
ParentNode.setRight(target.getLeft());
}
}else{
this.root=target.getLeft();
}
}else if(target.getRight()!=null){//同上 如果这个结点只有一个右子树 那就判断这个结点是父结点的左还是右结点 再把父结点的左或右结点设置为该结点的右子树即可
if(ParentNode!=null) {
if(ParentNode.getLeft().getValue()==val){
ParentNode.setLeft(target.getRight());
}else if(ParentNode.getRight().getValue()==val){
ParentNode.setRight(target.getRight());
}
}else{
this.root=target.getRight();
}
}
}
}
}
