二叉搜索树的实例和java

我正在尝试使用Cormen的伪代码实现BST算法但仍存在问题。

这是我的节点代码：

public class Node { Node left; Node right; int value; Node(int value){ this.value = value; this.left = null; this.right = null; } } 

而对于Bstree：

 public class Btree { Node root; Btree(){ this.root = null; } public static void inorderWalk(Node n){ if(n != null){ inorderWalk(n.left); System.out.print(n.value + " "); inorderWalk(n.right); } } public static Node getParent(Btree t, Node n){ Node current = t.root; Node parent = null; while(true){ if (current == null) return null; if( current.value == n.value ){ break; } if (current.value > n.value){ parent = current; current = current.left; } else{ //(current.value < n.value) parent = current; current = current.right; } } return parent; } public static Node search(Node n,int key){ if(n == null || key == n.value ){ return n; } if(key < n.value){ return search(n.left,key); } else{ return search(n.right,key); } } public static Node treeMinimum(Node x){ if(x == null){ return null; } while(x.left != null){ x = x.left; } return x; } public static Node treeMaximum(Node x){ if(x == null){ return null; } while(x.right != null){ x = x.right; } return x; } public static Node treeSuccessor(Btree t,Node x){ if (x.right == null){ return treeMinimum(x.right); } Node y = getParent(t,x); while(y != null && x == y.right){ x = y; y = getParent(t,y); } return y; } public static Btree insert(Btree t,Node z){ Node y = null; Node x = t.root; while(x != null){ y = x; if(z.value < x.value) x = x.left; else x = x.right; } Node tmp = getParent(t,z); tmp = y; if(y == null){ t.root = z; } else if(z.value < y.value) y.left = z; else y.right = z; return t; } public static Btree delete(Btree t,Node z){ Node y,x; if (z.left == null || z.right == null) y = z; else y = treeSuccessor(t,z); if (y.left != null) x = y.left; else x = y.right; if (x != null){ Node tmp = getParent(t,x); tmp = getParent(t,y); } if (getParent(t,y) == null ){ t.root = x; } else{ if( y == getParent(t,y).left ){ getParent(t,y).left = x; } else{ getParent(t,y).right = x; } } if(y != z){ z.value = y.value; } return t; } public static void main(String[] args){ Btree test = new Btree(); Node n1 = new Node(6); Node n2 = new Node(3); Node n3 = new Node(9); Node n4 = new Node(1); Node n5 = new Node(16); Node n6 = new Node(4); Node n7 = new Node(2); Node n8 = new Node(11); Node n9 = new Node(13); test = insert(test,n1); test = insert(test,n2); test = insert(test,n3); test = insert(test,n4); test = insert(test,n5); test = insert(test,n6); test = insert(test,n7); test = insert(test,n8); test = insert(test,n9); inorderWalk(test.root); System.out.println(); test = delete(test,n8); inorderWalk(test.root); System.out.println(); test = delete(test,n5); inorderWalk(test.root); System.out.println(); test = delete(test,n2); inorderWalk(test.root); System.out.println(); test = delete(test,n1); inorderWalk(test.root); } } 

主要问题是删除部分，有时它按预期工作，有时删除错误，有时空指针exception。 可能是什么问题？

Ps：这不是作业

Answer 1

代码的一些直接问题： treeSuccessor以

  if (x.right == null){ return treeMinimum(x.right); } 

当然应该是if (x.right != null) 。

您的insert代码包含行

  Node tmp = getParent(t,z); tmp = y; 

您分配给tmp并立即再次分配给它的位置。 在我看来你根本不需要这些行，因为你不再使用tmp 。 此时，您已经将y插入其子z的节点，因此只需删除这些行。

再次，在delete ，你有行

  if (x != null){ Node tmp = getParent(t,x); tmp = getParent(t,y); } 

你实际上没有做任何事情，因为在这个片段之外看不到tmp 。 接下来，在delete ，重复表达式getParent(t,y) ，这可能是一个昂贵的操作，因此您应该只计算一次并将其分配给某个变量。

但总的来说，你的代码虽然看似正确（可能除了delete ，我完全不理解，但看起来很可疑），但它与典型的二叉树代码并不相似。 您实际上不需要getParent和treeSuccessor方法来实现search ， insert和delete 。 您search的基本结构也适用于其他结构，并进行了以下修改：

• 使用insert ，当您到达null链接时，不是返回null ，而是将元素插入到该点
• 使用delete ，当你找到该元素时，如果它只有一个（或没有）子元素，则将其替换为该子元素，如果它有两个子元素，则将其替换为左子树的最大值或右边的最小值。儿童树

这两个都需要您在下降到树时跟踪父节点，但这是您需要进行search的唯一修改。 特别是，树中永远不需要向上（ treeSuccessor会这样做）。

Answer 2

首先，您的实现与面向对象无关（除了使用对象）。 例如，插入和删除操作应该在树上运行。

此外，我建议将Node类实现为Tree类的静态成员。

 public class Tree { private Node root = null; // remainder omitted public boolean insert(int element) { if (isEmpty()) { root = new Node(element); return true; // empty tree, Node could be inserted, return true } Node current = root; // start at root Node parent; // the current Node's parent do { parent = current; if (element < current.element) { current = current.left; // go to left } else if (element > current.element) { current = current.right; // go to right } else { return false; // duplicates are NOT allowed, element could not be inserted -> return false } while (current != null); Node node = new Node(element); if (element < current.element) { parent.left = node; } else { parent.right = node; } return true; // node successfully inserted } public boolean isEmpty() { return root == null; } private static class Node { // static member class Node left = null; Node right = null; final int element; Node(int element) { this.element = element; } } } 

Answer 3

…你的删除代码是什么？ 它没有多大意义。 我会考虑以更合理的方式重写它。 没有无意义的单字母变量名称。 并添加评论！

一种可能的算法是：

 Get the parent of the node to delete Get the right-most node of the left subtree, or the leftmost node of the right subtree Remove the node to delete and replace it with the node you found Rebalance the tree 

…或者，如果你想破解这些东西，那么它是正确的，我会开始关注

 if (x != null){ Node tmp = getParent(t,x); tmp = getParent(t,y); } 

部分原因，因为这显然是错误的。

Answer 4

我将不得不支持Anon并重新进行重写。 空指针来自你的getParent函数（它显式地返回其他东西的空值）。 所以我会从那里开始并修复函数，以便它们只在函数结束时返回一件事和一件事。

Answer 5

这是二进制搜索树的完整实现在Java插入，搜索，countNodes，遍历，删除，空，最大和最小节点，查找父节点，打印所有叶节点，获取级别，获取高度，获取深度，打印左视图，镜像视图

 import java.util.NoSuchElementException; import java.util.Scanner; import org.junit.experimental.max.MaxCore; class BSTNode { BSTNode left = null; BSTNode rigth = null; int data = 0; public BSTNode() { super(); } public BSTNode(int data) { this.left = null; this.rigth = null; this.data = data; } @Override public String toString() { return "BSTNode [left=" + left + ", rigth=" + rigth + ", data=" + data + "]"; } } class BinarySearchTree { BSTNode root = null; public BinarySearchTree() { } public void insert(int data) { BSTNode node = new BSTNode(data); if (root == null) { root = node; return; } BSTNode currentNode = root; BSTNode parentNode = null; while (true) { parentNode = currentNode; if (currentNode.data == data) throw new IllegalArgumentException("Duplicates nodes note allowed in Binary Search Tree"); if (currentNode.data > data) { currentNode = currentNode.left; if (currentNode == null) { parentNode.left = node; return; } } else { currentNode = currentNode.rigth; if (currentNode == null) { parentNode.rigth = node; return; } } } } public int countNodes() { return countNodes(root); } private int countNodes(BSTNode node) { if (node == null) { return 0; } else { int count = 1; count += countNodes(node.left); count += countNodes(node.rigth); return count; } } public boolean searchNode(int data) { if (empty()) return empty(); return searchNode(data, root); } public boolean searchNode(int data, BSTNode node) { if (node != null) { if (node.data == data) return true; else if (node.data > data) return searchNode(data, node.left); else if (node.data < data) return searchNode(data, node.rigth); } return false; } public boolean delete(int data) { if (empty()) throw new NoSuchElementException("Tree is Empty"); BSTNode currentNode = root; BSTNode parentNode = root; boolean isLeftChild = false; while (currentNode.data != data) { parentNode = currentNode; if (currentNode.data > data) { isLeftChild = true; currentNode = currentNode.left; } else if (currentNode.data < data) { isLeftChild = false; currentNode = currentNode.rigth; } if (currentNode == null) return false; } // CASE 1: node with no child if (currentNode.left == null && currentNode.rigth == null) { if (currentNode == root) root = null; if (isLeftChild) parentNode.left = null; else parentNode.rigth = null; } // CASE 2: if node with only one child else if (currentNode.left != null && currentNode.rigth == null) { if (root == currentNode) { root = currentNode.left; } if (isLeftChild) parentNode.left = currentNode.left; else parentNode.rigth = currentNode.left; } else if (currentNode.rigth != null && currentNode.left == null) { if (root == currentNode) root = currentNode.rigth; if (isLeftChild) parentNode.left = currentNode.rigth; else parentNode.rigth = currentNode.rigth; } // CASE 3: node with two child else if (currentNode.left != null && currentNode.rigth != null) { // Now we have to find minimum element in rigth sub tree // that is called successor BSTNode successor = getSuccessor(currentNode); if (currentNode == root) root = successor; if (isLeftChild) parentNode.left = successor; else parentNode.rigth = successor; successor.left = currentNode.left; } return true; } private BSTNode getSuccessor(BSTNode deleteNode) { BSTNode successor = null; BSTNode parentSuccessor = null; BSTNode currentNode = deleteNode.left; while (currentNode != null) { parentSuccessor = successor; successor = currentNode; currentNode = currentNode.left; } if (successor != deleteNode.rigth) { parentSuccessor.left = successor.left; successor.rigth = deleteNode.rigth; } return successor; } public int nodeWithMinimumValue() { return nodeWithMinimumValue(root); } private int nodeWithMinimumValue(BSTNode node) { if (node.left != null) return nodeWithMinimumValue(node.left); return node.data; } public int nodewithMaximumValue() { return nodewithMaximumValue(root); } private int nodewithMaximumValue(BSTNode node) { if (node.rigth != null) return nodewithMaximumValue(node.rigth); return node.data; } public int parent(int data) { return parent(root, data); } private int parent(BSTNode node, int data) { if (empty()) throw new IllegalArgumentException("Empty"); if (root.data == data) throw new IllegalArgumentException("No Parent node found"); BSTNode parent = null; BSTNode current = node; while (current.data != data) { parent = current; if (current.data > data) current = current.left; else current = current.rigth; if (current == null) throw new IllegalArgumentException(data + " is not a node in tree"); } return parent.data; } public int sibling(int data) { return sibling(root, data); } private int sibling(BSTNode node, int data) { if (empty()) throw new IllegalArgumentException("Empty"); if (root.data == data) throw new IllegalArgumentException("No Parent node found"); BSTNode cureent = node; BSTNode parent = null; boolean isLeft = false; while (cureent.data != data) { parent = cureent; if (cureent.data > data) { cureent = cureent.left; isLeft = true; } else { cureent = cureent.rigth; isLeft = false; } if (cureent == null) throw new IllegalArgumentException("No Parent node found"); } if (isLeft) { if (parent.rigth != null) { return parent.rigth.data; } else throw new IllegalArgumentException("No Sibling is there"); } else { if (parent.left != null) return parent.left.data; else throw new IllegalArgumentException("No Sibling is there"); } } public void leafNodes() { if (empty()) throw new IllegalArgumentException("Empty"); leafNode(root); } private void leafNode(BSTNode node) { if (node == null) return; if (node.rigth == null && node.left == null) System.out.print(node.data + " "); leafNode(node.left); leafNode(node.rigth); } public int level(int data) { if (empty()) throw new IllegalArgumentException("Empty"); return level(root, data, 1); } private int level(BSTNode node, int data, int level) { if (node == null) return 0; if (node.data == data) return level; int result = level(node.left, data, level + 1); if (result != 0) return result; result = level(node.rigth, data, level + 1); return result; } public int depth() { return depth(root); } private int depth(BSTNode node) { if (node == null) return 0; else return 1 + Math.max(depth(node.left), depth(node.rigth)); } public int height() { return height(root); } private int height(BSTNode node) { if (node == null) return 0; else return 1 + Math.max(height(node.left), height(node.rigth)); } public void leftView() { leftView(root); } private void leftView(BSTNode node) { if (node == null) return; int height = height(node); for (int i = 1; i <= height; i++) { printLeftView(node, i); } } private boolean printLeftView(BSTNode node, int level) { if (node == null) return false; if (level == 1) { System.out.print(node.data + " "); return true; } else { boolean left = printLeftView(node.left, level - 1); if (left) return true; else return printLeftView(node.rigth, level - 1); } } public void mirroeView() { BSTNode node = mirroeView(root); preorder(node); System.out.println(); inorder(node); System.out.println(); postorder(node); System.out.println(); } private BSTNode mirroeView(BSTNode node) { if (node == null || (node.left == null && node.rigth == null)) return node; BSTNode temp = node.left; node.left = node.rigth; node.rigth = temp; mirroeView(node.left); mirroeView(node.rigth); return node; } public void preorder() { preorder(root); } private void preorder(BSTNode node) { if (node != null) { System.out.print(node.data + " "); preorder(node.left); preorder(node.rigth); } } public void inorder() { inorder(root); } private void inorder(BSTNode node) { if (node != null) { inorder(node.left); System.out.print(node.data + " "); inorder(node.rigth); } } public void postorder() { postorder(root); } private void postorder(BSTNode node) { if (node != null) { postorder(node.left); postorder(node.rigth); System.out.print(node.data + " "); } } public boolean empty() { return root == null; } } public class BinarySearchTreeTest { public static void main(String[] l) { System.out.println("Weleome to Binary Search Tree"); Scanner scanner = new Scanner(System.in); boolean yes = true; BinarySearchTree tree = new BinarySearchTree(); do { System.out.println("\n1. Insert"); System.out.println("2. Search Node"); System.out.println("3. Count Node"); System.out.println("4. Empty Status"); System.out.println("5. Delete Node"); System.out.println("6. Node with Minimum Value"); System.out.println("7. Node with Maximum Value"); System.out.println("8. Find Parent node"); System.out.println("9. Count no of links"); System.out.println("10. Get the sibling of any node"); System.out.println("11. Print all the leaf node"); System.out.println("12. Get the level of node"); System.out.println("13. Depth of the tree"); System.out.println("14. Height of Binary Tree"); System.out.println("15. Left View"); System.out.println("16. Mirror Image of Binary Tree"); System.out.println("Enter Your Choice :: "); int choice = scanner.nextInt(); switch (choice) { case 1: try { System.out.println("Enter Value"); tree.insert(scanner.nextInt()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 2: System.out.println("Enter the node"); System.out.println(tree.searchNode(scanner.nextInt())); break; case 3: System.out.println(tree.countNodes()); break; case 4: System.out.println(tree.empty()); break; case 5: try { System.out.println("Enter the node"); System.out.println(tree.delete(scanner.nextInt())); } catch (Exception e) { System.out.println(e.getMessage()); } case 6: try { System.out.println(tree.nodeWithMinimumValue()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 7: try { System.out.println(tree.nodewithMaximumValue()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 8: try { System.out.println("Enter the node"); System.out.println(tree.parent(scanner.nextInt())); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 9: try { System.out.println(tree.countNodes() - 1); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 10: try { System.out.println("Enter the node"); System.out.println(tree.sibling(scanner.nextInt())); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 11: try { tree.leafNodes(); } catch (Exception e) { System.out.println(e.getMessage()); } case 12: try { System.out.println("Enter the node"); System.out.println("Level is : " + tree.level(scanner.nextInt())); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 13: try { System.out.println(tree.depth()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 14: try { System.out.println(tree.height()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 15: try { tree.leftView(); System.out.println(); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 16: try { tree.mirroeView(); } catch (Exception e) { System.out.println(e.getMessage()); } break; default: break; } tree.preorder(); System.out.println(); tree.inorder(); System.out.println(); tree.postorder(); } while (yes); scanner.close(); } }