1、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。
int Similar(BiTree p,q) //判断二叉树p和q是否相似 {if(p==null && q==null) return (1); else if(!p && q || p && !q) return (0);
else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束Similar
2、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。 29. ①试找出满足下列条件的二叉树
1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同
3、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下： typedef struct
{ int lvl; //层次序列指针，总是指向当前“根结点”在层次序列中的位置 int l,h; //中序序列的下上界
int f; //层次序列中当前“根结点”的双亲结点的指针 int lr; // 1—双亲的左子树 2—双亲的右子树 }qnode;
BiTree Creat(datatype in[],level[],int n)
//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。 n是二叉树的结点数 {if (n<1) {printf(“参数错误\\n”); exit(0);}
qnode s,Q[]; //Q是元素为qnode类型的队列，容量足够大 init(Q); int R=0; //R是层次序列指针，指向当前待处理的结点 BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结点 p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据
for (i=0; i if (i==0) //根结点无左子树，遍历序列的1—n-1是右子树 {p->lchild=null; s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s); } else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树 {p->rchild=null; s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else //根结点有左子树和右子树 {s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列 s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列 } while (!empty(Q)) //当队列不空，进行循环，构造二叉树的左右子树 { s=delqueue(Q); father=s.f; for (i=s.l; i<=s.h; i++) if (in[i]==level[s.lvl]) break; p=(bitreptr)malloc(sizeof(binode)); //申请结点空间 p->data=level[s.lvl]; p->lchild=null; p->rchild=null; //填写该结点数据 if (s.lr==1) father->lchild=p; else father->rchild=p； //让双亲的子女指针指向该结点 if (i==s.l) {p->lchild=null; //处理无左子女 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); } else if (i==s.h) {p->rchild=null; //处理无右子女 s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队列 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子树有关信息入队列 } }//结束while (!empty(Q)) return(p); }//算法结束 4、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。 当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。 设当n=m-1时结论成立，现证明当n=m时结论成立。 设中序序列为S1，S2，?，Sm,后序序列是P1,P2,?，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，?，Si-1是左子树的中序序列，而Si+1,Si+2,?,Sm是右子树的中序序列。 若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，?，Sm}和{P1，P2，?，Pm-1}可以唯一确定右子树，从而也确定了二叉树。 若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，?，Sm-1}和{P1，P2，?，Pm-1}唯一确定左子树，从而也确定了二叉树。 最后，当1 5、本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0<=i //由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点 {LinkedList h; h=(LinkedList)malloc(sizeof(LNode));//申请结点 h->next=h; //形成空循环链表 for(i=0;i while(p!=h && p->data {pre=p; p=p->next;} //查找A[i]的插入位置 if(p==h || p->data!=A[i]) //重复数据不再输入 {s=(LinkedList)malloc(sizeof(LNode)); s->data=A[i]; pre->next=s; s->next=p;//将结点s链入链表中 } }//for return(h); }算法结束 6、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。 void union(int A[],B[],C[],m,n) //整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。 {i=0; j=n-1; k=0;// i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始 while(i if(a[i] 4、要求二叉树按二叉链表形式存储。15分 （1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。 BiTree Creat() //建立二叉树的二叉链表形式的存储结构 {ElemType x；BiTree bt; scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0) {bt=(BiNode *)malloc(sizeof(BiNode)); bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } else error(“输入错误”)； return(bt); }//结束 BiTree int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0 {int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1); QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队 while (!QueueEmpty(Q)) {p=QueueOut(Q); //出队 if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队 else {if (p->lchild) return 0; //前边已有结点为空，本结点不空 else tag=1; //首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队 else if (p->rchild) return 0; else tag=1; } //while return 1; } //JudgeComplete 7、设从键盘输入一整数的序列：a1, a2, a3，?，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。 Knap(S，n) 若S=0 则Knap←true 否则若（S<0）或(S>0且n<1) 则Knap←false 否则若Knap(1) , _=true 则print(W[n])；Knap ←true 否则 Knap←Knap(2) _ , _ 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如： 设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。 将n(n>1)个整数存放到一维数组R中。设计一个尽可能高效（时间、空间）的算 法，将R中保存的序列循环左移p（0
相关推荐：
loading