public class BSTNode
1: //BSTNode.java
3: public class BSTNode
4: {
5: public int data;
6: public BSTNode parent;
7: public BSTNode left;
8: public BSTNode right;
10: public BSTNode
11: (
12: int data,
13: BSTNode parent,
14: BSTNode left,
15: BSTNode right
16: )
17: {
18: this.data = data;
19: this.parent = parent;
20: this.left = left;
21: this.right = right;
22: }
24: public BSTNode
25: (
26: int data,
27: BSTNode parent
28: )
29: {
30: this(data, parent, null, null);
31: }
33: public int count()
34: {
35: int leftCount = 0;
36: int rightCount = 0;
37: if (left != null)
38: {
39: leftCount = left.count();
40: }
41: if (right != null)
42: {
43: rightCount = right.count();
44: }
45: return 1 + leftCount + rightCount;
46: }
48: public BSTNode getSuccessor()
49: {
50: // Successor resides in right subtree, if present
51: if (right != null)
52: {
53: BSTNode successor = right;
54: while (successor.left != null)
55: {
56: successor = successor.left;
57: }
58: return successor;
59: }
61: // Otherwise the successor is up the tree
62: // Traverse up the tree until a parent is encountered from the left
63: BSTNode node = this;
64: while (node.parent != null && node == node.parent.right)
65: {
66: node = node.parent;
67: }
68: return node.parent;
69: }
71: public void replaceChild
72: (
73: BSTNode currentChild,
74: BSTNode newChild
75: )
76: {
77: if (currentChild == left)
78: {
79: left = newChild;
80: if (left != null)
81: {
82: left.parent = this;
83: }
84: }
85: else if (currentChild == right)
86: {
87: right = newChild;
88: if (right != null)
89: {
90: right.parent = this;
91: }
92: }
93: }
94: }