《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 6-1圖的基本概念與鄰接表和矩陣實(shí)現(xiàn)的實(shí)現(xiàn)10-27

圖(Graph)的數(shù)學(xué)定義G=(V,E,)V：頂點(diǎn)(vertex、node)的集合例如，V={A,B,C,D}E：邊(edge、arc)的集合例如，E={e1,e2,e3,e4}：E{<v1,v2>|v1,v2V}例如：={(e1,<A,B>),(e2,<B,C>),(e3,<C,D>),(e4,<D,B>)}圖的數(shù)據(jù)結(jié)構(gòu)課的定義G=(V,E)V：頂點(diǎn)的集合例如，V={A,B,C,D}E：邊的集合例如，E={<A,B>,<B,C>,<C,D>,<D,B>}有向圖、無向圖EACBDBCAFEDdirectedgraphundirectedgraphACDFEB鄰接點(diǎn)(adjacentvertex)、度(degree)EACBDin-degreeout-degree子圖(subgraph)EACBDCBD沒有嚴(yán)格的定義，一般指：稠密圖：|E|=Θ(|V|2)稀疏圖：非稠密圖，或者|E|<<|V|2(遠(yuǎn)遠(yuǎn)小于)稀疏圖(sparsegraph)、稠密圖(densegraph)路徑(path)和路徑長(zhǎng)度(pathlength)A->B->C->DA->E->C->DEACBD簡(jiǎn)單路徑(simplepath)A->B->C->D√A->E->C->D->B->C->DEACBDBACDFE連通圖(connectedgraph)a、連通圖BACDFEb、非連通圖強(qiáng)連通圖(stronglyconnectedgraph)a、強(qiáng)連通圖b、非強(qiáng)連通圖ABECDABECDBACDFEBACDFE生成樹(spanningtree)圖的規(guī)模兩個(gè)參數(shù)：V、E有向圖：|E|≤|V|*(|V|-1)=O(|V|2)無向圖：|E|≤(|V|*(|V|-1))/2=O(|V|2)圖的基本內(nèi)容本章的主要內(nèi)容：圖的存儲(chǔ)圖的遍歷及應(yīng)用有向圖的拓?fù)渑判騿栴}帶權(quán)有向圖的最短路徑問題帶權(quán)無向圖的最小生成樹問題圖的存儲(chǔ)G=(V,E)V：頂點(diǎn)的集合。例如，V={A,B,C,D}E：邊的集合。例如，E={<A,B>,<B,C>,<C,D>,<D,B>,<D,A>}兩種觀點(diǎn)：把E視為頂點(diǎn)之間的關(guān)系，則存儲(chǔ)V和V上的關(guān)系(即E)把V和E視為2個(gè)集合，則分別存儲(chǔ)V和E，再存儲(chǔ)V和E之間的鄰接關(guān)系無向圖-鄰接矩陣(adjacencymatrix)BACDFEABCDEFABCDEF010010100011000101001001110000011100012345012345010010100011000101001001110000011100012345ABCDEF無向圖-鄰接表(adjacencylist)鄰接表：使用線性表存儲(chǔ)鄰接點(diǎn)01234514043525011253BACDFE鏈表中的數(shù)字是頂點(diǎn)的編號(hào)。1條邊存了2次012345ABCDEFlist:鏈表無向圖-鄰接多重表(adjacencymultilist)例aecbd^^^^^1234acdb5e121434323552課堂練習(xí)V1V2V3V4V51、鄰接矩陣2、鄰接表3、鄰接多重表ABECD有向圖-鄰接矩陣ABCDEABCDE010010010000010110000010001234ABCDEABECD012341430122有向圖-鄰接表01234ABCDEABECD320030123414有向圖-逆鄰接表(inverseadjacencylist)01234ABCDE有向圖-十字鏈表ABCABC∧0121∧02∧

∧20∧

∧012V2V1V4V31、鄰接矩陣2、鄰接表3、十字鏈表課堂練習(xí)帶權(quán)重有向圖-鄰接矩陣ABECD9876543ABCDEABCDE987654301234ABCDE帶權(quán)重有向圖-鄰接表01234ABCDEABECD9876543012341,94,83,60,51,42,32,7總結(jié)鄰接矩陣比較適合稠密圖，空間復(fù)雜度O(|V|2)鄰接表比較適合稀疏圖，空間復(fù)雜度O(|V|+|E|)無論是鄰接矩陣還是鄰接表，邊都使用了頂點(diǎn)的下標(biāo)(引用)：簡(jiǎn)單、易行改變了頂點(diǎn)的編號(hào)必須改變鄰接矩陣和鄰接表也可以考慮其它的數(shù)據(jù)結(jié)構(gòu)：例如Map等圖的類型public

enumGraphKind{

UnDirectedGraph,

DirectedGraph,

WeightedUnDirectedGraph,

WeightedDirectedGraph}圖的接口public

interfaceIGraph<T>{

publicGraphKindgetGraphKind();//圖的類型

public

intnumberOfVertices();//頂點(diǎn)的個(gè)數(shù)

public

intnumberOfEdges();//邊數(shù)

public

intindex(Tx);//值等于x的頂點(diǎn)編號(hào)，-1，表示沒找到

publicTvalue(int

v);//編號(hào)為v的頂點(diǎn)的值

public

intinDegree(int

v);//有向圖的編號(hào)為v的頂點(diǎn)的入度

public

intoutDegree(int

v);//有向圖的編號(hào)為v的頂點(diǎn)的出度

public

intdegree(int

v);//無向圖的編號(hào)為v的頂點(diǎn)的度

public

booleanaddEdge(int

u,int

v);//加入邊<u,v>

public

booleanremoveEdge(int

u,int

v);//刪除邊<u,v>

public

voidaddWeightedEdge(int

u,int

v,double

w);//設(shè)置邊<u,v>的權(quán)重

public

doublegetWeight(int

u,int

v);//獲取邊<u,v>的權(quán)重

publicIterator<Integer>iterator(int

v);//用于迭代訪問頂點(diǎn)v的鄰接點(diǎn)}基于鄰接矩陣的有向圖實(shí)現(xiàn)01234ABCDEABCDEABCDE0000000000000000000000000public

classAjacencyMatrixDirectedGraph<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateObject[]vertices;

private

int[][]edges;

private

int

e;

private

final

int

n;

publicAjacencyMatrixDirectedGraph(T[]data){

n=data.length;

vertices=newObject[n]; System.arraycopy(data,0,vertices,0,n);

edges=new

int[n][n]; }基于鄰接矩陣的有向圖實(shí)現(xiàn)

publicGraphKindgetGraphKind(){

return

graghKind; }

private

voidrangeCheck(int

v){

if(v<0||v>=n)

throw

newIndexOutOfBoundsException(); }

public

intnumberOfVertices(){

return

n; }

public

intnumberOfEdges(){

return

e; }基于鄰接矩陣的有向圖實(shí)現(xiàn)

public

intindex(Tx){

for(inti=0;i<n;i++){

if(vertices[i].equals(x)) returni; }

return-1; }

publicTvalue(int

v){ rangeCheck(v);

return

vertices[v]; }基于鄰接矩陣的有向圖實(shí)現(xiàn)

public

intinDegree(int

v){ rangeCheck(v);

int

count=0;

for(int

i=0;i<n;++i)

count+=edges[i][v];

return

count; }

public

intoutDegree(int

v){ rangeCheck(v);

int

count=0;

for(int

i=0;i<n;++i)

count+=edges[v][i];

return

count; }

public

intdegree(int

v){

throw

newUnsupportedOperationException(); }ABCDEABCDE0100100100000101100000100ABECD基于鄰接矩陣的有向圖實(shí)現(xiàn)

public

booleanaddEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u][v]==0){

edges[u][v]=1; ++e;

return

true; }

return

false; }ABCDEABCDE0100100100000101100000100ABECD基于鄰接矩陣的有向圖實(shí)現(xiàn)

public

booleanremoveEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u][v]!=0){

edges[u][v]=0; --e;

return

true; }

return

false; }ABCDEABCDE0100100100000101100000100ABECD基于鄰接矩陣的有向圖實(shí)現(xiàn)

public

voidaddWeightedEdge(int

u,int

v,double

w){

throw

newUnsupportedOperationException(); }

public

doublegetWeight(int

u,int

v){

throw

newUnsupportedOperationException(); }基于鄰接矩陣的有向圖實(shí)現(xiàn)

publicIterator<Integer>iterator(int

v){ rangeCheck(v);

return

newItr(v); }

private

classItrimplementsIterator<Integer>{

private

int

vertex;

private

int

curPos;

publicItr(int

v){

vertex=v; }

public

booleanhasNext(){

for(;curPos<n;curPos++){

if(edges[vertex][curPos]!=0)

break; }

return

curPos==n?false:true; }

publicIntegernext(){

return

curPos++; } }ABCDEABCDE0100100100000101100000100ABECD基于鄰接矩陣的有向圖實(shí)現(xiàn)

public

static

voidmain(String[]args){ Character[]data={'a','b','c','d','e','f'}; AjacencyMatrixDirectedGraph<Character>graph=newAjacencyMatrixDirectedGraph<>(data); System.out.println("nodes="+graph.numberOfVertices());

graph.addEdge(0,2);

graph.addEdge(1,2);

graph.addEdge(1,4);

graph.addEdge(1,5);

graph.addEdge(2,3);

graph.addEdge(3,5);

graph.addEdge(4,3);

graph.addEdge(4,5); System.out.println("edges="+graph.numberOfEdges()); System.out.println("outdegreeof1="+graph.outDegree(1)); System.out.println("indegreeof5="+graph.inDegree(5));nodes=6edges=8outdegreeof1=3indegreeof5=3基于鄰接矩陣的有向圖實(shí)現(xiàn)

graph.removeEdge(1,4); System.out.println(graph.numberOfEdges()); System.out.println("outdegreeof1="+graph.outDegree(1)); System.out.println("valueof4="+graph.value(4)); System.out.println("subscriptofc="+graph.index('c')); System.out.println("---------"); Iterator<Integer>it=graph.iterator(1);

while(it.hasNext()){ System.out.println(it.next()); } }7outdegreeof1=2valueof4=esubscriptofc=2---------25基于鄰接表的有向圖實(shí)現(xiàn)012341430122public

classLinkedListDirectedGraph2<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateObject[]vertices;

privateList<Integer>[]edges;//線性表數(shù)組，比Object[]edges更清晰一些

private

int

e;

private

final

int

n;

publicLinkedListDirectedGraph2(T[]data){

n=data.length;

vertices=newObject[n]; System.arraycopy(data,0,vertices,0,n);

//創(chuàng)建數(shù)組時(shí)必須使用具體類型。List<?>是具體類型，而List<Integer>不是

edges=(List<Integer>[])newList<?>[n];

for(int

i=0;i<n;i++)

edges[i]=newLinkedList<>(); }ABECD基于鄰接表的有向圖實(shí)現(xiàn)

public

intinDegree(int

v){ rangeCheck(v);

int

count=0;

for(int

u=0;u<n;u++){

if(edges[u].indexOf(v)!=-1) ++count; }

return

count; }

public

intoutDegree(int

v){ rangeCheck(v);

int

count=edges[v].size();

return

count; }012341430122ABECD基于鄰接表的有向圖實(shí)現(xiàn)012341430122ABECD

public

booleanaddEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u].indexOf(v)==-1){//頂點(diǎn)u的鄰接點(diǎn)是否包含頂點(diǎn)v

edges[u].add(v);//將頂點(diǎn)v添加到頂點(diǎn)u的鄰接點(diǎn)鏈表 ++e;

return

true; }

return

false; }基于鄰接表的有向圖實(shí)現(xiàn)012341430122

public

booleanremoveEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u].remove(Integer.valueOf(v))){ --e;

return

true; }

return

false; }ABECD基于鄰接表的有向圖實(shí)現(xiàn)012341430122

public

booleanremoveEdge2(int

u,int

v){//效率比較高，需要newiterator對(duì)象 rangeCheck(u); rangeCheck(v); Iterator<Integer>itr=edges[u].iterator();

while(itr.hasNext()){

int

w=itr.next();

if(w==v){

itr.remove();//利用迭代器的就地刪除 --e;

return

true; } }

return

false; }ABECD基于鄰接表的有向圖實(shí)現(xiàn)012341430122

//indexOf和remove各遍歷了一次LinkedList，效率低

public

booleanremoveEdge3(int

u,int

v){ rangeCheck(u); rangeCheck(v);

int

w=edges[u].indexOf(v);//O(n)

if(w!=-1){

edges[u].remove(w);//O(n) --e;

return

true; }

return

false; }ABECD基于鄰接表的有向圖實(shí)現(xiàn)

publicIterator<Integer>iterator(int

v){ rangeCheck(v);

return

edges[v].iterator();//使用List實(shí)現(xiàn)的迭代器 }012341430122ABECD總結(jié)1、使用鄰接矩陣，inDegree、outDegree、index是O(|V|)，addEdge和removeEdge是O(1)。2、使用鄰接表，inDegree是O(|E|)、outDegree、index是O(|V|)addEdge和removeEdge是O(|V|)。3、給出的代碼沒有實(shí)用價(jià)值，只用于體會(huì)如何實(shí)現(xiàn)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。因?yàn)槭褂庙旤c(diǎn)在數(shù)組的下標(biāo)作為頂點(diǎn)的編號(hào)，不利于增加和刪除頂點(diǎn)。帶權(quán)重有向圖-鄰接矩陣ABECD9876543ABCDEABCDE9876543如何表示2個(gè)頂點(diǎn)之間沒有邊？如果使用泛型，因?yàn)楸仨氁阅硞€(gè)引用類型參數(shù)化，所以可以使用null表示無邊如果使用基本類型，必須以某個(gè)特定值表示無邊。基于鄰接矩陣的帶權(quán)重有向圖實(shí)現(xiàn)public

classAjacencyMatrixWeightedDirectedGraph<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.WeightedDirectedGraph;

public

final

static

double

noEdge=Double.POSITIVE_INFINITY;

privateObject[]vertices;

private

double[][]edges;//這里讓權(quán)重為double

private

int

e;

private

final

int

n;

publicAjacencyMatrixWeightedDirectedGraph(T[]data){

//也可以把noEdge的值作為1個(gè)參數(shù)

n=data.length;

vertices=newObject[n]; System.arraycopy(data,0,vertices,0,n);

edges=new

double[n][n];

for(int

i=0;i<n;++i) Arrays.fill(edges[i],noEdge); }基于鄰接矩陣的帶權(quán)重有向圖實(shí)現(xiàn)

public

booleanaddEdge(int

u,int

v){

throw

newUnsupportedOperationException(); }

public

booleanremoveEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u][v]!=noEdge){

edges[u][v]=noEdge; --e;

return

true; }

return

false; }基于鄰接矩陣的帶權(quán)重有向圖實(shí)現(xiàn)

public

voidaddWeightedEdge(int

u,int

v,double

w){ rangeCheck(u); rangeCheck(v);

if(edges[u][v]==noEdge){

edges[u][v]=w; ++e;

return; }

edges[u][v]=w;//已經(jīng)有的邊，認(rèn)為是修改權(quán)重 }

public

doublegetWeight(int

u,int

v){ rangeCheck(u); rangeCheck(v);

return

edges[u][v]; }基于鄰接表的帶權(quán)重有向圖實(shí)現(xiàn)01234ABCDEABECD9876543012341,94,83,60,51,42,32,7基于鄰接表的帶權(quán)重有向圖實(shí)現(xiàn)

private

static

classPair{

int

vertex;//鄰接點(diǎn)

double

weight;//權(quán)重 Pair(int

v,double

w){

vertex=v;

weight=w; } Pair(){ } PairsetNode(int

u){

vertex=u;

return

this; }

public

booleanequals(Objecto){//List的indexOf、remove要使用

if(o

instanceofPair)

return

this.vertex==((Pair)o).vertex;

return

false; } }public

classLinkedListWeightedDirectedGraph2<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.WeightedDirectedGraph;

public

final

static

double

noEdge=Double.POSITIVE_INFINITY;

privateObject[]vertices;

privateLinkedList<Pair>[]edges;//使用數(shù)組

private

int

e;

private

final

int

n;

private

finalPairpair=newPair();//用于鏈表的indexOf和remove

publicLinkedListWeightedDirectedGraph2(T[]data){

n=data.length;

vertices=newObject[n]; System.arraycopy(data,0,vertices,0,n);

edges=(LinkedList<Pair>[])newLinkedList<?>[n];

for(int

i=0;i<n;i++)

edges[i]=newLinkedList<>(); }基于鄰接表的帶權(quán)重有向圖實(shí)現(xiàn)

public

voidaddWeightedEdge(int

u,int

v,double

w){ rangeCheck(u); rangeCheck(v); LinkedList<Pair>list=edges[u]; Iterator<Pair>it=list.iterator();

while(it.hasNext()){ Pairpair=it.next();

if(pair.vertex==v){//邊存在，認(rèn)為修改

pair.weight=w;

return; } }

list.add(newPair(v,w)); ++e; }012341,94,83,60,51,42,32,7基于鄰接表的帶權(quán)重有向圖實(shí)現(xiàn)

public

doublegetWeight(int

u,int

v){ rangeCheck(u); rangeCheck(v); Iterator<Pair>it=edges[u].iterator();

while(it.hasNext()){ Pairpair=it.next();

if(pair.vertex==v)

return

pair.weight; }

return

noEdge;//無u->v的邊，用正無窮大表示 }012341,94,83,60,51,42,32,7基于鄰接表的帶權(quán)重有向圖實(shí)現(xiàn)012341,94,83,60,51,42,32,7

public

booleanremoveEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u].remove(pair.setNode(v))){ --e;

return

true; }

return

false; }基于鄰接表的帶權(quán)重有向圖實(shí)現(xiàn)無向圖的實(shí)現(xiàn)01234514043525011253BACDFE1條邊存了2次，當(dāng)然，也可以1條邊只存1次，怎么存？addEdge(1,0)、addEdge(0,1)addEdge(1,0)、removeEdge(0,1)ABCDEFABCDEF010010100011000101001001110000011100無向圖-鄰接矩陣BACDFE012345ABCDEF對(duì)稱矩陣，只存儲(chǔ)、使用下三角部分ABCDEFABCDEF010010100011000101001001110000011100基于鄰接矩陣的無向圖實(shí)現(xiàn)public

classAjacencyMatrixUnDirectedGraph<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.UnDirectedGraph;

privateObject[]vertices;

private

int[][]edges;

private

int

e;

private

final

int

n;

publicAjacencyMatrixUnDirectedGraph(T[]data){

n=data.length;

vertices=newObject[n]; System.arraycopy(data,0,vertices,0,n);

edges=new

int[n][];//使用下三角形

for(int

i=0;i<n;i++)

edges[i]=new

int[i+1];//注意：數(shù)組的大小等于頂點(diǎn)編號(hào)+1 }

public

intdegree(int

v){ rangeCheck(v);

int

count=0;

int

i=0;

for(;i<=v;i++)

count+=edges[v][i];

for(;i<n;i++)

count+=edges[i][v];

return

count; }ABCDEFABCDEF010010100011000101001001110000011100基于鄰接矩陣的無向圖實(shí)現(xiàn)ABCDEFABCDEF010010100011000101001001110000011100

public

booleanaddEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(v>u){//保證u>v

int

tmp=u;

u=v;

v=tmp; }

if(edges[u][v]==0){

edges[u][v]=1; ++e;

return

true; }

return

false; }基于鄰接矩陣的無向圖實(shí)現(xiàn)基于鄰接矩陣的無向圖實(shí)現(xiàn)ABCDEFABCDEF010010100011000101001001110000011100

public

booleanremoveEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(v>u){//保證u>v,交換2個(gè)整數(shù)的另外的寫法

v=v^u;

u=v^u;

v=v^u; }

if(edges[u][v]!=0){

edges[u][v]=0; --e;

return

true; }

return

false; }基于鄰接矩陣的無向圖實(shí)現(xiàn)ABCDEFABCDEF010010100011000101001001110000011100

public

booleanhasNext(){

for(;curPos<=vertex;++curPos){

if(edges[vertex][curPos]!=0)

return

true; }

for(;curPos<n;++curPos){

if(edges[curPos][vertex]!=0)

break; }

return

curPos==n?false:true; }

publicIntegernext(){

return

curPos++; }討論1、很多書把圖作為一種數(shù)據(jù)結(jié)構(gòu)介紹2、也有這樣的考題：邏輯數(shù)據(jù)結(jié)構(gòu)有哪幾種？答：線性表、樹、圖、集合個(gè)人觀點(diǎn)：前面已經(jīng)學(xué)習(xí)了線性表、棧、隊(duì)列、二叉樹、樹，知道了如何表達(dá)數(shù)據(jù)之間的關(guān)系(結(jié)構(gòu))：數(shù)組、引用(即順序和鏈?zhǔn)?討論更一般的關(guān)系也是使用數(shù)組和引用描述因此，以圖為例，探討各種合適的數(shù)據(jù)結(jié)構(gòu)：鄰接矩陣鄰接表多重鏈表十字鏈表...ABECDABCDEABCDE010010010000010110000010001234ABCDE0100101234ABCDE00100000101100000100有向圖-鄰接矩陣->Node//拆分鄰接矩陣，將頂點(diǎn)數(shù)組和鄰接數(shù)組合并到Node數(shù)組，使用數(shù)組表示鄰接關(guān)系public

classNodeDirectedGraph2<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateNode<?>[]graph;

private

int

e;//邊的條數(shù)

private

final

int

n;//頂點(diǎn)的個(gè)數(shù)

private

static

classNode<T>{ Tvertex;//頂點(diǎn)

int[]to;//鄰接點(diǎn) Node(Tnode,int

count){

vertex=node;

to=new

int[count]; } }有向圖-鄰接矩陣->NodeABECD012341430122有向圖-鄰接表->Node01234ABCDE143012201234ABCDE//將頂點(diǎn)數(shù)組和鄰接表合并到Node數(shù)組，使用LinkedList表示鄰接關(guān)系public

classNodeDirectedGraph<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateNode<?>[]graph;

private

int

e;

private

final

int

n;

private

static

classNode<T>{ Tvertex;//頂點(diǎn) List<Integer>to;//鄰接點(diǎn) Node(Tnode){

vertex=node;

to=newLinkedList<>(); } }有向圖-鄰接表->Node泛型數(shù)組T[]=>Object[]Object[]a=newObject[10];//T[]a=(T[])Object[10];不再用這種形式Tb=(T)a[0];a[0]=new***();Node<T>[]=>Node<?>[]Node<?>[]a=newNode<?>[10];Tb=(T)a[0];a[0]=newNode<>(....);ABECD有向圖-鄰接表143012201234ABCDE1401234ABCDE23012適用的場(chǎng)合???樹的鏈?zhǔn)酱鎯?chǔ)a.頂點(diǎn)同構(gòu)b.頂點(diǎn)異構(gòu)樹的每個(gè)頂點(diǎn)的子樹個(gè)數(shù)不一樣，如何設(shè)計(jì)結(jié)構(gòu)？樹的鏈?zhǔn)酱鎯?chǔ)public

classNode<T>{ Tdata; Node<?>[]subtrees=newNode<?>[5];

publicNode(Tdata){

this.data=data; }}樹的鏈?zhǔn)酱鎯?chǔ)public

classNode<T>{ Tdata; Node<?>[]subtrees;

publicNode(Tdata,int

n){

this.data=data;

subtrees=newNode<?>[n]; }}樹的鏈?zhǔn)酱鎯?chǔ)importjava.util.LinkedList;importjava.util.List;public

classNode<T>{ Tdata; List<Node<?>>subtrees;

publicNode(Tdata){

this.data=data;

subtrees=newLinkedList<>(); }}