河南数据库入门深入.docx

河南省数据库入门深入————————————————————————————————作者:————————————————————————————————日期: 1、对一般二叉树,仅根据一个先序、中序、后序遍历,不能确定另一个遍历序列。但对于满二叉树,任一结点的左右子树均含有数量相等的结点,根据此性质,可将任一遍历序列转为另一遍历序列(即任一遍历序列均可确定一棵二叉树)。voidPreToPost(ElemTypepre[],post[],intl1,h1,l2,h2)//将满二叉树的先序序列转为后序序列,l1,h1,l2,h2是序列初始和最后结点的下标。{if(h1>=l1){post[h2]=pre[l1];//根结点half=(h1-l1)/2;//左或右子树的结点数PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1)//将左子树先序序列转为后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1)//将右子树先序序列转为后序序列}}//PreToPost32..叶子结点只有在遍历中才能知道,这里使用中序递归遍历。设置前驱结点指针pre,初始为空。第一个叶子结点由指针head指向,遍历到叶子结点时,就将它前驱的rchild指针指向它,最后叶子结点的rchild为空。LinkedListhead,pre=null;//全局变量LinkedListInOrder(BiTreebt)//中序遍历二叉树bt,将叶子结点从左到右链成一个单链表,表头指针为head{if(bt){InOrder(bt->lchild);//中序遍历左子树if(bt->lchild==null&&bt->rchild==null)//叶子结点if(pre==null){head=bt;pre=bt;}//处理第一个叶子结点else{pre->rchild=bt;pre=bt;}//将叶子结点链入链表InOrder(bt->rchild);//中序遍历左子树pre->rchild=null;//设置链表尾}return(head);}//InOrder时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)2、4、 voidLinkList_reverse(Linklist&L)//链表的就地逆置;为简化算法,假设表长大于2{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next){q->next=p;p=q;q=s;s=s->next;//把L的元素逐个插入新表表头}q->next=p;s->next=q;L->next=s;}//LinkList_reverse3、本题要求建立有序的循环链表。从头到尾扫描数组A,取出A[i](0<=i<n),然后到链表中去查找值为A[i]的结点,若查找失败,则插入。LinkedListcreat(ElemTypeA[],intn)//由含n个数据的数组A生成循环链表,要求链表有序并且无值重复结点{LinkedListh;h=(LinkedList)malloc(sizeof(LNode));//申请结点h->next=h;//形成空循环链表for(i=0;i<n;i++){pre=h;p=h