您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
二叉排序树节点的删除(图文)
第十三双眼睛2023-10-21【数据结构与算法】人已围观
简介二叉排序树节点的删除
二叉排序树节点的删除
package com.xingchen.day013; public class BinSortTreeDemo { public static void main(String[] args) { int[] arr = {7,3,10,12,5,1,9,0}; BinSortTree binSortTree = new BinSortTree(); for (int i = 0; i<arr.length; i++) { binSortTree.add(new Node(arr[i])); } binSortTree.infixOrder(); binSortTree.delNode(1); binSortTree.infixOrder(); } } class BinSortTree{ public Node root; public void add(Node node) { if (root == null) { root = node; } else { root.add(node); } } public void infixOrder() { if (root != null) { root.infixOrder(); } else { System.out.println("二叉排序树为空"); } } public Node search(int value) { if (root == null) { return null; } return root.search(value); } public Node searchParent(int value) { if (root == null) { return null; } else { return root.searchParent(value); } } //返回以node为根节点的二叉树中的最小值 public int deleteRightMin(Node node) { Node target = node; //循环查找左节点 while (target.left != null) { target = target.left; } //这时target就指向了最小节点 delNode(target.value); return target.value; } public void delNode(int value) { if (root == null) { return; } else { Node targetNode = search(value); // 如果没有找到,直接返回 if (targetNode == null) { return; } //如果只有一个节点 if (root.left == null && root.right == null) { root = null; return; } // Node 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 minValue = deleteRightMin(targetNode.right); targetNode.value = minValue; } else { if (targetNode.left != null) { if (parent != null) { if (parent.left.value == value) { parent.left = targetNode.left; } else { parent.right = targetNode.left; } } else { root = targetNode.left; } } else { if (parent != null) { if (parent.left.value == value) { parent.left = targetNode.right; } else { parent.right = targetNode.right; } } else { root = targetNode.right; } } } } } } class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } 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); } } } public void infixOrder() { if (this.left != null) { this.left.infixOrder(); } System.out.println(this); if (this.right != null) { this.right.infixOrder(); } } public Node search(int value) { if (value == this.value) { return this; } else if(value < this.value) { if (this.left != null) { return this.left.search(value); } else { return null; } } else { if (this.right != null) { return this.right.search(value); } else { return null; } } } 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; } } } @Override public String toString() { return "Node{" + "value=" + value + '}'; } } |
Tags:
很赞哦! ()
上一篇:二叉排序树的创建(图文)
下一篇:平衡二叉树(图文)