如何在另一个函数中调用一个函数?

Question

我创建了一些函数，这些函数能够在二叉搜索树中以三种方式遍历后续节点，即按顺序、后顺序和前顺序。我现在的挑战是尝试将它们全部放在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);
}
}

Answer 1

我建议从currentNode = null开始，这样getNextItem的第一次调用实际上将按照给定的遍历顺序返回第一个节点的数据。

我也会让类自己管理它的root成员，这样主程序就不必在调用insert后更新它。

名称minValue并不能真正代表它的功能，因为它返回的不是节点的值，而是一个节点。它可能是TreeNode类上的一个方法。

这是它的样子:

class BinaryTree {
public static final int INORDER = 1;
public static final int PREORDER = 2;
public static final int POSTORDER = 3;
TreeNode root, currentNode;
public class TreeNode {
int data;
TreeNode left, right, parent;
public TreeNode(int data) {
this.data = data;
left = right = parent = null; // There should be no root here.
}

TreeNode minNode() {
return left == null ? this : left.minNode();
}
}
public BinaryTree() {
root = null;
}

public void insert(int newData) {
root = root == null ? new TreeNode(newData) : insert(root, newData);
}

private TreeNode insert(TreeNode node, int newData) {
if (node == null) return new TreeNode(newData);
if (newData < node.data) {
node.left = insert(node.left, newData);
node.left.parent = node;
} else if (newData > node.data) { 
node.right = insert(node.right, newData);
node.right.parent = node;
}
return node;
}
private TreeNode inOrderSuccessor(TreeNode node) {
if (node == null) return root.minNode();
if (node.right != null) return node.right.minNode();
while (node.parent != null) {
if (node == node.parent.left) return node.parent;
node = node.parent;
}
return null;
}

private TreeNode preOrderSuccessor(TreeNode node) {
if (node == null) return root;
if (node.left != null) return node.left;
if (node.right != null) return node.right;
while (node.parent != null) {
if (node == node.parent.left && node.parent.right != null) {
return node.parent.right;
}
node = node.parent;
}
return null;
}

private TreeNode postOrderSuccessor(TreeNode node) {
if (node == null) return root.minNode();
if (node.parent == null) return null;
if (node.parent.right == node || node.parent.right == null) return node.parent;
node = node.parent.right;
while (node.left == null && node.right != null) {
node = node.right;
}
return node.minNode();
}

public Comparable getNextItem(int orderType) {
if (root == null) return null;
switch (orderType) {
case INORDER:
currentNode = inOrderSuccessor(currentNode);
break;
case PREORDER:
currentNode = preOrderSuccessor(currentNode);
break;
case POSTORDER:
currentNode = postOrderSuccessor(currentNode);
break;
}
return currentNode == null ? null : currentNode.data;
}

public void reset() {
currentNode = null;
}
void print() {
print(root, "");
}
void print(TreeNode node, String tab) {
if (node == null) return;
print(node.right, tab + "  ");
System.out.println(tab + node.data);
print(node.left, tab + "  ");
}
public static void main(String[] args) {
Main tree = new BinaryTree();
tree.insert(8);
tree.insert(3);
tree.insert(10);
tree.insert(9);
tree.insert(1);
tree.insert(6);
tree.insert(7);
tree.print();
tree.reset();
System.out.println("In-order traversal:");
while (true) {
Comparable data = tree.getNextItem(INORDER);
if (data == null) break;
System.out.print(data + " ");
}
System.out.println();
tree.reset();
System.out.println("Pre-order traversal:");
while (true) {
Comparable data = tree.getNextItem(PREORDER);
if (data == null) break;
System.out.print(data + " ");
}
System.out.println();
tree.reset();
System.out.println("Post-order traversal:");
while (true) {
Comparable  data = tree.getNextItem(POSTORDER);
if (data == null) break;
System.out.print(data + " ");
}
System.out.println();
}
}

Answer 2

首先，我认为你的*successor方法需要递归;否则无法根据排序方法得到正确的后继程序。假设您已经这样做了:

getNextItem暗示您保留游标(例如要遍历的当前节点)，或者您提供currentNode作为参数。如果你不想要迭代行为(例如，如果你不想要光标)，那么第二种选择更适合你;即提供一个currentNode作为参数，然后选择合适的方法(订单类型)。

//..previous code
public Comparable getNextItem(int orderType, TreeNode currentNode) {
TreeNode successor = null;
switch (orderType) {
case INORDER:
successor = inOrderSuccessor(currentNode);
break;
case PREORDER:
successor = preOrderSuccessor(currentNode);
break;
case POSTORDER:
successor = postOrderSuccessor(currentNode);
break;
} //end of switch

return successor.data;
}
//..the rest

请注意空支票等。

编辑:如果不允许更改getNextItem方法的参数，则树需要表现为迭代器，因此需要游标。因为您已经有一个名为currentNode的字段，那么您可以将其用作游标，最初将其设置为root。

那么它应该是这样的:

//..previous code
public Comparable getNextItem(int orderType) {
TreeNode successor = null;
switch (orderType) {
case INORDER:
successor = inOrderSuccessor(this.currentNode);
break;
case PREORDER:
successor = preOrderSuccessor(this.currentNode);
break;
case POSTORDER:
successor = postOrderSuccessor(this.currentNode);
break;
} //end of switch
//keep the cursor up to date.
this.currentNode = successor;
return successor.data;
}
//..the rest

要使此选项正常工作，您还需要有一个reset方法，将currentNode设置为root，并密切关注null的值。

我也会建议一些重构，比如在二叉树中封装节点管理，并确保你的排序算法正确工作。