在Java中实现BinaryTree
我有这个代码用于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 list\n 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) 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,a,index*2+1); head.right=generateTreeWithArray(head.right,a,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 list\n 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(); } }
[更新] ：更新了代码以使用数组生成二叉树。 这将涉及较少的用户交互。
使用所有遍历类型和测试用例在Java中实现二进制树的最佳方法如下
package com.nitin.tree; public class Tree { private Node parent; private int data; private int size = 0; public Tree() { parent = new Node(data); } public void add(int data) { if (size == 0) { parent.data = data; size++; } else { add(parent, new Node(data)); } } private void add(Node root, Node newNode) { if (root == null) { return; } if (newNode.data < root.data) { if (root.left == null) { root.left = newNode; size++; } else { add(root.left, newNode); } } else { if (root.right == null) { root.right = newNode; size++; } else { add(root.right, newNode); } } } public int getLow() { Node current = parent; while (current.left != null) { current = current.left; } return current.data; } public int getHigh() { Node current = parent; while (current.right != null) { current = current.right; } return current.data; } private void in(Node node) { if (node != null) { in(node.left); System.out.print(node.data + " "); in(node.right); } } private void pre(Node node) { if (node != null) { System.out.print(node.data + " "); pre(node.left); pre(node.right); } } private void post(Node node) { if (node != null) { post(node.left); post(node.right); System.out.print(node.data + " "); } } public void preorder() { System.out.print("Preorder Traversal->"); pre(parent); System.out.println(); } public void postorder() { System.out.print("Postorder Traversal->"); post(parent); System.out.println(); } public void inorder() { System.out.print("Inorder Traversal->"); in(parent); System.out.println(); } private class Node { Node left; Node right; int data; public Node(int data) { this.data = data; } } public String toString() { Node current = parent; System.out.print("Traverse From Left "); while (current.left != null && current.right != null) { System.out.print(current.data + "->[" + current.left.data + " " + current.right.data + "] "); current = current.left; } System.out.println(); System.out.print("Traverse From Right "); current = parent; while (current.left != null && current.right != null) { System.out.print(current.data + "->[" + current.left.data + " " + current.right.data + "] "); current = current.right; } return ""; } public static void main(String af[]) { Tree t = new Tree(); t.add(40); t.add(25); t.add(78); t.add(10); t.add(32); t.add(50); t.add(93); t.add(3); t.add(17); t.add(30); t.add(38); System.out.println(t.getLow()); System.out.println(t.getHigh()); System.out.println("Size-" + t.size); System.out.println(t); t.inorder(); t.preorder(); t.postorder(); } }
你的问题是在public void createNodes(Node temp, T data)函数中。 传入一个与类变量temp同名的参数。 首先，我认为你自己不需要类变量。 第二个在这个方法中赋值给temp只有局部效果 – 你放松了temp参数中的信息，但设置temp，不会影响它在被调用方法中的值。 我建议你重写方法，以便它返回指向新创建节点的指针，并将此指针指定给本地temp的left和right 。 这样一来，变化就会传播开来。
另一种输出树的方式：
public void inorder() { inorder(root); } protected void visit(BSTNode p) { System.out.println("Node: " + p.el + "Left Side:" + (p.left!=null?p.left.el:"null") + "Right Side:" + (p.right!=null?p.right.el:"null")); }
我已经更改了BinaryTree类，如下所示。 特别是请参见createNode方法的更改。
如前所述，该问题的一个问题是，当它作为参数传递给createNode方法时，您的引用不会持久存在。 这种变化只是局部的。 在创建节点时，您需要在方法本身中返回显式节点引用。
public Node createNode() { Integer value = getData(); Node temp = new Node(value); if(head==null) { head = temp; } System.out.println("Do you want to add left branch on node("+value+")? Enter y/n"); if(input.next().charAt(0)=='y') { temp.left=createNode(); } System.out.println("Do you want to add right branch on node("+value+")? Enter y/n"); if(input.next().charAt(0)=='y') { temp.right=createNode(); } return temp; }
以下是结果输出：
Basic operations on a tree: 1. Create tree 2. Insert 3. Search value 4. print list Else. Exit Choice:1 Basic operations on a tree: 1. Create tree 2. Insert 3. Search value 4. print list Else. Exit Choice:2 Enter the value to insert: 10 Do you want to add left branch on node(10)? Enter y/n y Enter the value to insert: 20 Do you want to add left branch on node(20)? Enter y/n n Do you want to add right branch on node(20)? Enter y/n n Do you want to add right branch on node(10)? Enter y/n y Enter the value to insert: 30 Do you want to add left branch on node(30)? Enter y/n n Do you want to add right branch on node(30)? Enter y/n n Basic operations on a tree: 1. Create tree 2. Insert 3. Search value 4. print list Else. Exit Choice:4 20 10 30
我希望这对以后的人有所帮助（即使这已经晚了3年……）。 我今天刚开始学习二叉树。 我实际上计划将此作为执行更多相关任务的基础！
我更改了createNode方法，以便它可以工作：
public Node 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') { newnode.left = createNode(newnode.left, value); } System.out.println("If right child exits for ("+value+") enter y else n"); if(input.next().charAt(0) == 'y') { newnode.right = createNode(newnode.right, value); } return newnode; }