Ⅰ java中常见的八种数据结构
Java中常见数据结构
Java中常见的八种数据结构分别是哈希表、队列、树、Java8中HashMap的红黑树、堆、数组、栈以及链表。这八种数据结构各有特色，适用于不同的应用场景。
哈希表，一种高效的数据结构，通过哈希函数将任意长度的输入转为定长的输出，实现快速查询、插入、删除。在JDK8中，经典的HashMap结合了数组、链表和红黑树，进一步优化了性能。
队列，类似于水管，两端分别进行入水和出水操作，适用于需要按顺序处理任务的场景。队列允许在前端删除元素，在后端插入元素，遵循先进先出的原则。
树是一种非线性数据结构，由多个节点组成，具有层次关系。在Java中，树可以用于实现复杂的数据组织和检索。
Java8中HashMap的红黑树，实质上是一种平衡二叉树，通过颜色约束来保持树的平衡，确保了搜索、插入和删除操作的时间复杂度为O(log n)。
数组是一种线性数据结构，存储相同类型的数据在连续的空间中，查询速度快，但创建时大小固定，无法动态调整大小，且只支持同类型数据。
栈，类比为水桶，遵循先进后出的原则，适合用于实现函数调用、表达式求值等场景。
链表，是一种线性数据结构，数据元素以链式存储方式存在，通过引用连接相邻元素。链表在插入和删除元素时更加灵活，但查找效率较低。
图，由节点和边构成，节点之间通过边连接，用于表示任意两个元素之间的关系。图可以用于模拟复杂的网络结构和数据关系。
了解这些数据结构的特性和应用场景，对提升编程技能和解决实际问题具有重要意义。在不断学习和实践中，逐步掌握和应用这些数据结构，将有助于成为一名优秀的Java开发者。
Ⅱ 如何求二叉树最接近的共同祖先
【以下转载自网络】
首先，题目中没有明确说明节点的结构，所以这里分这两种情况讨论：
1. 二叉树节点具有父指针
在节点具有父指针的情况下，显然此二叉树就可以看成是通过父指针连接的"T"型链表，题目也就转化成查找"T"型链表的第一个公共节点。假设p，q分别为所求的两个节点，则通过遍历一遍可以知道p，q分别到根节点的长度pLen和qLen。这样就知道pLen和qLen之间长度之差，也就知道p、q到它们的第一个公共祖先节点k长度之差L。因为p，q到根节点的路径中都包含k到根节点的路径，所以pLen和qLen之差等于p、q到k的长度之差。然后，让p、q到根节点路径长度大的先向前走L，然后长度小再和大的同时向前遍历，当它们两指向同一个节点时，则那个节点即是所求。
[java] view plainprint?
/**
* 有父指针情况下，查找两个节点的最低公共节点
* @author chosen0ne
* 2011-01-18
*/
class BTree<T>{
private BTNode<T> root;
public BTree(BTNode<T> r){
this.root=r;
}
/**
* 查找两个节点的最低公共祖先节点
* @param p
* @param q
* @return BTNode<T> 最低公共祖先节点，没有找到返回null
*/
public BTNode<T> findLowestAncestor(BTNode<T> p,BTNode<T> q){
if(p==null||q==null)
throw new NullPointerException();
int pLen=0,qLen=0;//p，q两个节点到根节点的路径长度
//计算p到根节点的长度
for(BTNode<T> ancestor=p.parent;ancestor!=null;ancestor=ancestor.parent)
pLen++;
//计算q到根节点的长度
for(BTNode<T> ancestor=q.parent;ancestor!=null;ancestor=ancestor.parent)
qLen++;
//如果p到根节点的长度比q长，则让p前进pLen-qLen
for(;pLen>qLen;pLen--)
p=p.parent;
//如果q到根节点的长度比p长，则让q前进qLen-pLen
for(;qLen>pLen;qLen--)
q=q.parent;
//此时，p和q到根节点的长度相同。假设k是最近的公共节点，则p和q到k的长度相同
//p和q按照相同步长1向前遍历，如果存在公共节点则p和去会同时指向它
while(q!=null&&p!=null&&p!=q){
q=q.parent;
p=p.parent;
}
if(p==q)
return p;
return null;
}
/**
* 测试方法，在t中查找a，b的最低公共祖先节点
* @param t
* @param a
* @param b
*/
private static<T> void test(BTree<T> t, BTNode<T> a, BTNode<T> b){
BTree.BTNode<T> p=t.findLowestAncestor(b,a);
if(p!=null)
System.out.println(a.data+","+b.data+"的最低公共祖先节点是 ："+p.data);
else
System.out.println(a.data+","+b.data+"没有公共祖先节点");
}
public static void main(String[] arg){
/* 构造如下二叉树
a
/ /
b c
/ / / /
d e f g
*/
BTree.BTNode<String> g=new BTree.BTNode().data("g");
BTree.BTNode<String> f=new BTree.BTNode().data("f");
BTree.BTNode<String> e=new BTree.BTNode().data("e");
BTree.BTNode<String> d=new BTree.BTNode().data("d");
BTree.BTNode<String> c=new BTree.BTNode().data("c").left(f).right(g);
f.parent(c);
g.parent(c);
BTree.BTNode<String> b=new BTree.BTNode().data("b").left(d).right(e);
d.parent(b);
e.parent(b);
BTree.BTNode<String> a=new BTree.BTNode().data("a").left(b).right(c);
b.parent(a);
c.parent(a);
BTree<String> t=new BTree<String>(a);
test(t,c,f);
}
static class BTNode<T>
{
BTNode<T> left;
BTNode<T> right;
BTNode<T> parent;
T data;
public BTNode(){}
public BTNode(BTNode<T> l,BTNode<T> r,BTNode<T> p,T d){
this.left=l;
this.right=r;
this.parent=p;
this.data=d;
}
BTNode<T> left(BTNode<T> l){
this.left=l;
return this;
}
BTNode<T> right(BTNode<T> r){
this.right=r;
return this;
}
BTNode<T> parent(BTNode<T> p){
this.parent=p;
return this;
}
BTNode<T> data(T d){
this.data=d;
return this;
}
}
}
2.二叉树节点不具有父指针
这种情况下，必须通过遍历查找一个节点的祖先集合，然后比较两个节点的祖先集合就可以找到最低的那个。这里采用后序遍历，并传入一个栈记录该节点的祖先节点。在每次访问一个节点时，先把这个节点压入栈，然后判断该节点是不是要查找的那个节点，如果是返回。接着查找它的左子树和右子树，当要查找的节点在它的左右子树中则返回。然后判断该节点与栈顶节点是否相同，是则弹出栈顶元素。这是因为相同就代表了在访问它的左右子树时没有添加新的节点，也就是说要查找的那个节点不在它的左右子树中，则该节点也就是不是要查找的节点的祖先。
[java] view plainprint?
import java.util.ArrayList;
/**
* 没有父指针情况下，查找两个节点的最低公共节点
* @author chosen0ne
* 2011-01-18
*/
class BTree<T>
{
private BTNode<T> root;
public BTree(BTNode<T> r){
this.root=r;
}
/**
* 查找两个节点的最低公共祖先节点
* @param p
* @param q
* @return BTNode<T> 最低公共祖先节点，没有找到返回null
*/
public BTNode<T> findLowestAncestor(BTNode<T> p,BTNode<T> q){
if(p==null||q==null)
throw new NullPointerException();
ArrayList<BTNode<T>> sp=new ArrayList<BTNode<T>>();
ArrayList<BTNode<T>> sq=new ArrayList<BTNode<T>>();
travalPostOrder(root,p,sp);
travalPostOrder(root,q,sq);
//祖先栈中，以先后顺序存储，所以这里倒序来遍历以便找到最低的那个祖先节点
for(int i=sp.size()-1;i>=0;i--)
for(int j=sq.size()-1;j>=0;j--)
if(sp.get(i)==sq.get(j))
return sp.get(i);
return null;
}
/**
* 后序遍历二叉树，进行节点的搜索，当搜索成功时，将该节点的所有祖先存入栈中
* @param n 遍历的节点
* @param p 欲搜索的节点
* @param stack 存储祖先节点的栈，这里使用ArrayList，因为后续查找最低公共祖先时需要遍历所有元素
* @return boolean 是否搜索到该节点
*/
private boolean travalPostOrder(BTNode<T> n,BTNode<T> p,ArrayList<BTNode<T>> stack){
if(n!=null){
stack.add(n);
if(n==p)
return true;
if(travalPostOrder(n.left,p,stack))
return true;
if(travalPostOrder(n.right,p,stack))
return true;
int lastIndex=stack.size()-1;
//如果搜索完n的左右子树后，栈顶还是n，则代表n不是p的祖先节点，所以将n从栈中删除
if(n==stack.get(lastIndex)){
stack.remove(lastIndex);
}
}
return false;
}
/**
* 测试方法，在t中查找a，b的最低公共祖先节点
* @param t
* @param a
* @param b
*/
private static<T> void test(BTree<T> t, BTNode<T> a, BTNode<T> b){
BTree.BTNode<T> p=t.findLowestAncestor(b,a);
if(p!=null)
System.out.println(a.data+","+b.data+"的最低公共祖先节点是 ："+p.data);
else
System.out.println(a.data+","+b.data+"没有公共祖先节点");
}
public static void main(String[] arg){
/* 构造如下二叉树
a
/ /
b c
/ / / /
d e f g
*/
BTree.BTNode<String> g=new BTree.BTNode().data("g");
BTree.BTNode<String> f=new BTree.BTNode().data("f");
BTree.BTNode<String> e=new BTree.BTNode().data("e");
BTree.BTNode<String> d=new BTree.BTNode().data("d");
BTree.BTNode<String> c=new BTree.BTNode().data("c").left(f).right(g);
BTree.BTNode<String> b=new BTree.BTNode().data("b").left(d).right(e);
BTree.BTNode<String> a=new BTree.BTNode().data("a").left(b).right(c);
BTree<String> t=new BTree<String>(a);
test(t,a,b);
}
static class BTNode<T>
{
BTNode<T> left;
BTNode<T> right;
T data;
public BTNode(){}
public BTNode(BTNode<T> l,BTNode<T> r,T d){
this.left=l;
this.right=r;
this.data=d;
}
BTNode<T> left(BTNode<T> l){
this.left=l;
return this;
}
BTNode<T> right(BTNode<T> r){
this.right=r;
return this;
}
BTNode<T> data(T d){
this.data=d;
return this;
}
}
}
在没有父指针时，还可以给每个节点添加一个计数器，在进入一个节点时加1，在退出该节点时减1。访问该节点时，如果要查找的节点在该节点的子树中，则返回。实际上，这和上面的算法思想是一样的，只是实现不同。
这两种算法的时间复杂度都是O(n)，效率不错。没有父指针的情况，空间复杂度也是O(n)。