11.0 二叉排序树

二叉排序树

二叉排序树:BST: (Binary Sort(Search)Tree),对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。特别说明:如果有相同的值，可以将该节点放在左子节点或右子节点.比如针对前面的数据(7,3,10,12,5,1,9)，对应的二叉排序树为: 构建二叉排序代码如下

递归添加节点

//递归添加节点 public void add(Node 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); } } }

二叉排序树删除节点的三种情况 1.删除叶子节点思路 ⑴需求先去找到要删除的结点targetNode (2)找到targetNode的父结点parent (3）确定targetNode是parent的左子结点还是右子结点 (4）根据前面的情况来对应删除 左子结点parent.left = null 右子结点parent.right = null;

代码如下： 查找删除节点代码

//查找要删除的点 public Node search(int value){ if (this.value == value){ return this; } else if (value < this.value){ if (this.left == null){ return null; } return this.left.search(value); } else { if (this.right == null){ return null; } return this.right.search(value); } }

删除删除节点父节点代码：

//查找要删除节点的父节点 public Node searchParent(int value){ if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)){ return this; } else if (value < this.value && this.left != null){ return this.left.searchParent(value); } else if (value >= this.value && this.right != null){ return this.right.searchParent(value); } else { return null; } } //第一种情况如果删除的节点是叶子节点 if (targetNode.right == null && targetNode.left == null){ if (parentNode.left != null && parentNode.left.value == value){ parentNode.left = null; } else if (parentNode.right != null && parentNode.right.value == value){ parentNode.right = null; } }

3.删除有两颗子树的节点思路 1)需求先去找到要删除的结点targetNode (2)找到targetNode的父结点parent (3）从targetNode的右子树找到最小的结点 (4)用一个临时变量，将最小结点的值保存temp = 11 (5）珊除该最小结点 (6) targetNode.value = temp

代码如下

//第三种情况有二棵子树 else if (targetNode.right != null && targetNode.left != null){ int minVal = delLeftTreeMax(targetNode.left); targetNode.value = minVal; } //删除这个节点左子树最大的值(左子树) public int delLeftTreeMax(Node node){ Node target = node; while (target.right != null){ target = target.right; } deNode(target.value); return target.value; }

3.删除只有一颗子树的节点 1)需求先去找到要删除的结点targetNode (2)找到targetNode的父结点parent (3)确定targetNode的子结点是左子结点还是右子结点 (4) targetNode是parent的左子结点还是右子结点 (5)如果targetNode有左子结点 5.1如果targetNode是parent的左子结点 parent.left = targetNode.left; 5.2如果targetNode是parent的右子结点 parent.right = targetNode.left; (6)如果targetNode有右子结点 6.1如果targetNode是parent的左子结点 parent.left = targetNode.right; 6.2如果targetNode是parent的右子结点 parent.right = targetNode.right

代码如下

//第二种情况只有一棵子树 else { //左子树不为空 if (targetNode.left != null){ if (parentNode != null){ if (parentNode.left.value == value){ parentNode.left = targetNode.left; } else { parentNode.right = targetNode.left; } } else { root = targetNode.left; } } else if (targetNode.right != null){ if (parentNode != null){ if (parentNode.left.value == value){ parentNode.left = targetNode.right; } else { parentNode.right = targetNode.right; } } else { root = targetNode.right; } } }

ps：【源码自取，点击即可】 ps：以上笔记均来自尚硅谷韩顺平老师《Java数据结构与java算法》