二叉搜索樹測試！?。?、空樹2、葉子結(jié)點(diǎn)a、左孩子b、右孩子3、只有左子樹a、左孩子b、右孩子4、只有右子樹a、左孩子b、右孩子幾種情況？構(gòu)造測試用例，逐一測試5、左右子樹都有a、左孩子b、右孩子6、根結(jié)點(diǎn)a、葉子結(jié)點(diǎn)b、只有左子樹c、只有右子樹d、左右子樹都有二叉搜索樹

public

static

voidmain(String[]args){ BinarySearchTree<Integer,Character>bs=newBinarySearchTree<>(); System.out.println(bs.get(6));//測試空表

bs.put(6,'a');

bs.put(3,'b');

bs.put(2,'c');

bs.put(3,'d');//替換

bs.put(5,'e');

bs.put(4,'f');

bs.put(9,'g');

bs.put(8,'i');

bs.put(7,'h');

bs.put(10,'i');

bs.inOrder(); System.out.println(bs.get(6)); System.out.println(bs.get(2)); System.out.println(bs.remove(9));//測試各種情況2，4，8，10，5，7，3，9，6;不put5和4，然后remove3 System.out.println("------afterremove------");

bs.inOrder(); }從空樹開始建樹沒有scanner唯一出現(xiàn)print的地方01234514043525011253BACDFEABCDEFABCDEF010010100011000101001001110000011100無向圖一條邊存了2次或者說：每個(gè)頂點(diǎn)存儲(chǔ)自己的所有鄰接點(diǎn)BACDFEABCDEFACABBCD基于鄰接表的無向圖頂點(diǎn)v的鄰接點(diǎn)(關(guān)聯(lián)的邊的另一端的頂點(diǎn)):1、v的鏈表中的所有頂點(diǎn)2、比v的編號大的頂點(diǎn)u，如果u的鏈表中出現(xiàn)了v一條邊只存1次或者說：頂點(diǎn)的鄰接點(diǎn)分散在多個(gè)地方removeEdge(1,0)、removeEdge(0,1)：不知道是用哪一種方式調(diào)用基于鄰接表的無向圖A和B之間的邊：(A,B)或(B,A)BACDFEABCDEFACABBCD基于鄰接表的無向圖

public

booleanremoveEdge1(int

u,int

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

if(u>v){

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

return

true; } }else{

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

return

true; } }

return

false; }基于鄰接表的無向圖

public

booleanremoveEdge(int

u,int

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

if(v>u){//使u比v大

int

tmp=v;

v=u;

u=tmp; }

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

return

true; }

return

false; }基于鄰接表的無向圖

public

intdegree(int

v){

int

count=edges.get(v).size();

for(int

i=v+1;i<n;i++){

if(edges.get(i).indexOf(pair.setNode(v))!=-1) ++count; }

return

count; }BACDFEABCDEFACABBCD基于鄰接表的無向圖

private

classItrimplementsIterator<Integer>{

int

next;//下一個(gè)鄰接點(diǎn)的編號

privateIterator<Pair>it; Pairpair;

publicItr(int

v){

it=edges.get(v).iterator();

next=v;

pair=newPair(v,0); }基于鄰接表的無向圖

public

booleanhasNext(){

if(it.hasNext())//編號小于v

return

true;

while(++next<n){//編號大于v

if(edges.get(next).indexOf(pair)!=-1)

break; }

return

next!=n?true:false; }

publicIntegernext(){

if(it.hasNext())

return

it.next().vertex;

return

next; } }BACDFEABCDEFEABCDEFD初始化reached[]將u入棧如果棧為空，算法結(jié)束；否則：出棧=>u如果reached[u]=true，繼續(xù)3，否則:reached[]=true將u的鄰接點(diǎn)v，并且reached[v]=false入棧，繼續(xù)3非遞歸描述：非遞歸深度優(yōu)先廣度優(yōu)先搜索初始化reached將u入隊(duì)如果隊(duì)為空，算法結(jié)束；否則：出隊(duì)=>u，如果reached[u]=true則繼續(xù)3，否則:reached[u]=true將u的鄰接點(diǎn)v，并且reached[v]=false入隊(duì)，繼續(xù)2算法描述：注：也可以先reached[v]=true再入隊(duì)，減少同一個(gè)頂點(diǎn)多次入隊(duì)BACDFEABCDEFABCDEF初始化reached[]將u入棧，reached[u]=true如果棧為空，算法結(jié)束；否則：出棧=>u遍歷u將u的鄰接點(diǎn)v，并且reached[v]=false入棧，reached[v]=true繼續(xù)3防止同一個(gè)頂點(diǎn)多次入棧：非遞歸深度優(yōu)先非遞歸深度優(yōu)先

public

voidndfs(int

u,Consumer<T>fun){

reached=new

boolean[n]; ndfs0(u,fun); }

private

voidndfs0(int

t,Consumer<T>fun){ Deque<Integer>stack=newLinkedList<>();//非多線程，不要使用類庫的Stack！

stack.push(t);

reached[t]=true;//等待搜索

while(!stack.isEmpty()){

int

u=stack.pop();

fun.accept(graph.value(u));

for(Iterator<Integer>it=graph.iterator(u);it.hasNext();){

int

v=it.next();

if(!reached[v]){

stack.push(v);

reached[v]=true;//等待搜素 } } } }拓?fù)渑判?/p>

public

int[]topologicalSort(){

if(graph.getGraphKind()!=GraphKind.DirectedGraph||

graph.getGraphKind()!=GraphKind.WeightedDirectedGraph)

return

null; Deque<Integer>stack=newArrayDeque<>(n);//最多n個(gè)數(shù)據(jù)

int[]indegree=new

int[n];

for(int

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

if((indegree[i]=graph.inDegree(i))==0)

stack.push(i); }

int[]result=new

int[n];

int

index=0;

while(!stack.isEmpty()){

int

v=stack.pop();

result[index++]=v; Iterator<Integer>it=graph.iterator(v);

while(it.hasNext()){

int

i=it.next();

if(--indegree[i]==0)

stack.push(i); } }

return

index==n?result:null; }完全二叉樹(completebinarytree)ACGBDEFHIACGBDEFHIACGBDEFHJI完全二叉樹(completebinarytree)ACGBDEFHJI完全二叉樹(completebinarytree)

public

booleanisCompleteBinaryTree2(){ Deque<Node<T>>q=newLinkedList<>();//不能使用ArrayDeque???

q.offer(root);

while(!q.isEmpty()){//入隊(duì) Node<T>t=q.poll();

if(t==null)

break;

q.offer(t.left);

q.offer(t.right); }

while(!q.isEmpty()){//檢測

if(q.poll()!=null)

return

false; }

return

true; }完全二叉樹(completebinarytree)

public

booleanisCompleteBinaryTree1(){

if(root==null)

return

true; Deque<Node<T>>q=newLinkedList<>();

q.offer(root);

while(!q.isEmpty()){//null不入隊(duì)

if(q.peek().left==null)//遇到左孩子為空，去測試

break; Node<T>t=q.poll();

q.offer(t.left);

if(t.right==null)//遇到右孩子為空，去測試

break;

q.offer(t.right); }

while(!q.isEmpty()){//測試：隊(duì)中剩余的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)才是完全二叉樹 Node<T>t=q.poll();

if(t.left!=null||t.right!=null)

return

false; }

return

true; }滿二叉樹

public

booleanisFullBinaryTree(){

if(root==null)

return

true; Deque<Node<T>>q=newLinkedList<>();

q.offer(root);

int

count=1;//第0層1個(gè)結(jié)點(diǎn)

while(!q.isEmpty()){

if(q.size()!=count)

return

false;

//上一層的結(jié)點(diǎn)出隊(duì)，下一層的結(jié)點(diǎn)入隊(duì),null不入隊(duì)

for(int

nodes=count;nodes>0;nodes--){ Node<T>t=q.poll();

if(t.