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

Question

我创建的函数能够在二叉搜索树中以所有 3 种方式（按顺序、后序和前序）遍历它来获取后继节点。我现在的挑战是尝试将它们全部放在一个 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

首先，我认为你的

*successor

方法需要是递归的；否则您将无法根据订购方法获得正确的继任者。假设你已经做到了：

getNextItem

意味着您保留一个游标（例如要遍历的当前节点），或者您提供一个

currentNode

作为参数。如果您不想要迭代行为（例如，如果您不想要游标），那么第二个选项对您来说会更好；也就是提供一个

currentNode

作为参数，然后选择合适的方法WRT订单类型）。

   //..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

值。

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

Answer 2

我建议从

currentNode = null

开始，这样

getNextItem

的第一次调用实际上将返回给定遍历顺序中第 first 节点的数据。

我也会让班级自己管理它的

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 Main();
        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:");
        for (int i = 0; i < 8; i++) {
            Comparable  data = tree.getNextItem(POSTORDER);
            if (data == null) break;
            System.out.print(data + " ");
        }
        System.out.println();
    }
}