Ⅰ 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)。