Created
July 14, 2014 14:57
-
-
Save bitcpf/0f9a508eb9692a9362b2 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package cc150_4_6; | |
public class NodeSuccessor<Key extends Comparable<Key>> { | |
private Node root; | |
class Node{ | |
private Key key; | |
public Node left; | |
public Node right; | |
public Node parent; | |
public Node(Key data){ | |
this.key = data; | |
} | |
} | |
public NodeSuccessor(Key[] keys, int flag){ | |
if(flag ==1){ | |
for(Key key: keys) | |
put(key); | |
} | |
else{ | |
for(Key key:keys){ | |
BTput(key); | |
} | |
} | |
} | |
public void put(Key key){ | |
root = put(root,key); | |
} | |
public Node put(Node x, Key key){ | |
if(x == null) | |
// System.out.println("Put Key new Node: "+key); | |
{ | |
Node temp = new Node(key); | |
temp.parent = x; | |
return temp; | |
} | |
if(Integer.valueOf(key.toString())%2 ==0) { | |
x.left = put(x.left,key); | |
x.left.parent = x; | |
} | |
else { | |
x.right = put(x.right,key); | |
x.right.parent = x; | |
} | |
return x; | |
} | |
public void BTput(Key key){ | |
root = BTput(root,key); | |
} | |
public Node BTput(Node x, Key key){ | |
if(x == null) | |
{ | |
Node temp = new Node(key); | |
return temp; | |
} | |
int cmp = key.compareTo(x.key); | |
if(cmp < 0) { | |
x.left = BTput(x.left,key); | |
x.left.parent = x; | |
} | |
else if(cmp > 0) { | |
x.right = BTput(x.right,key); | |
x.right.parent = x; | |
} | |
return x; | |
} | |
public void printTree(Node head){ | |
if(head == null) return; | |
printTree(head.left); | |
System.out.print(head.key + ", "); | |
printTree(head.right); | |
} | |
public Node successor(Node node){ | |
System.out.println("current node is:"+node.key); | |
if(node == null) return null; | |
Node cur; | |
if(node.right != null){ | |
cur = node.right; | |
while(cur.left != null) | |
cur = cur.left; | |
return cur; | |
} | |
else{ | |
cur = node; | |
while(cur.parent != null){ | |
if(cur.parent.left == cur) | |
return cur.parent; | |
cur = cur.parent; | |
} | |
} | |
return null; | |
} | |
public static void main(String[] args) { | |
/* _______7______ | |
/ \ | |
__4__ __10 | |
/ \ / \ | |
3 8 11 | |
/ | |
1 | |
\ | |
2 | |
*/ | |
Integer[] data = { 7, 10, 4, 3, 1, 2, 8, 11 }; | |
NodeSuccessor<Integer> test = new NodeSuccessor<Integer>(data,2); | |
test.printTree(test.root); | |
System.out.println(""); | |
// System.out.println(test.root.left.left.parent.key); | |
System.out.println(test.successor(test.root.left.left).key); | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment