二进制搜索树实现和Java

本文介绍了二进制搜索树实现和Java的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

这是我的Node代码：

公共类Node {剩余的节点； 节点权限； int值； Node（int value）{ this.value = value; this.left = null; this.right = null; } }

对于Bstree：

公共类Btree {节点根； Btree（）{ this.root = null; } public static void inorderWalk（Node n）{ if（n！= null）{ inorderWalk（n.left）; System.out.print（n.value +）; inorderWalk（n.right）; } } 公共静态节点getParent（Btree t，Node n）{ Node current = t.root; Node parent = null; while（true）{ if（current == null） return null; if（current.value == n.value）{休息; } 如果（current.value> n.value）{ parent = current; current = current.left; } else {//(current.value< n.value） parent = current; current = current.right; } } 返还父母； } 公共静态节点搜索（节点n，int键）{ if（n == null || key == n.value）{ return n; } if（key< n.value）{ return search（n.left，key）; } else { return search（n.right，key）; } } 公共静态节点treeMinimum（Node x）{ if（x == null）{返回null; } while（x.left！= null）{ x = x.left; } return x; } 公共静态节点treeMaximum（Node x）{ if（x == null）{返回null; } while（x.right！= null）{ x = x.right; } return x; } 公共静态节点treeSuccessor（Btree t，Node x）{ if（x.right == null）{返回treeMinimum（x.right） ; } 节点y = getParent（t，x）; while（y！= null&& x == y.right）{ x = y; y = getParent（t，y）; } 返回y； } 公共静态Btree insert（Btree t，Node z）{ Node y = null; 节点x = t.root; while（x！= null）{ y = x; if（z.value< x.value） x = x.left; else x = x.right; } 节点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; 返回t; } 公共静态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）{节点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（）; 节点n1 =新节点（6）; 节点n2 =新节点（3）; 节点n3 =新节点（9）; 节点n4 =新节点（1）; 节点n5 =新节点（16）; 节点n6 =新节点（4）; 节点n7 =新节点（2）; 节点n8 =新节点（11）; 节点n9 =新节点（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）; } }

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

Ps：这不是家庭作业

解决方案

您的代码有一些直接的问题：您的 treeSuccessor 开头为

if（x.right == null）{返回treeMinimum（x.right）; }

如果（x.right！= null），当然。

您的插入代码包含以下行

节点tmp = getParent（t，z）; tmp = y;

您在其中分配给 tmp 的位置再来一次。在我看来，您根本不需要这些行，因为您不再使用 tmp 了。此时，您将 y 作为要插入其子 z 的节点，因此只需删除这些行。 / p>

再次，在删除中，您有以下几行

if（x！= null）{节点tmp = getParent（t，x）; tmp = getParent（t，y）; }

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

但是总的来说，您的代码虽然看起来是正确的（可能与 delete ，我不太了解，但看起来很可疑），与典型的二叉树代码不太相似。您实际上并不需要 getParent 和 treeSuccessor 方法来实现搜索，插入和删除。您对搜索拥有的基本结构也适用于其他结构，并进行了以下修改：

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

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

I am trying to implement BST algorithm using Cormen's pseudo code yet having issue.

Here is my Code for Node:

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

and for the 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); } }

The main problem is with the remove part, sometimes it is working as intended, sometimes removing wrongly and sometimes null pointer exception. What can be the issue ?

Ps: this is NOT a homework

解决方案

Some immediate problems with your code: your treeSuccessor starts with

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

which should be if (x.right != null), of course.

Your insert code has the lines

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

where you assign to tmp and immediately assign to it again. It doesn't seem to me that you need these lines at all, since you don't use tmp further on. At this moment, you have y being the node to whose child z gets inserted, so just delete these lines.

Again, in delete, you have the lines

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

where you don't actually do anything, since tmp is not visible outside this snippet. And further on, in delete, you repeat the expression getParent(t,y), which can be an expensive operation, so you should compute it only once and assign it to some variable.

But in general, your code, though it seems correct (probably apart from delete, which I did not understand completely but which looks suspicious), does not much resemble typical binary tree code. You don't really need the getParent and treeSuccessor methods to implement search, insert, and delete. The basic structure that you have for search works for the others too, with the following modifications:

• with insert, when you get to a null link, instead of returning null, insert the element to that point
• with delete, when you find the element, if it has only one (or no) child, replace it with that child, and if it has two children, replace it with either the maximum of the left child tree or the minimum of the right child tree

Both of these require in addition that you keep track of the parent node while descending into the tree, but that's the only modification you need to make to search. In particular, there is never any need to go upwards in the tree (which treeSuccessor will do).