用java编写查找二叉树某个结点的父结点的算法。要求： 1.采用链表存储结构，添加该方法为其成员方法； 2、编写测试程序，创建一棵二叉树，测试查找某个给定结点的父结点。 要求：1、分别采用二叉链表和三叉链表实现 二叉树的root为1，左孩子为2，右孩子为3

在Java中，我们可以为二叉搜索树（Binary Search Tree，BST）定义一个Node类，包含节点值、左指针和右指针，并提供一个`findParent(Node target)`方法来查找给定结点的父节点。这里我会展示如何为二叉链表和三叉链表实现这个功能。

首先，我们定义一个二叉链表的`Node`类：

public class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;

    public BinaryTreeNode(int value) {
        this.value = value;
    }

    // 父节点查找方法
    public BinaryTreeNode findParent(BinaryTreeNode target) {
        if (value == target.value) return null; // 目标节点本身就是根节点，没有父节点
        if (target.value < value) { // 向左寻找
            if (left != null) return left.findParent(target);
            else return this; // 左子树不存在，所以当前节点就是目标节点的父节点
        } else { // 向右寻找
            if (right != null) return right.findParent(target);
            else return this; // 右子树不存在，所以当前节点就是目标节点的父节点
        }
    }
}

接下来，对于三叉链表（每个节点有三个指针，分别指向左孩子、右孩子和父节点），我们需要稍微修改一下`Node`类：

public class TernaryTreeNode {
    int value;
    TernaryTreeNode left;
    TernaryTreeNode middle;
    TernaryTreeNode right;
    TernaryTreeNode parent;

    public TernaryTreeNode(int value) {
        this.value = value;
    }

    // 父节点查找方法
    public TernaryTreeNode findParent(TernaryTreeNode target) {
        if (value == target.value) return parent; // 直接返回父节点
        if (target.value < value) { // 向左或中间寻找
            if (left != null || middle != null) {
                return left != null ? left.findParent(target) : middle.findParent(target);
            } else {
                return this; // 子节点不存在，当前节点就是目标节点的父节点
            }
        } else { // 向右寻找
            if (right != null) return right.findParent(target);
            else return this; // 右子树不存在，所以当前节点就是目标节点的父节点
        }
    }
}

现在你可以创建测试程序来验证这两个方法：

public static void main(String[] args) {
    // 二叉链表示例
    BinaryTreeNode root = new BinaryTreeNode(1);
    root.left = new BinaryTreeNode(2);
    root.right = new BinaryTreeNode(3);

    // 查找特定节点的父节点
    BinaryTreeNode nodeToFind = root.left;
    BinaryTreeNode parentNode = root.findParent(nodeToFind);
    System.out.println("Parent of " + nodeToFind.value + " is " + (parentNode == null ? "null" : parentNode.value));

    // 三叉链表示例
    TernaryTreeNode ternaryRoot = new TernaryTreeNode(1);
    ternaryRoot.left = new TernaryTreeNode(2);
    ternaryRoot.middle = new TernaryTreeNode(3);
    ternaryRoot.parent = null; // 初始化父节点

    // 测试三叉链表
    TernaryTreeNode ternaryNodeToFind = ternaryRoot.left;
    TernaryTreeNode ternaryParentNode = ternaryRoot.findParent(ternaryNodeToFind);
    System.out.println("Parent of " + ternaryNodeToFind.value + " is " + (ternaryParentNode == null ? "null" : ternaryParentNode.value));
}