二叉树创建并查询 (java)

Question

要求：用java编写代码，不用C++；

创建一个二叉树，结点存放的是整型数据，遵循的规则是：第一个数值作为二叉树的树根，小于父节点的值放在左子节点，大于父节点的值放在右子节点。 在创建好二叉树的基础之上，进行查询，通过输入的要查询的值，找出它双亲结点、孩子结点、兄弟结点。 输出二叉树的前序、中序、后序遍历结果。

输入格式:

输入数值为整型，多行输入。 第一行：二叉树的结点个数。 第二行：结点的值，以逗号间隔。 第三行：要查询的结点值。

输出格式:

第一行输出要查询的结点的双亲结点。 第二行输出要查询的结点的孩子结点。 第三行输出兄弟结点。 第四行为二叉树前序遍历结果。 第五行为二叉树中序遍历结果。 第六行为二叉树后序遍历结果。

输入样例:

在这里给出一组输入。例如：

8
5,2,9,11,4,23,10,16
23

输出样例:

在这里给出相应的输出。例如：

23的双亲是11
23的左孩子是16无右孩子
23的兄弟是10
前序结果5,2,4,9,11,10,23,16
中序结果2,4,5,9,10,11,16,23
后序结果4,2,10,16,23,11,9,5

输入样例2:

在这里给出一组输入。例如：

1
7
7

输出样例2:

在这里给出相应的输出。例如：

7无双亲
7无孩子
7无兄弟
前序结果7
中序结果7
后序结果7

Answer 1

import java.util.List;
import java.util.Scanner;
public class BinaryTree {
    private Node root;
    /**
     * 内部节点类
     */
    private class Node{
        private Node left;
        private Node right;
        private int data;
        public Node(int data){
            this.left = null;
            this.right = null;
            this.data = data;
        }
    }

    public BinaryTree(){
        root = null;
    }

    /**
     * 递归创建二叉树
     * @param node
     * @param data
     */
    public void buildTree(Node node,int data){
        if(root == null){
            root = new Node(data);
        }else{
            if(data < node.data){
                if(node.left == null){
                    node.left = new Node(data);
                }else{
                    buildTree(node.left,data);
                }
            }else{
                if(node.right == null){
                    node.right = new Node(data);
                }else{
                    buildTree(node.right,data);
                }
            }
        }
    }

    /**
     * 前序遍历
     * @param node
     */
    public void preOrder(Node node,StringBuilder sb){
        if(node != null){
            sb.append(node.data+",");
            preOrder(node.left,sb);
            preOrder(node.right,sb);
        }
    }

    /**
     * 中序遍历
     * @param node
     */
    public void inOrder(Node node,StringBuilder sb){
        if(node != null){
            inOrder(node.left,sb);
            sb.append(node.data+",");
            inOrder(node.right,sb);
        }
    }

    /**
     * 后序遍历
     * @param node
     */
    public void postOrder(Node node,StringBuilder sb){
        if(node != null){
            postOrder(node.left,sb);
            postOrder(node.right,sb);
            sb.append(node.data+",");
        }
    }

    //查询双亲
    public Node parent(int target){
        Node temp=parent(root, target);
        return temp;
    }
    public Node parent(Node node,int target){
        if(node==null){
            return null;
        }
        if((node.left!=null&&node.left.data==target)||(node.right!=null&&node.right.data==target)){
            return node;
        }

        //在左子树中查找 ， 如果左子树中没有去右子树中查找
        Node N;
        if((N=parent(node.left,target))!=null){
            return N;
        }else{
            return parent(node.right,target);
        }
    }

    //查询目标当前节点
    public Node findNode(int target){
        Node node = new Node(target);
        if(root==null){
            return null;
        }else{
            Node temp=findNode(root,target);
            return temp;
        }
    }
    public Node findNode(Node root,int target){
        if(root==null){
            return null;
        }
        if(root.data==target){
            return root;
        }
        Node N;
        Node P;
        if((N=findNode(root.left,target))!=null){
            return N;
        }else{
            root=root.right;
            if((P=findNode(root,target))==null){
                return null;
            }else{
                return P;
            }
        }
    }
    


    public static void main(String[] args) {
        StringBuilder sb=new StringBuilder();
        Scanner scanner=new Scanner(System.in);
        System.out.println("输入：");
        int count=scanner.nextInt();
        String[] a = scanner.next().split(",");
        int target=scanner.nextInt();
        BinaryTree bTree = new BinaryTree();
        for (int i = 0; i < a.length; i++) {
            bTree.buildTree(bTree.root, Integer.valueOf(a[i]));
        }
        System.out.println("输出：");
        Node parent = bTree.parent(target);
        if (parent==null){
            System.out.println(target+"无双亲");
        }else{
            System.out.println(target+"的双亲是"+parent.data);
        }
        Node currNode = bTree.findNode(target);
        if (currNode==null){
            System.out.println("不存在当前节点");
        }else{
            if(currNode.left==null&&currNode.right==null){
                System.out.println(target+"无孩子");
            }else{
                System.out.print(target+(currNode.left==null?"无左孩子":"左孩子是"+currNode.left.data));
                System.out.println(currNode.right==null?"无右孩子":"右孩子是"+currNode.right.data);
            }
        }
        if(parent==null){
            System.out.println(target+"无兄弟");
        }else {
            if (parent.right == null || parent.left == null) {
                System.out.println(target + "无兄弟");
            } else {
                System.out.println(target + "的兄弟是" + (parent.right.data == currNode.data ? parent.left.data : parent.right.data));
            }
        }
        bTree.preOrder(bTree.root,sb);
        System.out.println("前序结果"+sb.toString().substring(0,sb.length()-1));
        sb.setLength(0);
        bTree.inOrder(bTree.root,sb);
        System.out.println("中序结果"+sb.toString().substring(0,sb.length()-1));
        sb.setLength(0);
        bTree.postOrder(bTree.root,sb);
        System.out.println("后序结果"+sb.toString().substring(0,sb.length()-1));
    }
}