本文共 4841 字,大约阅读时间需要 16 分钟。
二叉排序树: BST: (Binary Sort(Search) Tree),对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。
特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点 创建二叉树添加节点构建排序树且遍历首先需要构建节点类,存放单个数据。节点类当中实现添加节点的方法和遍历方法。在二叉树类当中根据root节点进行添加和遍历。
class BSTree { private Node root; public void add(Node node) { if (root == null) { root = node; } else { root.add(node); } } public void DLR() { if (root != null) { root.DLR(); } else { System.out.println("树空,无法遍历"); } }}class Node { int value; Node left; 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 DLR() { System.out.println(this); if (this.left != null) { this.left.DLR(); } if (this.right != null) { this.right.DLR(); } } @Override public String toString() { return "Node[value = " + value + "]"; }}
对代码进行测试:使用上图的数组进行测试,在构建好了的二叉排序树如上图,其前序遍历的结果是:10,5,2,4,6,8,9,15
public class BST { public static void main(String[] args) { int[] arr = { 10, 5, 6, 2, 4, 8, 9, 15 }; BSTree bst = new BSTree(); for (int i = 0; i < arr.length; i++) { bst.add(new Node(arr[i])); } bst.DLR(); }}
运行记过如下图:
二叉树删除节点在删除节点的时候有三种情况:
代码实现:在node节点类当中添加俩个方法:
// 找到目标节点 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 { System.out.println("该节点没有父节点!"); return null; } } }
然后在BSTree类当中编写delete删除的方法。以及node节点类当中的方法进行调用,和一个查找最小值的方法,
public Node search(int value) { if (root == null) { System.out.println("空树"); return null; } else { return root.search(value); } } public Node searchParent(int value) { if (root == null) { return null; } else { System.out.println("父节点:" + root.searchParent(value)); return root.searchParent(value); } } public void delete(int value) { if (root == null) { return; } else { Node target = search(value); // 是否找到目标节点 if (target == null) { return; } // 只有一个节点,直接删除这个节点 if (root.left == null && root.right == null) { root = null; } // 查找目标节点的父节点 Node targetParent = searchParent(value); // 删叶子节点 if (target.left == null && target.right == null) { // 判断目标节点是父节点的左右? if (targetParent.left != null && targetParent.left.value == value) { targetParent.left = null; } if (targetParent.right != null && targetParent.right.value == value) { targetParent.right = null; } } else if (target.left != null && target.right != null) { int minValue = deleteMin(target.right); target.value = minValue; } else { // 目标节点有左子树 if (target.left != null) { // 目标节点是父节点的左右? if (targetParent != null) { if (targetParent.left.value == value) { targetParent.left = target.left; } else { targetParent.right = target.left; } } else { root = target.left; } } else { if (targetParent != null) { if (targetParent.left.value == value) { targetParent.left = target.right; } else { targetParent.right = target.right; } } else { root = target.right; } } } } } public int deleteMin(Node node) { Node targetNode = node; // 循环查找左子树,会找到最小值 while (targetNode.left != null) { targetNode = targetNode.left; // targetnode指向最小的值 } delete(targetNode.value); return targetNode.value; }
进行测试:分别删除不同情况的节点:
public static void main(String[] args) { int[] arr = { 10, 5, 6, 2, 4, 8, 9, 15 }; BSTree bst = new BSTree(); for (int i = 0; i < arr.length; i++) { bst.add(new Node(arr[i])); } // bst.searchParent(8); // bst.search(10); bst.DLR(); System.out.println("删除 :"); bst.delete(4); // 删叶子节点 => 10 5 2 6 8 9 15 bst.delete(6); // 删只有一棵子树的节点 10 5 2 8 9 15 bst.delete(5);// 删除有两棵子树的节点 10 8 2 9 15 bst.DLR(); }
如下图所示:
转载地址:http://igmzi.baihongyu.com/