记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。r
i
t
um0，visited0
um记访问顶点个数访问数组visited初始化。r
co
st
用户定义的顶点数r
AdjListg用邻接表作存储结构的有向图g。r
voiddfsvr
visitedv1
um访问的顶点数＋1r
if
um
pri
tf“d是有向图的根。
”v
um0ifr
pgvfirstarcr
whilepr
ifvisiedpadjvex0dfspadjvexr
pp
extwhiler
visitedv0
um恢复顶点vr
dfsr
voidJudgeRootr
判断有向图是否有根，有根则输出之。r
statici
tir
fori1i
i从每个顶点出发，调用dfs各一次。r
um0visited1
0dfsir
　JudgeRootr
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用givertex。r
r
r
r
33、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。r
当
1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。r
设当
m1时结论成立，现证明当
m时结论成立。r
设中序序列为S1，S2，…，Sm后序序列是P1P2…，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si1≤i≤m，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si1是左子树的中序序列，而Si1Si2…Sm是右子树的中序序列。r
若i1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m1则S2，S3，…，Sm和P1，P2，…，Pm1可以唯一确定右子树，从而也确定了二叉树。r
若im则Sm是根，这时二叉树的右子树为空，左子树的结点数是m1，则S1，S2，…，Sm1和P1，P2，…，Pm1唯一确定左子树，从而也确定了二叉树。r
最后，当1im时，Si把中序序列分成S1，S2，…，Si1和Si1Si2…，Sm。由于后序遍历是“左子树右子树根结点”，所以P1P2…Pi1和PiPi1…Pm1是二叉树的左子树和右子树的后序遍历序列。因而由S1，S2，…，Si1和P1，P2，…，Pi1r
可唯一确定二叉树的左子树，由Si1Si2…，Sm和r
PiPi1…，Pm1可唯一确定二叉树的右子树。r
r
34、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。r
29①试找出满足下列条件的二叉树r
1）先序序列与后序序列相同2）中序序列与后序序列相同r
3）先序序列与中序序列相同4）中序序列与层次遍历序列相同r
r
35、已知有向图GVE，其中VV1V2V3V4V5V6V7，EV1V2V1V3V1V4V2V5V3V5V3V6V4V6V5V7V6V7r