二叉树的java实现
❶ 怎样用java来体现二叉树（顺便加上注释）
二叉树，和数据库的B树操作流程是一样的，例如：有如下字段
F,C,B,H,K,I；
如果要形成二叉树的话，则，首先取第一个数据作为根节点，所以，现在是 F ，如果字段比根节点小，则保存在左子树，如果比根节点大或者等于根节点则保存在右子树，最后按左---根-----右输出所以数据。
所以，实现的关键就是在于保存的数据上是否存在大小比较功能，而String类中compareTo()有这个能力,节点类要保存两类数据，左节点，右节点
class Node
{
private String data;
private Node left;
private Node right;
public Node (String data){
this.data = data;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right){
this.right = right;
}
public String getDate() {
return this.data;
}
public Node getLeft(){
return this.left;
}
public Node getRight(){
return this.right;
}
public void addNode(Node newNode){
if(this.data.compareTo(newNode.data)>=0) {
if(this.left == null){
this.left = newNode;
}else {
this.left.addNode(newNode);
}
}else {
if(this.right == null) {
this.right = newNode;
} else {
this.right.addNode(newNode);
}
}
}
public void printNode(){
if(this.left!= null){
this.left.printNode();
}
System.out.println(this.data);
if(this.right != null){
this.right.printNode();
}
}
}
class BinaryTree
{
private Node root = null;
public void add(String data) {
Node newNode = new Node(data);
if(this.root == null) {
this.root = newNode;
}else{
this.root.addNode(newNode);
}
}
public void print() {
this.root.printNode();
}
}
public class Hello
{
public static void main (String args[]) {
BinaryTree link = new BinaryTree();
link.add("F");
link.add("C");
link.add("B");
link.add("H");
link.add("K");
link.add("I");
link.print();
}
}
你一看就英文就知道什么意思了，应该可以理解了
这个二叉树捉摸不透就别琢磨了，开放中一般用不上
}
❷ java 构建二叉树
首先我想问为什么要用LinkedList 来建立二叉树呢? LinkedList 是线性表,
树是树形的, 似乎不太合适。
其实也可以用数组完成，而且效率更高.
关键是我觉得你这个输入本身就是一个二叉树啊，
String input = "ABCDE F G";
节点编号从0到8. 层次遍历的话:
对于节点i.
leftChild = input.charAt(2*i+1); //做子树
rightChild = input.charAt(2*i+2);//右子树
如果你要将带有节点信息的树存到LinkedList里面, 先建立一个节点类:
class Node{
public char cValue;
public Node leftChild;
public Node rightChild;
public Node(v){
this.cValue = v;
}
}
然后遍历input,建立各个节点对象.
LinkedList tree = new LinkedList();
for(int i=0;i< input.length;i++)
LinkedList.add(new Node(input.charAt(i)));
然后为各个节点设置左右子树:
for(int i=0;i<input.length;i++){
((Node)tree.get(i)).leftChild = (Node)tree.get(2*i+1);
((Node)tree.get(i)).rightChild = (Node)tree.get(2*i+2);
}
这样LinkedList 就存储了整个二叉树. 而第0个元素就是树根，思路大体是这样吧。
❸ 用java怎么构造一个二叉树
定义一个结点类：x0dx0apublic class Node {x0dx0a private int value;x0dx0a private Node leftNode;x0dx0a private Node rightNode;x0dx0a x0dx0a public Node getRightNode() {x0dx0a return rightNode;x0dx0a }x0dx0a public void setRightNode(Node rightNode) {x0dx0a this.rightNode = rightNode;x0dx0a }x0dx0a public int getValue() {x0dx0a return value;x0dx0a }x0dx0a public void setValue(int value) {x0dx0a this.value = value;x0dx0a }x0dx0a public Node getLeftNode() {x0dx0a return leftNode;x0dx0a }x0dx0a public void setLeftNode(Node leftNode) {x0dx0a this.leftNode = leftNode;x0dx0a }x0dx0a x0dx0a}x0dx0a x0dx0a初始化结点树：x0dx0apublic void initNodeTree()x0dx0a {x0dx0a int nodeNumber;x0dx0a HashMap
❹ 用java怎么构造一个二叉树
二叉树的相关操作，包括创建，中序、先序、后序（递归和非递归），其中重点的是java在先序创建二叉树和后序非递归遍历的的实现。
package com.algorithm.tree;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;
public class Tree {
private Node root;
public Tree() {
}
public Tree(Node root) {
this.root = root;
}
//创建二叉树
public void buildTree() {
Scanner scn = null;
try {
scn = new Scanner(new File("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
root = createTree(root,scn);
}
//先序遍历创建二叉树
private Node createTree(Node node,Scanner scn) {
String temp = scn.next();
if (temp.trim().equals("#")) {
return null;
} else {
node = new Node((T)temp);
node.setLeft(createTree(node.getLeft(), scn));
node.setRight(createTree(node.getRight(), scn));
return node;
}
}
//中序遍历(递归)
public void inOrderTraverse() {
inOrderTraverse(root);
}
public void inOrderTraverse(Node node) {
if (node != null) {
inOrderTraverse(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse(node.getRight());
}
}
//中序遍历(非递归)
public void nrInOrderTraverse() {
Stack<Node> stack = new Stack<Node>();
Node node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
System.out.println(node.getValue());
node = node.getRight();
}
}
//先序遍历(递归)
public void preOrderTraverse() {
preOrderTraverse(root);
}
public void preOrderTraverse(Node node) {
if (node != null) {
System.out.println(node.getValue());
preOrderTraverse(node.getLeft());
preOrderTraverse(node.getRight());
}
}
//先序遍历（非递归）
public void nrPreOrderTraverse() {
Stack<Node> stack = new Stack<Node>();
Node node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
System.out.println(node.getValue());
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
node = node.getRight();
}
}
//后序遍历(递归)
public void postOrderTraverse() {
postOrderTraverse(root);
}
public void postOrderTraverse(Node node) {
if (node != null) {
postOrderTraverse(node.getLeft());
postOrderTraverse(node.getRight());
System.out.println(node.getValue());
}
}
//后续遍历(非递归)
public void nrPostOrderTraverse() {
Stack<Node> stack = new Stack<Node>();
Node node = root;
Node preNode = null;//表示最近一次访问的节点
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.peek();
if (node.getRight() == null || node.getRight() == preNode) {
System.out.println(node.getValue());
node = stack.pop();
preNode = node;
node = null;
} else {
node = node.getRight();
}
}
}
//按层次遍历
public void levelTraverse() {
levelTraverse(root);
}
public void levelTraverse(Node node) {
Queue<Node> queue = new LinkedBlockingQueue<Node>();
queue.add(node);
while (!queue.isEmpty()) {
Node temp = queue.poll();
if (temp != null) {
System.out.println(temp.getValue());
queue.add(temp.getLeft());
queue.add(temp.getRight());
}
}
}
}
//树的节点
class Node {
private Node left;
private Node right;
private T value;
public Node() {
}
public Node(Node left,Node right,T value) {
this.left = left;
this.right = right;
this.value = value;
}
public Node(T value) {
this(null,null,value);
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
}
测试代码：
package com.algorithm.tree;
public class TreeTest {
/**
* @param args
*/
public static void main(String[] args) {
Tree tree = new Tree();
tree.buildTree();
System.out.println("中序遍历");
tree.inOrderTraverse();
tree.nrInOrderTraverse();
System.out.println("后续遍历");
//tree.nrPostOrderTraverse();
tree.postOrderTraverse();
tree.nrPostOrderTraverse();
System.out.println("先序遍历");
tree.preOrderTraverse();
tree.nrPreOrderTraverse();
//
}
}
❺ 用java实现二叉树
我有很多个(假设10万个)数据要保存起来，以后还需要从保存的这些数据中检索是否存在某
个数据，（我想说出二叉树的好处，该怎么说呢？那就是说别人的缺点），假如存在数组中，
那么，碰巧要找的数字位于99999那个地方，那查找的速度将很慢，因为要从第1个依次往
后取，取出来后进行比较。平衡二叉树（构建平衡二叉树需要先排序，我们这里就不作考虑
了）可以很好地解决这个问题，但二叉树的遍历（前序，中序，后序）效率要比数组低很多，
public class Node {
public int value;
public Node left;
public Node right;
public void store(intvalue)
right.value=value;
}
else
{
right.store(value);
}
}
}
public boolean find(intvalue)
{
System.out.println("happen" +this.value);
if(value ==this.value)
{
return true;
}
else if(value>this.value)
{
if(right ==null)returnfalse;
return right.find(value);
}else
{
if(left ==null)returnfalse;
return left.find(value);
}
}
public void preList()
{
System.out.print(this.value+ ",");
if(left!=null)left.preList();
if(right!=null) right.preList();
}
public void middleList()
{
if(left!=null)left.preList();
System.out.print(this.value+ ",");
if(right!=null)right.preList();
}
public void afterList()
{
if(left!=null)left.preList();
if(right!=null)right.preList();
System.out.print(this.value+ ",");
}
public static voidmain(String [] args)
{
int [] data =new int[20];
for(inti=0;i<data.length;i++)
{
data[i] = (int)(Math.random()*100)+ 1;
System.out.print(data[i] +",");
}
System.out.println();
Node root = new Node();
root.value = data[0];
for(inti=1;i<data.length;i++)
{
root.store(data[i]);
}
root.find(data[19]);
root.preList();
System.out.println();
root.middleList();
System.out.println();
root.afterList();
}
}
❻ 二叉树的java实现与几种遍历
二叉树的定义
二叉树(binary tree)是结点的有限集合，这个集合或者空，或者由一个根及两个互不相交的称为这个根的左子树或右子树构成.
从定义可以看出，二叉树包括：1.空树 2.只有一个根节点 3.只有左子树 4.只有右子树 5.左右子树都存在 有且仅有这5种表现形式
二叉树的遍历分为三种：前序遍历 中序遍历 后序遍历
前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树
中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树
后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点
其中前，后，中指的是每次遍历时候的根节点被遍历的顺序
具体实现看下图：
❼ java二叉树的顺序表实现
做了很多年的程序员，觉得什么树的设计并不是非常实用。二叉树有顺序存储，当一个insert大量同时顺序自增插入的时候，树就会失去平衡。树的一方为了不让塌陷，会增大树的高度。性能会非常不好。以上是题外话。分析需求在写代码。
import java.util.List;
import java.util.LinkedList;
public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private static List<Node> nodeList = null;
private static class Node {
Node leftChild;
Node rightChild;
int data;
Node(int newData) {
leftChild = null;
rightChild = null;
data = newData;
}
}
// 创建二叉树
public void createBintree() {
nodeList = new LinkedList<Node>();
// 将数组的值转换为node
for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
nodeList.add(new Node(array[nodeIndex]));
}
// 对除最后一个父节点按照父节点和孩子节点的数字关系建立二叉树
for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
}
// 最后一个父节点
int lastParentIndex = array.length / 2 - 1;
// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);
// 如果为奇数，建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);
}
}
// 前序遍历
public static void preOrderTraverse(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}
// 中序遍历
public static void inOrderTraverse(Node node) {
if (node == null) {
return;
}
inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}
// 后序遍历
public static void postOrderTraverse(Node node) {
if (node == null) {
return;
}
postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
}
public static void main(String[] args) {
Bintrees binTree = new Bintrees();
binTree.createBintree();
Node root = nodeList.get(0);
System.out.println("前序遍历：");
preOrderTraverse(root);
System.out.println();
System.out.println("中序遍历：");
inOrderTraverse(root);
System.out.println();
System.out.println("后序遍历：");
postOrderTraverse(root);
}
}
❽ 说明生活中遇到的二叉树，用java实现二叉树. (求源码，要求简练、易懂。非常满意会额外加分)
import java.util.ArrayList;
// 树的一个节点
class TreeNode {
Object _value = null; // 他的值
TreeNode _parent = null; // 他的父节点，根节点没有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子节点
public TreeNode( Object value, TreeNode parent ){
this._parent = parent;
this._value = value;
}
public TreeNode getParent(){
return _parent;
}
public String toString() {
return _value.toString();
}
}
public class Tree {
// 给出宽度优先遍历的值数组，构建出一棵多叉树
// null 值表示一个层次的结束
// "|" 表示一个层次中一个父亲节点的孩子输入结束
// 如：给定下面的值数组：
// { "root", null, "left", "right", null }
// 则构建出一个根节点，带有两个孩子("left","right")的树
public Tree( Object[] values ){
// 创建根
_root = new TreeNode( values[0], null );
// 创建下面的子节点
TreeNode currentParent = _root; // 用于待创建节点的父亲
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父亲的第几个儿子
//TreeNode lastNode = null; // 最后一个创建出来的TreeNode，用于找到他的父亲
for ( int i = 2; i < values.length; i++ ){
// 如果null ,表示下一个节点的父亲是当前节点的父亲的第一个孩子节点
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
}
// 表示一个父节点的所有孩子输入完毕
if ( values[i].equals("|") ){
if ( currentChildIndex+1 < currentParent._childList.size() ){
currentChildIndex++;
currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);
}
continue;
}
TreeNode child = createChildNode( currentParent, values[i] );
}
}
TreeNode _root = null;
public TreeNode getRoot(){
return _root;
}
/**
// 按宽度优先遍历，打印出parent子树所有的节点
private void printSteps( TreeNode parent, int currentDepth ){
for ( int i = 0; i < parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
System.out.println(currentDepth+":"+child);
}
if ( parent._childList.size() != 0 ) System.out.println(""+null);// 为了避免叶子节点也会打印null
//打印 parent 同层的节点的孩子
if ( parent._parent != null ){ // 不是root
int i = 1;
while ( i < parent._parent._childList.size() ){// parent 的父亲还有孩子
TreeNode current = (TreeNode)parent._parent._childList.get(i);
printSteps( current, currentDepth );
i++;
}
}
// 递归调用，打印所有节点
for ( int i = 0; i < parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
printSteps( child, currentDepth+1 );
}
}
// 按宽度优先遍历，打印出parent子树所有的节点
public void printSteps(){
System.out.println(""+_root);
System.out.println(""+null);
printSteps(_root, 1 );
}**/
// 将给定的值做为 parent 的孩子，构建节点
private TreeNode createChildNode( TreeNode parent, Object value ){
TreeNode child = new TreeNode( value , parent );
parent._childList.add( child );
return child;
}
public static void main(String[] args) {
Tree tree = new Tree( new Object[]{ "root", null,
"left", "right", null,
"l1","l2","l3", "|", "r1","r2",null } );
//tree.printSteps();
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(1) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(2) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(1) );
}
}
看一下吧！这是在网上找的一个例子！看对你有没有帮助！
❾ 用java怎么构造一个二叉树呢
二叉树的相关操作，包括创建，中序、先序、后序（递归和非递归），其中重点的是java在先序创建二叉树和后序非递归遍历的的实现。
package com.algorithm.tree;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;
public class Tree<T> {
private Node<T> root;
public Tree() {
}
public Tree(Node<T> root) {
this.root = root;
}
//创建二叉树
public void buildTree() {
Scanner scn = null;
try {
scn = new Scanner(new File("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
root = createTree(root,scn);
}
//先序遍历创建二叉树
private Node<T> createTree(Node<T> node,Scanner scn) {
String temp = scn.next();
if (temp.trim().equals("#")) {
return null;
} else {
node = new Node<T>((T)temp);
node.setLeft(createTree(node.getLeft(), scn));
node.setRight(createTree(node.getRight(), scn));
return node;
}
}
//中序遍历(递归)
public void inOrderTraverse() {
inOrderTraverse(root);
}
public void inOrderTraverse(Node<T> node) {
if (node != null) {
inOrderTraverse(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse(node.getRight());
}
}
//中序遍历(非递归)
public void nrInOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
System.out.println(node.getValue());
node = node.getRight();
}
}
//先序遍历(递归)
public void preOrderTraverse() {
preOrderTraverse(root);
}
public void preOrderTraverse(Node<T> node) {
if (node != null) {
System.out.println(node.getValue());
preOrderTraverse(node.getLeft());
preOrderTraverse(node.getRight());
}
}
//先序遍历（非递归）
public void nrPreOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
System.out.println(node.getValue());
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
node = node.getRight();
}
}
//后序遍历(递归)
public void postOrderTraverse() {
postOrderTraverse(root);
}
public void postOrderTraverse(Node<T> node) {
if (node != null) {
postOrderTraverse(node.getLeft());
postOrderTraverse(node.getRight());
System.out.println(node.getValue());
}
}
//后续遍历(非递归)
public void nrPostOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
Node<T> preNode = null;//表示最近一次访问的节点
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.peek();
if (node.getRight() == null || node.getRight() == preNode) {
System.out.println(node.getValue());
node = stack.pop();
preNode = node;
node = null;
} else {
node = node.getRight();
}
}
}
//按层次遍历
public void levelTraverse() {
levelTraverse(root);
}
public void levelTraverse(Node<T> node) {
Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
queue.add(node);
while (!queue.isEmpty()) {
Node<T> temp = queue.poll();
if (temp != null) {
System.out.println(temp.getValue());
queue.add(temp.getLeft());
queue.add(temp.getRight());
}
}
}
}
//树的节点
class Node<T> {
private Node<T> left;
private Node<T> right;
private T value;
public Node() {
}
public Node(Node<T> left,Node<T> right,T value) {
this.left = left;
this.right = right;
this.value = value;
}
public Node(T value) {
this(null,null,value);
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
}
测试代码：
package com.algorithm.tree;
public class TreeTest {
/**
* @param args
*/
public static void main(String[] args) {
Tree<Integer> tree = new Tree<Integer>();
tree.buildTree();
System.out.println("中序遍历");
tree.inOrderTraverse();
tree.nrInOrderTraverse();
System.out.println("后续遍历");
//tree.nrPostOrderTraverse();
tree.postOrderTraverse();
tree.nrPostOrderTraverse();
System.out.println("先序遍历");
tree.preOrderTraverse();
tree.nrPreOrderTraverse();
//
}
}