{
InitALGraph(G)
scanf("%d",&v)
if(v<0) return ERROR//顶点数不能为负
G.vexnum=v
scanf("%d",&a)
if(a<0) return ERROR//边数不能为负
G.arcnum=a
for(m=0m<vm++)
G.vertices[m].data=getchar()//输入各顶点的符号
for(m=1m<=am++)
{
t=getchar()h=getchar()//t为弧尾,h为弧头
if((i=LocateVex(G,t))<0) return ERROR
if((j=LocateVex(G,h))<0) return ERROR//顶点未找到
p=(ArcNode*)malloc(sizeof(ArcNode))
if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p
else
{
for(q=G.vertices[i].firstarcq->nextarcq=q->nextarc)
q->nextarc=p
}
p->adjvex=jp->nextarc=NULL
}//while
return OK
}//Build_AdjList
7.15
//本题中的图G均为有向无权图,其余情况容易由此写出
Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v
{
if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE
G.vexs[++G.vexnum]=v
return OK
}//Insert_Vex
Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR
if((j=LocateVex(G,w))<0) return ERROR
if(i==j) return ERROR
if(!G.arcs[i][j].adj)
{
G.arcs[i][j].adj=1
G.arcnum++
}
return OK
}//Insert_Arc
Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v
{
n=G.vexnum
if((m=LocateVex(G,v))<0) return ERROR
G.vexs[m]<->G.vexs[n]//将待删除顶点交换到最后一个顶点
for(i=0i<ni++)
{
G.arcs[i][m]=G.arcs[i][n]
G.arcs[m][i]=G.arcs[n][i]//将边的关系随之交换
}
G.arcs[m][m].adj=0
G.vexnum--
return OK
}//Delete_Vex
分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.
Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR
if((j=LocateVex(G,w))<0) return ERROR
if(G.arcs[i][j].adj)
{
G.arcs[i][j].adj=0
G.arcnum--
}
return OK
}//Delete_Arc
7.16
//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出.
Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR
if((j=LocateVex(G,w))<0) return ERROR
p=(ArcNode*)malloc(sizeof(ArcNode))
p->adjvex=jp->nextarc=NULL
if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p
else
{
for(q=G.vertices[i].firstarcq->q->nextarcq=q->nextarc)
if(q->adjvex==j) return ERROR//边已经存在
q->nextarc=p
}
G.arcnum++
return OK
}//Insert_Arc
7.17
//为节省篇幅,本题只给出较为复杂的Delete_Vex算法.其余算法请自行写出.
Status Delete_Vex(OLGraph &G,char v)//在十字链表表示的图G上删除顶点v
{
if((m=LocateVex(G,v))<0) return ERROR
n=G.vexnum
for(i=0i<ni++) //删除所有以v为头的边
{
if(G.xlist[i].firstin->tailvex==m) //如果待删除的边是头链上的第一个结点
{
q=G.xlist[i].firstin
G.xlist[i].firstin=q->hlink
free(q)G.arcnum--
}
else //否则
{
for(p=G.xlist[i].firstinp&&p->hlink->tailvex!=mp=p->hlink)
if(p)
{
q=p->hlink
p->hlink=q->hlink
free(q)G.arcnum--
}
}//else
}//for
for(i=0i<ni++) //删除所有以v为尾的边
{
if(G.xlist[i].firstout->headvex==m) //如果待删除的边是尾链上的第一个结点
{
q=G.xlist[i].firstout
G.xlist[i].firstout=q->tlink
free(q)G.arcnum--
}
else //否则
{
for(p=G.xlist[i].firstoutp&&p->tlink->headvex!=mp=p->tlink)
if(p)
{
q=p->tlink
p->tlink=q->tlink
free(q)G.arcnum--
}
}//else
}//for
for(i=mi<ni++) //顺次用结点m之后的顶点取代前一个顶点
{
G.xlist[i]=G.xlist[i+1]//修改表头向量
for(p=G.xlist[i].firstinpp=p->hlink)
p->headvex--
for(p=G.xlist[i].firstoutpp=p->tlink)
p->tailvex--//修改各链中的顶点序号
}
G.vexnum--
return OK
}//Delete_Vex
7.18
//为节省篇幅,本题只给出Delete_Arc算法.其余算法请自行写出.
Status Delete_Arc(AMLGraph &G,char v,char w)////在邻接多重表表示的图G上删除边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR
if((j=LocateVex(G,w))<0) return ERROR
if(G.adjmulist[i].firstedge->jvex==j)
G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink
else
{
for(p=G.adjmulist[i].firstedgep&&p->ilink->jvex!=jp=p->ilink)
if (!p) return ERROR//未找到
p->ilink=p->ilink->ilink
} //在i链表中删除该边
if(G.adjmulist[j].firstedge->ivex==i)
G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink
else
{
for(p=G.adjmulist[j].firstedgep&&p->jlink->ivex!=ip=p->jlink)
if (!p) return ERROR//未找到
q=p->jlink
p->jlink=q->jlink
free(q)
} //在i链表中删除该边
G.arcnum--
return OK
}//Delete_Arc
7.19
Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表
{
InitAMLGraph(G)
scanf("%d",&v)
if(v<0) return ERROR//顶点数不能为负
G.vexnum=v
scanf(%d",&a)
if(a<0) return ERROR//边数不能为负
G.arcnum=a
for(m=0m<vm++)
G.adjmulist[m].data=getchar()//输入各顶点的符号
for(m=1m<=am++)
{
t=getchar()h=getchar()//t为弧尾,h为弧头
if((i=LocateVex(G,t))<0) return ERROR
if((j=LocateVex(G,h))<0) return ERROR//顶点未找到
p=(EBox*)malloc(sizeof(EBox))
p->ivex=ip->jvex=j
p->ilink=NULLp->jlink=NULL//边结点赋初值
if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p
else
{
q=G.adjmulist[i].firstedge
while(q)
{
r=q
if(q->ivex==i) q=q->ilink
else q=q->jlink
}
if(r->ivex==i) r->ilink=p//注意i值既可能出现在边结点的ivex域中,
else r->jlink=p//又可能出现在边结点的jvex域中
}//else //插入i链表尾部
if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p
else
{
q=G.adjmulist[i].firstedge
while(q)
{
r=q
if(q->jvex==j) q=q->jlink
else q=q->ilnk
}
if(r->jvex==j) r->jlink=p
else r->ilink=p
}//else //插入j链表尾部
}//for
return OK
}//Build_AdjList
7.20
int Pass_MGraph(MGraph G)//判断一个邻接矩阵存储的有向图是不是可传递的,是则返回1,否则返回0
{
for(x=0x<G.vexnumx++)
for(y=0y<G.vexnumy++)
if(G.arcs[x][y])
{
for(z=0z<G.vexnumz++)
if(z!=x&&G.arcs[y][z]&&!G.arcs[x][z]) return 0//图不可传递的条件
}//if
return 1
}//Pass_MGraph
分析:本算法的时间复杂度大概是O(n^2*d).
7.21
int Pass_ALGraph(ALGraph G)//判断一个邻接表存储的有向图是不是可传递的,是则返回1,否则返回0
{
for(x=0x<G.vexnumx++)
for(p=G.vertices[x].firstarcpp=p->nextarc)
{
y=p->adjvex
for(q=G.vertices[y].firstarcqq=q->nextarc)
{
z=q->adjvex
if(z!=x&&!is_adj(G,x,z)) return 0
}//for
}//for
}//Pass_ALGraph
int is_adj(ALGraph G,int m,int n)//判断有向图G中是否存在边(m,n),是则返回1,否则返回0
{
for(p=G.vertices[m].firstarcpp=p->nextarc)
if(p->adjvex==n) return 1
return 0
}//is_adj
7.22
int visited[MAXSIZE]//指示顶点是否在当前路径上
int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
if(i==j) return 1//i就是j
else
{
visited[i]=1
for(p=G.vertices[i].firstarcpp=p->nextarc)
{
k=p->adjvex
if(!visited[k]&&exist_path(k,j)) return 1//i下游的顶点到j有路径
}//for
}//else
}//exist_path_DFS
7.23
int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
int visited[MAXSIZE]
InitQueue(Q)
EnQueue(Q,i)
while(!QueueEmpty(Q))
{
DeQueue(Q,u)
visited[u]=1
for(p=G.vertices[i].firstarcpp=p->nextarc)
{
k=p->adjvex
if(k==j) return 1
if(!visited[k]) EnQueue(Q,k)
}//for
}//while
return 0
}//exist_path_BFS
7.24
void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G
{
int visited[MAXSIZE]
InitStack(S)
Push(S,GetVex(S,1))//将第一个顶点入栈
visit(1)
visited =1
while(!StackEmpty(S))
{
while(Gettop(S,i)&&i)
{
j=FirstAdjVex(G,i)
if(j&&!visited[j])
{
visit(j)
visited[j]=1
Push(S,j)//向左走到尽头
}
}//while
if(!StackEmpty(S))
{
Pop(S,j)
Gettop(S,i)
k=NextAdjVex(G,i,j)//向右走一步
if(k&&!visited[k])
{
visit(k)
visited[k]=1
Push(S,k)
}
}//if
}//while
}//Straverse_Nonrecursive
分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.
7.25
见书后解答.
7.26
Status TopoNo(ALGraph G)//按照题目要求顺序重排有向图中的顶点
{
int new[MAXSIZE],indegree[MAXSIZE]//储存结点的新序号
n=G.vexnum
FindInDegree(G,indegree)
InitStack(S)
for(i=1i<G.vexnumi++)
if(!indegree[i]) Push(S,i)//零入度结点入栈
count=0
while(!StackEmpty(S))
{
Pop(S,i)
new[i]=n--//记录结点的拓扑逆序序号
count++
for(p=G.vertices[i].firstarcpp=p->nextarc)
{
k=p->adjvex
if(!(--indegree[k])) Push(S,k)
}//for
}//while
if(count<G.vexnum) return ERROR//图中存在环
for(i=1i<=ni++) printf("Old No:%d New No:%d\n",i,new[i])
return OK
}//TopoNo
分析:只要按拓扑逆序对顶点编号,就可以使邻接矩阵成为下三角矩阵.
7.27
int visited[MAXSIZE]
int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径
{
if(i==j&&k==0) return 1//找到了一条路径,且长度符合要求
else if(k>0)
{
visited[i]=1
for(p=G.vertices[i].firstarcpp=p->nextarc)
{
l=p->adjvex
if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1//剩余路径长度减一
}//for
visited[i]=0//本题允许曾经被访问过的结点出现在另一条路径中
}//else
return 0//没找到
}//exist_path_len
7.28
int path[MAXSIZE],visited[MAXSIZE]//暂存遍历过程中的路径
int Find_All_Path(ALGraph G,int u,int v,int k)//求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度
{
path[k]=u//加入当前路径中
visited[u]=1
if(u==v) //找到了一条简单路径
{
printf("Found one path!\n")
for(i=0path[i]i++) printf("%d",path[i])//打印输出
}
else
for(p=G.vertices[u].firstarcpp=p->nextarc)
{
l=p->adjvex
if(!visited[l]) Find_All_Path(G,l,v,k+1)//继续寻找
}
visited[u]=0
path[k]=0//回溯
}//Find_All_Path
main()
{
...
Find_All_Path(G,u,v,0)//在主函数中初次调用,k值应为0
...
}//main
7.29
int GetPathNum_Len(ALGraph G,int i,int j,int len)//求邻接表方式存储的有向图G的顶点i到j之间长度为len的简单路径条数
{
if(i==j&&len==0) return 1//找到了一条路径,且长度符合要求
else if(len>0)
{
sum=0//sum表示通过本结点的路径数
visited[i]=1
for(p=G.vertices[i].firstarcpp=p->nextarc)
{
l=p->adjvex
if(!visited[l])
sum+=GetPathNum_Len(G,l,j,len-1)//剩余路径长度减一
}//for
visited[i]=0//本题允许曾经被访问过的结点出现在另一条路径中
}//else
return sum
}//GetPathNum_Len
7.30
int visited[MAXSIZE]
int path[MAXSIZE]//暂存当前路径
int cycles[MAXSIZE][MAXSIZE]//储存发现的回路所包含的结点
int thiscycle[MAXSIZE]//储存当前发现的一个回路
int cycount=0//已发现的回路个数
void GetAllCycle(ALGraph G)//求有向图中所有的简单回路
{
for(v=0v<G.vexnumv++) visited[v]=0
for(v=0v<G.vexnumv++)
if(!visited[v]) DFS(G,v,0)//深度优先遍历
}//DFSTraverse
void DFS(ALGraph G,int v,int k)//k表示当前结点在路径上的序号
{
visited[v]=1
path[k]=v//记录当前路径
for(p=G.vertices[v].firstarcpp=p->nextarc)
{
w=p->adjvex
if(!visited[w]) DFS(G,w,k+1)
else //发现了一条回路
{
for(i=0path[i]!=wi++)//找到回路的起点
for(j=0path[i+j]i++) thiscycle[j]=path[i+j]//把回路复制下来
if(!exist_cycle()) cycles[cycount++]=thiscycle//如果该回路尚未被记录过,就添加到记录中
for(i=0i<G.vexnumi++) thiscycle[i]=0//清空目前回路数组
}//else
}//for
path[k]=0
visited[k]=0//注意只有当前路径上的结点visited为真.因此一旦遍历中发现当前结点visited为真,即表示发现了一条回路
}//DFS
int exist_cycle()//判断thiscycle数组中记录的回路在cycles的记录中是否已经存在
{
int temp[MAXSIZE]
for(i=0i<cycounti++) //判断已有的回路与thiscycle是否相同
{ //也就是,所有结点和它们的顺序都相同
j=0c=thiscycle//例如,142857和857142是相同的回路
for(k=0cycles[i][k]!=c&&cycles[i][k]!=0k++)//在cycles的一个行向量中寻找等于thiscycle第一个结点的元素
if(cycles[i][k]) //有与之相同的一个元素
{
for(m=0cycles[i][k+m]m++)
temp[m]=cycles[i][k+m]
for(n=0n<kn++,m++)
temp[m]=cycles[i][n]//调整cycles中的当前记录的循环相位并放入temp数组中
if(!StrCompare(temp,thiscycle)) //与thiscycle比较
return 1//完全相等
for(m=0m<G.vexnumm++) temp[m]=0//清空这个数组
}
}//for
return 0//所有现存回路都不与thiscycle完全相等
}//exist_cycle
分析:这个算法的思想是,在遍历中暂存当前路径,当遇到一个结点已经在路径之中时就表明存在一条回路扫描路径向量path可以获得这条回路上的所有结点.把结点序列(例如,142857)存入thiscycle中由于这种算法中,一条回路会被发现好几次,所以必须先判断该回路是否已经在cycles中被记录过,如果没有才能存入cycles的一个行向量中.把cycles的每一个行向量取出来与之比较.由于一条回路可能有多种存储顺序,比如142857等同于285714和571428,所以还要调整行向量的次序,并存入temp数组,例如,thiscycle为142857第一个结点为1,cycles的当前向量为857142,则找到后者中的1,把1后部分提到1前部分前面,最终在temp中得到142857,与thiscycle比较,发现相同,因此142857和857142是同一条回路,不予存储.这个算法太复杂,很难保证细节的准确性,大家理解思路便可.希望有人给出更加简捷的算法.
7.31
int visited[MAXSIZE]
int finished[MAXSIZE]
int count//count在第一次深度优先遍历中用于指示finished数组的填充位置
void Get_SGraph(OLGraph G)//求十字链表结构储存的有向图G的强连通分量
{
count=0
for(v=0v<G.vexnumv++) visited[v]=0
for(v=0v<G.vexnumv++) //第一次深度优先遍历建立finished数组
if(!visited[v]) DFS1(G,v)
for(v=0v<G.vexnumv++) visited[v]=0//清空visited数组
for(i=G.vexnum-1i>=0i--) //第二次逆向的深度优先遍历
{
v=finished(i)
if(!visited[v])
{
printf("\n")//不同的强连通分量在不同的行输出
DFS2(G,v)
}
}//for
}//Get_SGraph
void DFS1(OLGraph G,int v)//第一次深度优先遍历的算法
{
visited[v]=1
for(p=G.xlist[v].firstoutpp=p->tlink)
{
w=p->headvex
if(!visited[w]) DFS1(G,w)
}//for
finished[++count]=v//在第一次遍历中建立finished数组
}//DFS1
void DFS2(OLGraph G,int v)//第二次逆向的深度优先遍历的算法
{
visited[v]=1
printf("%d",v)//在第二次遍历中输出结点序号
for(p=G.xlist[v].firstinpp=p->hlink)
{
w=p->tailvex
if(!visited[w]) DFS2(G,w)
}//for
}//DFS2
分析:求有向图的强连通分量的算法的时间复杂度和深度优先遍历相同,也为O(n+e).
7.32
void Forest_Prim(ALGraph G,int k,CSTree &T)//从顶点k出发,构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存储
{
for(j=0j<G.vexnumj++) //以下在Prim算法基础上稍作改动
if(j!=k)
{
closedge[j]={k,Max_int}
for(p=G.vertices[j].firstarcpp=p->nextarc)
if(p->adjvex==k) closedge[j].lowcost=p->cost
}//if
closedge[k].lowcost=0
for(i=1i<G.vexnumi++)
{
k=minimum(closedge)
if(closedge[k].lowcost<Max_int)
{
Addto_Forest(T,closedge[k].adjvex,k)//把这条边加入生成森林中
closedge[k].lowcost=0
for(p=G.vertices[k].firstarcpp=p->nextarc)
if(p->cost<closedge[p->adjvex].lowcost)
closedge[p->adjvex]={k,p->cost}
}//if
else Forest_Prim(G,k)//对另外一个连通分量执行算法
}//for
}//Forest_Prim
void Addto_Forest(CSTree &T,int i,int j)//把边(i,j)添加到孩子兄弟链表表示的树T中
{
p=Locate(T,i)//找到结点i对应的指针p,过程略
q=(CSTNode*)malloc(sizeof(CSTNode))
q->data=j
if(!p) //起始顶点不属于森林中已有的任何一棵树
{
p=(CSTNode*)malloc(sizeof(CSTNode))
p->data=i
for(r=Tr->nextsibr=r->nextsib)
r->nextsib=p
p->firstchild=q
} //作为新树插入到最右侧
else if(!p->firstchild) //双亲还没有孩子
p->firstchild=q//作为双亲的第一个孩子
else //双亲已经有了孩子
{
for(r=p->firstchildr->nextsibr=r->nextsib)
r->nextsib=q//作为双亲最后一个孩子的兄弟
}
}//Addto_Forest
main()
{
...
T=(CSTNode*)malloc(sizeof(CSTNode))//建立树根
T->data=1
Forest_Prim(G,1,T)
...
}//main
分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块而得到的,其时间复杂度为O(n^2).
7.33
typedef struct {
int vex//结点序号
int ecno//结点所属的连通分量号
} VexInfo
VexInfo vexs[MAXSIZE]//记录结点所属连通分量号的数组
void Init_VexInfo(VexInfo &vexs[ ],int vexnum)//初始化
{
for(i=0i<vexnumi++)
vexs[i]={i,i}//初始状态:每一个结点都属于不同的连通分量
}//Init_VexInfo
int is_ec(VexInfo vexs[ ],int i,int j)//判断顶点i和顶点j是否属于同一个连通分量
{
if(vexs[i].ecno==vexs[j].ecno) return 1
四、 遍历二叉树 二叉树是一种非线性的数据结构，在对它进行 *** 作时，总是需要逐一对每个数据元素实施 *** 作，这样就存在一个 *** 作顺序问题，由此提出了二叉树的遍历 *** 作。所谓遍历二叉树就 是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比 较、更新、查看元素内容等等各种 *** 作。二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按 层次访问。下面我们将分别进行讨论。
1、 按根、左子树和右子树三部分进行遍历 遍历二叉树的顺序存在下面6种可能：TLR（根左右）, TRL（根右左）LTR（左根右）, RTL（右根左）LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。（1）先序遍历若二叉树为空，则结束遍历 *** 作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历 *** 作；否则中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历若二叉树为空，则结束遍历 *** 作；否则后序遍历左子树；后序遍历右子树；访问根结点。例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列二叉树的两种遍历方法：（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列
（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。 由此可以看出：（1）遍历 *** 作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历 *** 作是一个递归的过程，因此，这三种遍历 *** 作的算法可以用递归函数实现。（1）先序遍历递归算法
void PreOrder(BTree BT) {
if (BT) { Visit(BT)
PreOrder(BT->Lchild)
PreOrder(BT->Rchild)
}（2）中序遍历递归算法
void InOrder(BTree BT) {
if (BT) {
InOrder(BT->Lchild)
Visit(BT)
InOrder(BT->Rchild)
}
}（3）后序遍历递归算法
void PostOrder(BTree BT) {
if (BT) {
PostOrder(BT->Lchild)
PostOrder(BT->Rchild)
Visit(BT)
}
} 2 、按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。
void LevelOreder(QBTree BT) {
for (i=1i<=BT.ni++)
if (BT.elem[i]!='#') Visite(BT.elem[i])
}二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述如下：访问根结点，并将该结点记录下来；若记录的所有结点都已处理完毕，则结束遍历 *** 作；否则重复下列 *** 作。取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。 在这个算法中，应使用一个队列结构完成这项 *** 作。所谓记录访问结点就是入队 *** 作； 而取出记录的结点就是出队 *** 作。这样一来，我们的算法就可以描述成下列形式：（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列 *** 作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；void LevelOrder(BTree *BT) {
if (!BT) exit
InitQueue(Q)p=BT//初始化
Visite(p)EnQueue(&Q,p)//访问根结点，并将根结点入队
while (!QueueEmpty(Q)) { //当队非空时重复执行下列 *** 作
DeQueue(&Q,&p)//出队
if (!p->Lchild) {Visite(p->Lchild)EnQueue(&Q,p->Lchild)//处理左孩子<br> if (!p->Rchild) {Visite(p->Rchild)EnQueue(&Q,p->Rchild)//处理右孩子<br> }
}
五、典型二叉树的 *** 作算法 1、 输入一个二叉树的先序序列，构造这棵二叉树 为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，'#'。在算法中，需要对每个输入的字符进行判断，如果对应的字符是'#'，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。算法：BTree Pre_Create_BT( ) {
getch(ch)
if (ch=='#') return NULL//构造空树
else { BT=(BTree)malloc(sizeof(BTLinklist))//构造新结点
BT->data=ch
BT->lchild =Pre_Create_BT( )//构造左子树
BT->rchild =Pre_Create_BT( )//构造右子树
return BT
}
} 2、 计算一棵二叉树的叶子结点数目 这个 *** 作可以使用三种遍历顺序中的任何一种，只是需要将访问 *** 作变成判断该结点是否 为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。算法：void Leaf(BTree BT,int *count) {
if (BT) {
Leaf(BT->child,&count)//计算左子树的叶子结点个数
if (BT->lchild==NULL&&BT->rchild==NULL) (*count)++
Leaf(BT->rchild,&count)//计算右子树的叶子结点个数
}
} 3、 交换二叉树的左右子树 许多 *** 作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一 些。而有些 *** 作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个 *** 作就属于这类情况。算法：void change_left_right(BTree BT) {
if (BT) {
change_left_right(BT->lchild)
change_left_right(BT->rchild)
BT->lchild<->BT->rchild
}
} 4 、求二叉树的高度 这个 *** 作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树 的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。算法：int hight(BTree BT) { //h1和h2分别是以BT为根的左右子树的高度
if (BT==NULL) return 0
else {
h1=hight(BT->lchild)
h2=hight(BT->right)
return max{h1,h2}+1
}
} 六、树、森林与二叉树的转换 1、 树、森林转换成二叉树 将一棵树转换成二叉树的方法： 将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。 特点：一棵树转换成二叉树后，根结点没有右孩子。 将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根 结点看作兄弟关系，并对其中的每棵树依依地进行转换。2 、二叉树还原成树或森林 这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。
第 3 节 哈夫曼树及其应用1、哈夫曼树的定义及特点
在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼树的一个重要特点是：没有度为1的结点。
2、构造哈夫曼树的过程：
（1）将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。 例如： 假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。
它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713．判定树在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：if (socre<60) printf("bad")
else if (socre<70) printf("pass")
else if (score<80) printf("general")
else if (score<90) printf("good")
esle printf("very good")在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：
4．前缀编码 在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两 个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
（1）等长编码 这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位 数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。（2）不等长编码 在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有8个字符，每个字符的使用频率分别为{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，现以此为例设计哈夫曼编码。
哈夫曼编码设计过程为：
（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到{5,29,7,8,14,23,3,11}；
（2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图5-27所示；
（3）由此哈夫曼树生成哈夫曼编码，如图5-28所示。
最后得出每个字符的编码为：比如，发送一段编码：0000011011010010， 接收方可以准确地通过译码得到：⑥⑥⑦⑤②⑧。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）