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

juzqafwq  于 2023-04-04  发布在  Java
关注(0)|答案(2)|浏览(260)

我创建了能够在二叉搜索树中以三种方式遍历后继节点的函数,顺序,后序和前序。我现在的挑战是尝试将它们都放在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);

    }
}
kcrjzv8t

kcrjzv8t1#

我建议从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();
    }
}
fslejnso

fslejnso2#

首先,我认为你的*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值。
我还建议进行一些重构,比如将节点管理封装到二叉树中,并确保排序算法正确工作。

相关问题