1
Javaを使用して、次の質問をgeeksforgeeks.com http://www.geeksforgeeks.org/inorder-predecessor-successor-given-key-bst/から解決しようとしています。私は木の中にすでにあるキーを探している間、正しい後継者を得ていますが、ツリーにない値については、私はkeyの正しい後継者を得ることができません。バイナリ検索ツリーが正しいinorderの後継語を返さない
package com.geeksforgeeks.binarysearchtree;
public class BinarySearchTree {
public Node root;
static class Node
{
int data;
Node right;
Node left;
public Node(int data)
{
this.data=data;
this.right=null;
this.left=null;
}
}
public void insert(int data)
{
root=treeInsert(root,data);
}
public Node treeInsert(Node root,int data)
{
if(root==null)
{
root=new Node(data);
return root;
}
if(data >= root.data)
root.right= treeInsert(root.right,data);
else
root.left= treeInsert(root.left,data);
return root;
}
public void delete(int data)
{
root=recDelete(root,data);
}
public Node recDelete(Node root,int data)
{
//Base Case
if(root==null)return root;
//Recurring down the tree
if(root.data>data)
root.left=recDelete(root.left,data);
else if(root.data<data)
root.right=recDelete(root.right,data);
else
{
if(root.left==null)return root.right;
else if(root.right==null)return root.left;
root.data= min(root.right);
root.right=recDelete(root.right,root.data);
}
return root;
}
private int min(Node root) {
// TODO Auto-generated method stub
int minv=root.data;
while(root.left!=null)
{
minv=root.left.data;
root=root.left;
}
return minv;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/ \
30 70
/\ /\
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("successor :"+tree.inOrderSuccessor(50));
tree.delete(20);
tree.inOrder();
tree.delete(30);
tree.inOrder();
tree.delete(50);
tree.inOrder();
}
private int inOrderSuccessor(int i) {
Node successor=recursiveInOrderSuccessor(root,i);
if(successor!=null)
return successor.data;
else
return -1;
}
private Node recursiveInOrderSuccessor(Node root2,int i) {
Node successor=null;
//if tree is empty
if(root2==null)return null;
//if root is the key
if(root2.data==i)
{
successor=root2.right;
if(root2.right!=null)
{
while(successor.left!=null)
successor=successor.left;
}
return successor;
}
Node newSuccessor = null;
if(root2.data>i)
{
successor=root2;
newSuccessor=recursiveInOrderSuccessor(root2.left,i);
}
else
{
successor=root2;
newSuccessor=recursiveInOrderSuccessor(root2.right,i);
}
if(newSuccessor==null)
return successor;
else
return newSuccessor;
}
private void inOrder() {
// TODO Auto-generated method stub
inOrderRecursion(root);
}
private void inOrderRecursion(Node root) {
// TODO Auto-generated method stub
if(root!=null)
{
inOrderRecursion(root.left);
System.out.println(root.data);
inOrderRecursion(root.right);
}
}
}