二叉排序树：BST（Binary Sort Tree) 对于二叉排序树的任一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前的值大，如果有相同的值，可以将该节点放在左子节点或右子节点（需要保证左子树的任意节点的值都比右子树任意节点的值小） 创建
public void addNode(BinaryNode node) { if (node == null) { return; } // 值得比较 if (this.value < node.value) { // 挂在右子树 if (this.right == null) { this.right = node; } else {// 递归添加 this.right.addNode(node); } } else {// 挂在左自子树 if (this.left == null) { this.left = node; } else { // this.left.addNode(node); } } }if (targetNode.left == null && targetNode.right == null) { if (parent.left != null && parent.left.value == value) { // 左子节点 parent.left = null; } else if (parent.right != null && parent.right.value == value) { // 右子节点 parent.right = null; } } if (targetNode.left != null) { if (parent.left.value == value) { parent.left = targetNode.left; } else if (parent.right.value == value) { parent.right = targetNode.left; }else { root=targetNode.left; } } else if (targetNode.right != null) {// 要删除的结点是右子节点 if (parent.left.value == value) { parent.left = targetNode.right; } else if (parent.right.value == value) { parent.right = targetNode.right; }else { root=targetNode.right; } } public int delRightTreeMin(BinaryNode node) { BinaryNode temp=node; //循环查找左节点,找到最小值 while(temp.left!=null) { temp=temp.left; } //temp此时为最小的节点 //删除最小节点 delNode(temp.value); return temp.value; } if (targetNode.left != null && targetNode.right != null) { // 有两个子树 int Min=delRightTreeMin(targetNode.right); targetNode.value=Min; }
附录
package 树; import java.lang.annotation.Target; public class 二叉排序树 { public static void main(String[] args) { // TODO 自动生成的方法存根 int[] arr = { 9, 5, 13, 4, 7, 10, 15, 3 };// { 7, 3, 10, 12, 5, 1, 9 };//9,5,13,4,7,10,15,3 BinarySortTree demo = new BinarySortTree(); // 循环添加结点到二叉排序树 for (int i = 0; i < arr.length; i++) { demo.add(new BinaryNode(arr[i])); } demo.infixOrder(); // 删除叶子节点 // demo.delNode(2); // demo.infixOrder(); demo.delNode(5); demo.infixOrder(); } } // 创建二叉排序树 class BinarySortTree { private BinaryNode root; // 添加 public void add(BinaryNode node) { if (root == null) { root = node; } else { root.addNode(node); } } // 遍历 public void infixOrder() { if (root != null) { root.infixOrder(); } else { System.out.println("空树不能遍历"); } } // 查找要删除的结点 public BinaryNode search(int value) { if (root == null) { return null; } else { return root.search(value); } } // 查找父节点 public BinaryNode searchparent(int value) { if (root == null) { return null; } else { return root.searchparent(value); } } //对有两个子树的删除的处理 返回最小节点的值 删除Node的最小节点 public int delRightTreeMin(BinaryNode node) { BinaryNode temp=node; //循环查找左节点,找到最小值 while(temp.left!=null) { temp=temp.left; } //temp此时为最小的节点 //删除最小节点 delNode(temp.value); return temp.value; } // 删除 public void delNode(int value) { if (root == null) { return; } else { // 1 找到需要删除的结点 BinaryNode targetNode = search(value); // 没有找到 if (targetNode == null) { return; } // 只有一个单独的结点 if (root.left == null && root.right == null) { root = null; return; } // 查找targetNode的父节点 BinaryNode parent = searchparent(value); // 要删除的结点是叶子节点 if (targetNode.left == null && targetNode.right == null) { if (parent.left != null && parent.left.value == value) { // 左子节点 parent.left = null; } else if (parent.right != null && parent.right.value == value) { // 右子节点 parent.right = null; } } else if (targetNode.left != null && targetNode.right != null) { // 有两个子树 int Min=delRightTreeMin(targetNode.right); targetNode.value=Min; } else { // 只有一个子树 // 如果要删除的结点有左子节点 if (targetNode.left != null) { if (parent.left.value == value) { parent.left = targetNode.left; } else if (parent.right.value == value) { parent.right = targetNode.left; }else { root=targetNode.left; } } else if (targetNode.right != null) {// 要删除的结点是右子节点 if (parent.left.value == value) { parent.left = targetNode.right; } else if (parent.right.value == value) { parent.right = targetNode.right; }else { root=targetNode.right; } } } } } } // 创建结点 class BinaryNode { int value; BinaryNode left; BinaryNode right; BinaryNode(int value) { this.value = value; } // 查找要删除的结点 public BinaryNode 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 BinaryNode 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) { return this.left.searchparent(value); } else if (value >= this.value && this.right != null) { return this.right.searchparent(value); } else { return null; // 么有找到父节点 } } } // 添加结点 public void addNode(BinaryNode node) { if (node == null) { return; } // 值得比较 if (this.value < node.value) { // 挂在右子树 if (this.right == null) { this.right = node; } else {// 递归添加 this.right.addNode(node); } } else {// 挂在左自子树 if (this.left == null) { this.left = node; } else { // this.left.addNode(node); } } } public void infixOrder() { if (this.left != null) { this.left.infixOrder(); } System.out.println(this.value); if (this.right != null) { this.right.infixOrder(); } } }