2015新疆维吾尔自治区数据库入门入门

1、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。

#define true 1

#define false 0

typedef struct node

{datatype data; struct node *llink,*rlink;} *BTree;

void JudgeBST（BTree t,int flag）

// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（t!=null && flag）

{ Judgebst（t->llink,flag）；// 中序遍历左子树

if（pre==null）pre=t；// 中序遍历的第一个结点不必判断

else if（pre->data<t->data）pre=t；//前驱指针指向当前结点

else{flag=flase；} //不是完全二叉树

Judgebst （t->rlink,flag）；// 中序遍历右子树

}//JudgeBST算法结束

2、#define maxsize 栈空间容量

void InOutS(int s[maxsize])

//s是元素为整数的栈，本算法进行入栈和退栈操作。

{int top=0; //top为栈顶指针，定义top=0时为栈空。

for(i=1; i<=n; i++) //n个整数序列作处理。

{scanf(“%d”,&x); //从键盘读入整数序列。

if(x!=-1) // 读入的整数不等于-1时入栈。

if(top==maxsize-1){printf(“栈满\n”);exit(0);}

else s[++top]=x; //x入栈。

else //读入的整数等于-1时退栈。

{if(top==0){printf(“栈空\n”);exit(0);}

else printf(“出栈元素是%d\n”,s[top--])；}

}

}//算法结

3、给出折半查找的递归算法，并给出算法时间复杂度性分析。

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}可以唯一确定右子树，从而也确定了二叉树。