二叉树创建并查询 (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
后序结果7import 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));
}
}
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));
}
}
稍等一下，我来帮你写，待会发你。
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);
}
}
您好，我是有问必答小助手，您的问题已经有小伙伴解答了，您看下是否解决，可以追评进行沟通哦~
如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～
ps:问答VIP仅需29元，即可享受5次/月 有问必答服务，了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632
你好，我正在做这道题，但是第二个测试点一直显示答案错误，N极大或者极小的测试点都是对的，想问问这是为啥呢