weixin_49484445
2021-05-13 13:09
采纳率: 50%
浏览 107
已采纳

二叉树创建并查询 (java)

要求:用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
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

6条回答 默认 最新

  • CSDN专家-sinjack 2021-05-13 15:33
    已采纳
    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));
        }
    }
    
    点赞 评论
  • CSDN专家-sinjack 2021-05-13 13:58

    稍等一下,我来帮你写,待会发你。

    点赞 评论
  • package T4;
    
    public class Node {
    
    	//数据域
    	int data;
    	//左孩子
    	Node leftChild;
    	//右孩子
    	Node rightChild;
    	
    	public Node(int data) {
    		this.data = data;
    		leftChild = null;
    		rightChild = null;
    	}
    }
    
    package T4;
    
    public class BTree {
    
    	//根节点
    	Node root;
    	public BTree(int data) {
    		root = new Node(data);
    	}
    	//新增节点
    	//10,8,7,20,90,100,3,6,1,-10
    	public void addNode(int data){
    		//获取根节点
    		Node p=root;
    		//生成新增节点
    		Node t = new Node(data);
    		while(true){
    			//放到根节点的左边
    			if(p.data>data){
    				if(p.leftChild !=null){
    					//继续往下找
    					p = p.leftChild;
    				}else{
    					p.leftChild = t;
    					break;
    				}
    			}else{//放到根节点的右边
    				if(p.rightChild!=null){
    					p=p.rightChild;
    				}else{
    					p.rightChild = t;
    					break;
    				}
    			}
    		}
    	}
    	public void display(Node root){
    		//先根遍历10,8,7,3,1,-10,6,20,90,100
    		System.out.println(root.data);
    		if(root.leftChild!=null){ //往左走
    			System.out.println("往左走");
    			display(root.leftChild);
    		}
    		//中根遍历:-10,1,3,6,7,8,10,20,90,100
    //		System.out.println(root.data);
    		if(root.rightChild!=null){//往右走
    			System.out.println("往右走");
    			display(root.rightChild);
    		}
    		//后根遍历:-10,1,6,3,7,8,100,90,20,10
    //		System.out.println(root.data);
    	}
    	public static void main(String[] args) {
    		//10,8,7,20,90,100,3,6,1,-10
    		BTree tree = new BTree(10);
    		tree.addNode(8);
    		tree.addNode(7);
    		tree.addNode(20);
    		tree.addNode(90);
    		tree.addNode(100);
    		tree.addNode(3);
    		tree.addNode(6);
    		tree.addNode(1);
    		tree.addNode(-10);
    		tree.display(tree.root);
    	}
    }
    
    点赞 评论
  • CSDN专家-sinjack 2021-05-13 14:45
    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));
        }
    }
    
    点赞 评论
  • CSDN专家-sinjack 2021-05-13 14:46

    点赞 评论
  • 有问必答小助手 2021-05-14 17:03

    您好,我是有问必答小助手,您的问题已经有小伙伴解答了,您看下是否解决,可以追评进行沟通哦~

    如果有您比较满意的答案 / 帮您提供解决思路的答案,可以点击【采纳】按钮,给回答的小伙伴一些鼓励哦~~

    ps:问答VIP仅需29元,即可享受5次/月 有问必答服务,了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632

    点赞 评论

相关推荐 更多相似问题