1、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。
29. ①试找出满足下列条件的二叉树
1)先序序列与后序序列相同 2)中序序列与后序序列相同
3)先序序列与中序序列相同 4)中序序列与层次遍历序列相同
2、将顶点放在两个集合V1和V2。对每个顶点,检查其和邻接点是否在同一个集合中,如是,则为非二部图。为此,用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。 int BPGraph (AdjMatrix g)
//判断以邻接矩阵表示的图g是否是二部图。
{int s[]; //顶点向量,元素值表示其属于那个集合(值1和2表示两个集合)
int Q[];//Q为队列,元素为图的顶点,这里设顶点信息就是顶点编号。
int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组
for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化,各顶点未确定属于那个集合
Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1
while(f {v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号 if (!visited[v]) {visited[v]=1; //确保对每一个顶点,都要检查与其邻接点不应在一个集合中 for (j=1,j<=n;j++) if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列 else if (s[j]==s[v]) return(0);} //非二部图 }//if (!visited[v]) }//while return(1); }//是二部图 [算法讨论] 题目给的是连通无向图,若非连通,则算法要修改。 3、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性,设p在q的左边。后序遍历必然先遍历到结点p,栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时,将栈中元素从栈顶开始逐个到辅助栈中去匹配,第一个匹配(即相等)的元素就是结点p 和q的最近公共祖先。 typedef struct {BiTree t;int tag;//tag=0 表示结点的左子女已被访问,tag=1表示结点的右子女已被访问 }stack; stack s[],s1[];//栈,容量够大 BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。{top=0; bt=ROOT; while(bt!=null ||top>0) {while(bt!=null && bt!=p && bt!=q) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下 if(bt==p) //不失一般性,假定p在q的左侧,遇结点p时,栈中元素均为p的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存 if(bt==q) //找到q 结点。 for(i=top;i>0;i--)//;将栈中元素的树结点到s1去匹配 {pp=s[i].t; for (j=top1;j>0;j--) if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”);return (pp);} } while(top!=0 && s[top].tag==1) top--; //退栈 if (top!=0){s[top].tag=1;bt=s[top].t->rchild;} //沿右分枝向下遍历 }//结束while(bt!=null ||top>0) return(null);//q、p无公共祖先 }//结束Ancestor 4、矩阵中元素按行和按列都已排序,要求查找时间复杂度为O(m+n),因此不能采用常规的二层循环的查找。可以先从右上角(i=a,j=d)元素与x比较,只有三种情况:一是A[i,j]>x,这情况下向j 小的方向继续查找;二是A[i,j] void search(datatype A[ ][ ], int a,b,c,d, datatype x) //n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中. {i=a; j=d; flag=0; //flag是成功查到x的标志 while(i<=b && j>=c) if(A[i][j]==x) {flag=1;break;} else if (A[i][j]>x) j--; else i++; if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型. else printf(“矩阵A中无%d 元素”,x); }算法search结束。