我创建了能够在二叉搜索树中以三种方式遍历后继节点的函数,顺序,后序和前序。我现在的挑战是尝试将它们都放在getNextItem方法中,然后使用getNextItem方法调用前面提到的每个函数。我知道getNextItem方法的框架应该是什么,但我不知道如何完成它。如果有人想测试我的函数,我还包括了insert和main方法。请注意,我不能更改getNextItem方法中的参数。
public class BinaryTree {
public static final int INORDER = 1;
public static final int PREORDER = 2;
public static final int POSTORDER = 3;
TreeNode root;
TreeNode currentNode;
class TreeNode {
int data;
TreeNode left, right, parent, root;
TreeNode(int data) {
this.data = data;
left = right = parent = root = null;
}
}
TreeNode insert(TreeNode node, int data) {
if (node == null) {
return (new TreeNode(data));
}
else {
TreeNode temp = null;
if (data <= node.data) {
temp = insert(node.left, data);
node.left = temp;
temp.parent = node;
}
else {
temp = insert(node.right, data);
node.right = temp;
temp.parent = node;
}
return node;
}
}
public Comparable getNextItem(int orderType) {
switch (orderType) {
case INORDER:
break;
case PREORDER:
break;
case POSTORDER:
break;
return;
}
TreeNode inOrderSuccessor(TreeNode n) {
if (n.right != null) {
return minValue(n.right);
}
TreeNode p = n.parent;
while (p != null && n == p.right) {
n = p;
p = p.parent;
}
return p;
}
TreeNode minValue(TreeNode node) {
TreeNode current = node;
while (current.left != null) {
current = current.left;
}
return current;
}
TreeNode preorderSuccessor(TreeNode n) {
if (n.left != null)
return n.left;
if (n.right != null)
return n.right;
TreeNode curr = n, parent = curr.parent;
while (parent != null && parent.right == curr) {
curr = curr.parent;
parent = parent.parent;
}
if (parent == null)
return null;
return parent.right;
}
TreeNode postorderSuccessor(TreeNode n) {
if (n == null)
return null;
TreeNode parent = n.parent;
if (parent.right == null || parent.right == n)
return parent;
TreeNode curr = parent.right;
while (curr.left != null)
curr = curr.left;
return curr;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
TreeNode root = null, temp = null, suc = null, suc2 = null, suc3 = null, min = null;
root = tree.insert(root, 20);
root = tree.insert(root, 8);
root = tree.insert(root, 22);
root = tree.insert(root, 4);
root = tree.insert(root, 12);
root = tree.insert(root, 10);
root = tree.insert(root, 14);
temp = root.left.right.right;
suc = tree.inOrderSuccessor(temp);
System.out.println(
"Inorder successor of "
+ temp.data + " is " + suc.data);
suc = tree.preorderSuccessor(temp);
System.out.println(
"Preorder successor of "
+ temp.data + " is " + suc.data);
suc = tree.postorderSuccessor(temp);
System.out.println(
"Postorder successor of "
+ temp.data + " is " + suc.data);
}
}
2条答案
按热度按时间kcrjzv8t1#
我建议从
currentNode = null
开始,这样getNextItem
的第一次调用实际上会返回给定遍历顺序中第一个节点的数据。我还想让类自己管理它的
root
成员,这样主程序在调用insert
后就不必更新它了。名称
minValue
并不能真正代表它的作用,因为它返回的不是节点的值,而是一个节点。它可能是TreeNode
类上的一个方法。以下是它的外观:
fslejnso2#
首先,我认为你的
*successor
方法需要是递归的;否则,根据排序方法,您将无法获得正确的后继者。假设您已经这样做了:getNextItem
意味着你保留一个游标(例如,要遍历的当前节点),或者你提供一个currentNode
作为参数。如果你不想要迭代行为(例如,如果你不想要游标),那么第二种选择对你来说会更好;即提供一个currentNode
作为参数,然后选择适当的方法(WRT订单类型)。请注意空检查等。
编辑:如果你不允许改变
getNextItem
方法的参数,那么你的树需要表现得像一个迭代器,因此你需要一个游标。因为你已经有了一个名为currentNode
的字段,那么你可以把它用作游标,最初将它设置为root
。然后它应该看起来像这样:
要使此选项正常工作,还需要有一个
reset
方法,该方法将currentNode
设置为root
,并关注null
值。我还建议进行一些重构,比如将节点管理封装到二叉树中,并确保排序算法正确工作。