二叉排序树

二叉排序树

{27,8,9,14,2,33,18};

public class BinarySortTree { public static void main(String[] args) { int[] myNum= {27,8,9,14,2,33,18}; Node root = new Node(27); for(int i=1;i<myNum.length;i++) { binarySortTree(root,myNum[i]); } zhongSort(root); } //建立二叉排序树 public static void binarySortTree(Node myNode,int value) { if(value <= myNode.num) { if(myNode.getLeft() == null) { Node mid = new Node(value); myNode.setLeft(mid); return; }else { binarySortTree(myNode.getLeft(),value); } } if(value > myNode.num) { if(myNode.getRight() == null) { Node mid = new Node(value); myNode.setRight(mid); return; }else { binarySortTree(myNode.getRight(),value); } } } //中序遍历二叉树，是数据从小到大输出 public static void zhongSort(Node node) { if(node.getLeft()!=null) { zhongSort(node.getLeft()); } System.out.print(node.num + " "); if(node.getRight()!=null) { zhongSort(node.getRight()); } } } class Node{ int num; Node left; Node right; public Node(int num) { super(); this.num = num; } public int getNum() { return num; } public void setNum(int num) { this.num = num; } 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 [num=" + num + "]"; } }

二叉排序树删除节点

三种情况：

删除没有子节点的节点：先找到要删除的节点，再找到要删除节点的父节点parent，判断要删除节点是父节点的左子节点还是右子节点，如果是左子节点，则parent.left=null;如果是右子节点，则parent.right=null;删除有一个子节点的节点:先找到要删除的节点，再使用辅助节点标识要删除节点的子节点child,再找到要删除节点的父节点parent,判断要删除节点是父节点的左子节点还是右子节点，如果是左子节点，则parent.left=child;如果是右子节点，则parent.right=child;删除有两个子节点的节点：先找到要删除的节点，再找到要删除节点的左子树的最大值的节点或者右子树的最小节点，替代要删除的节点。

代码实现（在上述代码的基础上实现）

public class BinarySortTree { public static void main(String[] args) { int[] myNum= {27,8,9,14,2,33,18}; Node root = new Node(27); //建立二叉排序树 for(int i=1;i<myNum.length;i++) { binarySortTree(root,myNum[i]); } //输入要删除的结点的值 //情况1：18 delNode(root,18); //情况2：9 //delNode(root,9); //情况3：8 //delNode(root,8); zhongSort(root); } //建立二叉排序树 public static void binarySortTree(Node myNode,int value) { if(value <= myNode.num) { if(myNode.getLeft() == null) { Node mid = new Node(value); myNode.setLeft(mid); return; }else { binarySortTree(myNode.getLeft(),value); } } if(value > myNode.num) { if(myNode.getRight() == null) { Node mid = new Node(value); myNode.setRight(mid); return; }else { binarySortTree(myNode.getRight(),value); } } } //删除节点value public static void delNode(Node root,int value) { //查找要删除的节点 Node getThis = searchNode(root,value); if(getThis == null) { System.out.println("没有该节点"); }else { System.out.println(getThis); //查看要删除节点的子结点的情况 //1.删除不含子节点的节点。 //例：18 if(getThis.getLeft() == null && getThis.getRight() == null) { //查找父节点 Node getParent = searchNodeParent(root,value); if(getParent == null) { System.out.println("只有这一个节点"); }else if(getParent.getLeft() == getThis) { getParent.setLeft(null); }else { getParent.setRight(null); } } //3.删除含两个子节点的节点 //例：8 else if(getThis.getLeft() != null && getThis.getRight() != null) { //查找右子树中最小的节点 Node mixNode = SearchMix(getThis.getRight()); System.out.println(mixNode); int mix = mixNode.num; //删除原最小节点 delNode(getThis,mix); //将原最小值填入 getThis.num = mix; } //2.删除含一个子节点的节点 //例：9 else { if(getThis.getLeft() != null) { //找到其左子节点 Node thisLeft = getThis.getLeft(); //找到其父节点 Node getParent = searchNodeParent(root,value); if(getParent == null) { System.out.println("删除后仅剩节点"+thisLeft); }else if(getParent.getLeft() == getThis) { getParent.setLeft(thisLeft); }else { getParent.setRight(thisLeft); } }else if(getThis.getRight() != null) { //找到其右子节点 Node thisRight = getThis.getRight(); //找到其父节点 Node getParent = searchNodeParent(root,value); if(getParent == null) { System.out.println("删除后仅剩节点"+thisRight); }else if(getParent.getLeft() == getThis) { getParent.setLeft(thisRight); }else { getParent.setRight(thisRight); } } } } } //查找要删除的节点 public static Node searchNode(Node node,int value) { if(node.num == value) { return node; }else if(node.num > value){//左递归 if(node.getLeft() ==null) {//没有该节点 return null; }else { return searchNode(node.getLeft(),value); } }else{ if(node.getRight() == null) {//没有该节点 return null; }else { return searchNode(node.getRight(),value); } } } //查找父节点,flag=0为左子节点，flag=1为右子节点 public static Node searchNodeParent(Node node,int value) { if(node.getLeft()!=null&&node.getLeft().num == value) { return node; }else if(node.getRight()!=null&&node.getRight().num == value) { return node; }else { if(node.getLeft() != null &&node.num > value) {//左递归 return searchNodeParent(node.getLeft(),value); }else if(node.getRight() != null &&node.num < value) { return searchNodeParent(node.getRight(),value); }else { return null; } } } //查找子树中值最小的节点 public static Node SearchMix(Node node) { if(node.getLeft()!=null) { return SearchMix(node.getLeft()); }else { return node; } } //中序遍历二叉树，是数据从小到大输出 public static void zhongSort(Node node) { if(node.getLeft()!=null) { zhongSort(node.getLeft()); } System.out.print(node.num + " "); if(node.getRight()!=null) { zhongSort(node.getRight()); } } } class Node{ int num; Node left; Node right; public Node(int num) { super(); this.num = num; } public int getNum() { return num; } public void setNum(int num) { this.num = num; } 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 [num=" + num + "]"; } }