234树java

⑴ 树在java中的应用有哪些

首先：树与线性表、栈、队列等线性结构不同，树是一种非线性结构。一棵树只有一个根节点，如果一棵树有了多个根节点，那它已经不再是一棵树了，而是多棵树的集合，也被称为森林。
其次：java中树的应用主要有：菜单树，还有权限树，商品分类列表也是树结构。

⑵ 用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();

//
}

}

⑶ 二叉树的java实现与几种遍历

二叉树的定义

二叉树(binary tree)是结点的有限集合，这个集合或者空，或者由一个根及两个互不相交的称为这个根的左子树或右子树构成.

从定义可以看出，二叉树包括：1.空树 2.只有一个根节点 3.只有左子树 4.只有右子树 5.左右子树都存在 有且仅有这5种表现形式

二叉树的遍历分为三种：前序遍历 中序遍历 后序遍历

• 前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树

• 中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树

• 后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点

其中前，后，中指的是每次遍历时候的根节点被遍历的顺序

具体实现看下图：

⑷ java如何创建一颗二叉树

计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。

树是由一个或多个结点组成的有限集合，其中：

⒈必有一个特定的称为根(ROOT)的结点；

二叉树
⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。

树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树

1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为2;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。

2.树的深度——组成该树各结点的最大层次。

3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；

4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。

树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如右图可写成如下形式：
二叉树
(a( b(d,e), c( f( ,g(h,i) ), )))

⑸ 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实现二叉树

我有很多个(假设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();
}
}