我正在研究一種使用二叉搜索樹獲取前一個(gè)節(jié)點(diǎn)的方法。現(xiàn)在我想我明白了，但是我正在努力處理我的 if 語句。指令是 getPrevNode(BSTNode) 方法應(yīng)該在樹中找到參數(shù)之前的節(jié)點(diǎn)。這是我正在使用的算法。? 如果節(jié)點(diǎn)有左子節(jié)點(diǎn)，則向下移動(dòng)左子樹以獲得最大節(jié)點(diǎn)? 否則，如果節(jié)點(diǎn)有父節(jié)點(diǎn)，我們需要按如下方式向上移動(dòng)樹：? 如果節(jié)點(diǎn)是右子節(jié)點(diǎn)，則返回其父節(jié)點(diǎn)? 如果節(jié)點(diǎn)是左孩子，則向上移動(dòng)樹直到成為右孩子并返回其父節(jié)點(diǎn)? 如果你到達(dá)根節(jié)點(diǎn)并且永遠(yuǎn)不是右孩子，那么就沒有前一個(gè)節(jié)點(diǎn)讓我們注意，這也是一個(gè)輔助方法。因此，這是我到目前為止的代碼，遵循該算法。 private BSTNode<E> getPrevNode(BSTNode<E> node){ if(node.left != null) { return getPrevNode(node.left); } else if(node.parent != null) { if(node == node.right) { return node.parent; } else if(node == node.left) { return node.parent; } } return getPrevNode(node);}現(xiàn)在我知道它不準(zhǔn)確，但這就是我要問的原因。我將嘗試提供有關(guān)此代碼的一些信息，但我將省略一些方法，因?yàn)槲也幌ＭL。public class BinarySearchTree<E extends Comparable<E>>{private BSTNode<E> root; // root of overall treeprivate int numElements;private BSTNode<E> first;// post: constructs an empty search treepublic BinarySearchTree(){ this.root = null; this.numElements = 0;}private BSTNode<E> getPrevNode(BSTNode<E> node){ if(node.left != null) { return getPrevNode(node.left); } else if(node.parent != null) { if(node == node.right) { return node.parent; } else if(node == node.left) { return node.parent; } } return getPrevNode(node);} public class Iterator{ private BSTNode<E> currentNode; public Iterator() { currentNode = first; } public boolean hasNext() { return currentNode != null; } public E next() { E value = currentNode.data; currentNode = currentNode.next; return value; }}private static class BSTNode<E>{ public E data; public BSTNode<E> left; public BSTNode<E> right; public BSTNode<E> parent; public BSTNode<E> next; public BSTNode(E data) { this(data, null, null, null, null); }我希望這些信息有用。
3 回答
搖曳的薔薇
TA貢獻(xiàn)1793條經(jīng)驗(yàn) 獲得超6個(gè)贊
試試這個(gè)也許：
private BSTNode<E> getPrevNode(BSTNode<E> node) {
if(node.left != null) {
node = node.left;
while(node.right != null) {
node = node.right;
}
return node;
} else if(node.parent != null) {
// If the node is a right child, return its parent
if(node.parent.right == node) {
return node.parent;
}
// If the node is a left child, move up the tree
// until you are a right child and return its parent
if(node.parent.left == node) {
while(node.parent.right != node) {
// If you reach the root and are never a right child, no previous node return null
if(node.parent == root) {
return null;
}
node = node.parent;
}
return node.parent;
}
}
return null;
}
交互式愛情
TA貢獻(xiàn)1712條經(jīng)驗(yàn) 獲得超3個(gè)贊
利亞姆的回答到目前為止也是正確的，但是這是解決它的另一種方法。
private BSTNode<E> getPrevNode(BSTNode<E> node)
{
if(node.left != null)
{
node = node.left;
while(node.right != null)
{
node = node.right;
}
return node;
}
else if(node.parent != null)
{
if(node.parent.right == node)
{
return node.parent;
}
if(node.parent.left == node)
{
while(node.parent != null && node.parent.left == node)
{
node = node.parent;
}
if(node == root)
{
return null;
}
else
{
return node.parent;
}
}
}
return null;
}
長風(fēng)秋雁
TA貢獻(xiàn)1757條經(jīng)驗(yàn) 獲得超7個(gè)贊
這是一個(gè)代碼更少的解決方案。
private BSTNode<E> getPrevNode(BSTNode<E> node, int val) {
if (node == null) return null;
BSTNode<E> prev = null;
while (node != null) {
if (val < node.data) {
prev = node;
node = node.left;
} else if (val > node.data) {
prev = node;
node = node.right;
} else {
break;
}
}
return node != null ? prev : null;
}
添加回答
舉報(bào)
0/150
提交
取消