java平衡二叉树
A. 用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();
}
}
B. 如何用java实现二叉树
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);
}
}
输出结果：
前序遍历：
1 2 4 8 9 5 3 6 7
中序遍历：
8 4 9 2 5 1 6 3 7
后序遍历：
8 9 4 5 2 6 7 3 1
C. 用Java怎么实现平衡树动态演示
publicclasstreenode1{//二叉树的结点类
publicstringdata;//数据元数
publictreenode1left,right;//指向左,右孩子结点的链
publictreenode1(){
this("?");
}
publictreenode1(stringd){//构造有值结点
data=d;
left=right=null;
}
publicvoidpreorder(treenode1p){//先根次序遍历二叉树
if(p!=null){
system.out.print(p.data+"");
preorder(p.left);
preorder(p.right);
}
}
publicvoidinorder(treenode1p){//中根次序遍历二叉树
if(p!=null){inorder(p.left);
system.out.print(p.data+"");
inorder(p.right);
}
}
publicvoidpostorder(treenode1p){//后根次序遍历二叉树
if(p!=null){postorder(p.left);
postorder(p.right);
system.out.print(p.data+"");
}
}
}
D. 用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();
//
}
}
E. java TreeSet集合内部数据结构有没有经过平衡二叉树的转换
TreeSet集合底层代码本就是自平衡二叉树的结构
F. Java中处理稀疏矩阵时，是否可以将每一行存为一个平衡二叉树，然后将值（num）和对应坐标（i、j）保存。
从数据结构上讲没有问题，但是这么做没有意义……就用最简单的一位数组式二叉树表示生成的二叉树，你还需要一个二维数组或者map来存放坐标。加上编译和反编译的算法，资源损耗明显比锯齿数组打……
G. 红黑树和平衡二叉树 区别
红黑树和平衡二叉树的主要区别如下：
平衡二叉树（AVL）树是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而的英文旋转非常耗时的。所以平衡二叉树（AVL）适合用于插入与删除次数比较少，但查找多的情况。
红黑树在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log
n)。所以红黑树适用于搜索，插入，删除操作较多的情况。
(7)java平衡二叉树扩展阅读：
平衡二叉树在Windows
NT内核中广泛存在。
红黑树的应用：
1、在C
++的STL中，地图和集都是用红黑树实现的；
2、着名的Linux的的进程调度完全公平调度程序，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
3、IO多路复用的epoll的的的实现采用红黑树组织管理的sockfd，以支持快速的增删改查；
4、Nginx的的的中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；
5、Java中的TreeMap中的实现。
参考资料：
网络-平衡二叉树
网络-红黑树
H. 怎样用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();
}
}
你一看就英文就知道什么意思了，应该可以理解了
这个二叉树捉摸不透就别琢磨了，开放中一般用不上
}
I. java中的二叉树是什么意思
二叉树的相关操作，包括创建，中序、先序、后序（递归和非递归），其中重点的是java在先序创建二叉树和后序非递归遍历的的实现。