在Java中实现BinaryTree
发布时间：2020-12-15 04:56:32 所属栏目：Java 来源：网络整理
导读：我有这个代码用于BinaryTree创建和遍历 class Node{ Integer data; Node left; Node right; Node() { data = null; left = null; right = null; }}class BinaryTree{ Node head; Scanner input = new Scanner(System.in); BinaryTree() { head = null; } pub
|
我有这个代码用于BinaryTree创建和遍历
class Node
{
Integer data;
Node left;
Node right;
Node()
{
data = null;
left = null;
right = null;
}
}
class BinaryTree
{
Node head;
Scanner input = new Scanner(System.in);
BinaryTree()
{
head = null;
}
public void createNode(Node temp,Integer value)
{
Node newnode= new Node();
value = getData();
newnode.data = value;
temp = newnode;
if(head==null)
{
head = temp;
}
System.out.println("If left child exits for ("+value+") enter y else n");
if(input.next().charAt(0)=='y')
{
createNode(temp.left,value);
}
System.out.println("If right child exits for ("+value+") enter y else n");
if(input.next().charAt(0)=='y')
{
createNode(temp.right,value);
}
}
public Integer getData()
{
out.println("Enter the value to insert:");
return (Integer)input.nextInt();
}
public void print()
{
inorder(head);
}
public void inorder(Node node)
{
if(node!=null)
{
inorder(node.left);
System.out.println(node.data);
inorder(node.right);
}
else
return;
}
}
class BinaryTreeWorker
{
static BinaryTree treeObj = null;
static Scanner input = new Scanner(System.in);
public static void displaymenu()
{
int choice;
do{
out.print("n Basic operations on a tree:");
out.print("n 1. Create tree n 2. Insert n 3. Search value n 4. print listn Else. Exit n Choice:");
choice = input.nextInt();
switch(choice)
{
case 1:
treeObj = createBTree();
break;
case 2:
treeObj.createNode(null,null);
break;
case 3:
//searchnode();
break;
case 4:
treeObj.print();
break;
default:
return;
}
}while(true);
}
public static BinaryTree createBTree()
{
return new BinaryTree();
}
public static void main(String[] args)
{
displaymenu();
}
}
它编译并运行.但我认为顺序遍历存在问题. 我创建了下面的树,
2
1 3
但它只打印2. 解决方法
我已经尝试按你的方式解决问题,我已经粘贴了下面的解决方案.虽然我没有彻底测试它,所以它可能会在一些边缘条件下失败..但我已经测试了一个案例.如果在某些情况下失败,请告诉我.我希望其他人能帮助我更好地回答这个问题.我同意这个解决方案不是编写二叉树的最理想的方法,但是如果有人正在练习,它不会受到这种伤害.
import java.util.Scanner;
class Node
{
Integer data;
Node left;
Node right;
Node()
{
data = null;
left = null;
right = null;
}
}
class BinaryTree
{
Node head;
Scanner input = new Scanner(System.in);
BinaryTree()
{
head = null;
}
public void createNode(Node temp,Node newnode)
{
if(head==null)
{
System.out.println("No value exist in tree,the value just entered is set to Root");
head = newnode;
return;
}
if(temp==null)
temp = head;
System.out.println("where you want to insert this value,l for left of ("+temp.data+"),r for right of ("+temp.data+")");
char inputValue=input.next().charAt(0);
if(inputValue=='l'){
if(temp.left==null)
{
temp.left=newnode;
System.out.println("value got successfully added to left of ("+temp.data+")");
return;
}else {
System.out.println("value left to ("+temp.data+") is occupied 1by ("+temp.left.data+")");
createNode(temp.left,newnode);
}
}
else if(inputValue=='r')
{
if(temp.right==null)
{
temp.right=newnode;
System.out.println("value got successfully added to right of ("+temp.data+")");
return;
}else {
System.out.println("value right to ("+temp.data+") is occupied by ("+temp.right.data+")");
createNode(temp.right,newnode);
}
}else{
System.out.println("incorrect input plz try again,correctly");
return;
}
}
public Node generateTree(){
int [] a = new int[10];
int index = 0;
while(index<a.length){
a[index]=getData();
index++;
}
if(a.length==0 ){
return null;
}
Node newnode= new Node();
/*newnode.left=null;
newnode.right=null;*/
return generateTreeWithArray(newnode,a,0);
}
public Node generateTreeWithArray(Node head,int [] a,int index){
if(index >= a.length)
return null;
System.out.println("at index "+index+" value is "+a[index]);
if(head==null)
head= new Node();
head.data = a[index];
head.left=generateTreeWithArray(head.left,index*2+1);
head.right=generateTreeWithArray(head.right,index*2+2);
return head;
}
public Integer getData()
{
System.out.println("Enter the value to insert:");
return (Integer)input.nextInt();
}
public void print()
{
inorder(head);
}
public void inorder(Node node)
{
if(node!=null)
{
inorder(node.left);
System.out.println(node.data);
inorder(node.right);
}
else
return;
}
}
public class BinaryTreeWorker
{
static BinaryTree treeObj = null;
static Scanner input = new Scanner(System.in);
public static void displaymenu()
{
int choice;
do{
System.out.print("n Basic operations on a tree:");
System.out.print("n 1. Create tree n 2. Insert n 3. Search value n 4. print listn 5. generate a tree n Else. Exit n Choice:");
choice = input.nextInt();
switch(choice)
{
case 1:
treeObj = createBTree();
break;
case 2:
Node newnode= new Node();
newnode.data = getData();
newnode.left=null;
newnode.right=null;
treeObj.createNode(treeObj.head,newnode);
break;
case 3:
//searchnode();
break;
case 4:
System.out.println("inorder traversal of list gives follows");
treeObj.print();
break;
case 5:
Node tempHead = treeObj.generateTree();
System.out.println("inorder traversal of list with head = ("+tempHead.data+")gives follows");
treeObj.inorder(tempHead);
break;
default:
return;
}
}while(true);
}
public static Integer getData()
{
System.out.println("Enter the value to insert:");
return (Integer)input.nextInt();
}
public static BinaryTree createBTree()
{
return new BinaryTree();
}
public static void main(String[] args)
{
displaymenu();
}
}
[更新]：更新了代码以使用数组生成二叉树.这将涉及较少的用户交互. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
推荐文章
站长推荐
热点阅读