实验6 实验目的：1、掌握二叉树的所有算法2、熟悉计算机英语和术语实验步骤：1、二叉树算法的模拟2、完型填空3、翻译具体要求：一、设计一个完整的程序，实现二叉树的各种算法要求：/*用函数实现如下二叉排序树算法：（1）插入新结点（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法（4）层次遍历二叉树（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0) （6）交换各结点的左右子树（7）求二叉树的深度（8）叶子结点数输入：第一行：准备建树的结点个数n第二行：输入n个整数，用空格分隔第三行：输入待查找的关键字第四行：输入待查找的关键字第五行：输入待插入的关键字输出：第一行：二叉树的先序遍历序列第二行：二叉树的中序遍历序列第三行：二叉树的后序遍历序列第四行：查找结果第五行：查找结果第六行~第八行：插入新结点后的二叉树的先、中、序遍历序列第九行：插入新结点后的二叉树的中序遍历序列(非递归算法) 代码：#include "stdio.h"#include "malloc.h"#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int KeyType;#define STACK_INIT_SIZE 100 // 存储空间初始分配量#define STACKINCREMENT 10 // 存储空间分配增量#define MAXQSIZE 100typedef int ElemType;typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;//左右孩子指针} BiTNode,*BiTree;Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){if(!T){p=f;return FALSE;}else if(key==T->data){p=T;return TRUE;}else if(key<T->data)return SearchBST(T->lchild,key,T,p);else return(SearchBST(T->rchild,key,T,p));}Status InsertBST(BiTree &T,ElemType e){BiTree s,p;if(!SearchBST(T,e,NULL,p)){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;else if(e<p->data)p->lchild=s;else p->rchild=s;return TRUE;}else return FALSE;}Status PrintElement( ElemType e ) { // 输出元素e的值printf("%d ", e );return OK;}// PrintElementStatus PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) { // 前序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
//补全代码,可用多个语句if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))return OK;return ERROR;}else return OK;} // PreOrderTraverseStatus InOrderTraverse( BiTree T, Status(*Visit)(ElemType) ){// 中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
//补全代码,可用多个语句if(T){if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild,Visit))return OK;return ERROR;}else return OK;} // InOrderTraverseStatu s PostOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) { // 后序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
//补全代码,可用多个语句if(T){if(PostOrderTraverse(T->lchild,Visit))if(PostOrderTraverse(T->rchild,Visit))if(Visit(T->data))return OK;return ERROR;}else return OK;} // PostOrderTraverseStatus Putout(BiTree T){PreOrderTraverse(T,PrintElement);printf("\n");InOrderTraverse(T, PrintElement);printf("\n");PostOrderTraverse(T,PrintElement);printf("\n");return OK;}//·······················非递归算法struct SqStack{BiTree *base; // 在栈构造之前和销毁之后，base的值为NULLBiTree *top; // 栈顶指针int stacksize; // 当前已分配的存储空间，以元素为单位}; // 顺序栈Status InitStack(SqStack &S){S.base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree));if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}Status Push(SqStack &S,BiTree e){if((S.top-S.base)>=S.stacksize){S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree));if(!S.base)return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}Status Pop(SqStack &S,BiTree &e){if(S.top==S.base)return ERROR;e=*--S.top;return OK;}Status StackEmpty(SqStack S){ // 若栈S为空栈，则返回TRUE，否则返回FALSEif(S.top-S.base==0)return TRUE;else return FALSE;}Status InOrderTraverse1(BiTree T,Status(*Visit)(ElemType e),SqStack S) {BiTree p;InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,p);if(!Visit(p->data))return ERROR;p=p->rchild;}}return OK;}//···························层次遍历typedef struct{BiTree *base; // 初始化的动态分配存储空间int front; // 头指针,若队列不空,指向队列头元素int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置}SqQueue;Status InitQueue(SqQueue &Q){Q.base=(BiTree*)malloc(MAXQSIZE*sizeof(BiTree));if(!Q.base)return ERROR;Q.front=Q.rear=0;return OK;}int QueueLength(SqQueue Q){// 返回Q的元素个数// 请补全代码return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}Status EnQueue(SqQueue &Q,BiTree e){// 插入元素e为Q的新的队尾元素// 请补全代码if((Q.rear+1)%MAXQSIZE==Q.front)return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;}Status DeQueue(SqQueue &Q,BiTree &e){// 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR // 请补全代码if(Q.front==Q.rear)return ERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK;}Status LevelTraverse(BiTree T,SqQueue Q)//层次遍历二叉树{InitQueue(Q);BiTree p;p=T;if(T)EnQueue(Q,T);// printf("%d",QueueLength(Q));while(QueueLength(Q)!=0){DeQueue(Q,p); //根结点出队printf("%d ",p->data); //输出数据if(p->lchild)EnQueue(Q,p->lchild); //左孩子进队if(p->rchild)EnQueue(Q,p->rchild); //右孩子进队}return OK;}void Change(BiTree T){BiTNode *p;if(T){p=T->lchild;T->lchild=T->rchild;T->rchild=p;Change(T->lchild);Change(T->rchild);}// return OK;}int BTreeDepth(BiTree T)//求由BT指针指向的一棵二叉树的深度{// int dep1,dep2;if(T!=NULL){//计算左子树的深度int dep1=BTreeDepth(T->lchild); //计算右子树的深度int dep2=BTreeDepth(T->rchild); //返回树的深度if(dep1>dep2)return dep1+1;elsereturn dep2+1;}else return 0;}//`````````````叶子结点数Status yezhi(BiTree T,SqQueue Q){int i=0;InitQueue(Q);BiTree p;p=T;if(T)EnQueue(Q,T);// printf("%d",QueueLength(Q));while(QueueLength(Q)!=0){DeQueue(Q,p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);if(!p->lchild&&!p->rchild)i++;}return i;}int main() //主函数{SqStack S;SqQueue Q,Q3;BiTree T=NULL,f,p;int i,n,e,a,b,c;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&e);InsertBST(T,e);}scanf("%d",&a);scanf("%d",&b);scanf("%d",&c);Putout(T);printf("%d\n",SearchBST(T,a,f,p));printf("%d\n",SearchBST(T,b,f,p));InsertBST(T,c);Putout(T);InOrderTraverse1(T, PrintElement,S);printf("\n");LevelTraverse(T,Q);printf("\n");Change(T);Putout(T);Change(T);Putout(T);printf("%d",BTreeDepth(T));printf("\n");printf("%d",yezhi(T,Q3));printf("\n");return OK;}//main完型填空There are many kinds of Computer languages. A typical imperative language contains an (1)_ sub language which approximates the mathematical abstractions of" timeless" functions applied to "space- less" values, where the actual operation sequences and use Of storage space duringexpression evaluation are organized behind the (2).In this setting, values are data structures of low volume, typically a few computer words or less, which means that an illusion of (3) can be realized by having intermediatere- suits during expression evalution stored at thediscretion of the language implementation, andeffecting pa- rameter (4)and (5)operations through value copying.(1) A. applicative B. mandatoryC. applicationD. voluntary(2) A. screen B. backgroundC. foregroundD. scenes(3) A. spaceful B. spacelessnessC. spacelessD. space(4) A. transportation B. tranverseC. transmissionD. translation(5) A. assignment B. dispatchC. valueD. design四翻译Query By Example (QBE)In database management programs ,a query technique ,developed by IBM for use in the QBE program ,that prompts you totype the search criteria into a template resembling the data record .The advantage of query-by-example retrieval is that youdon’t need to learn a query language to frame a query .When you start the search ,the program presents a screen that lists allthe data fields that appear on every data record ;enter information that restricts the search to just the specified criteria .Thefields lift bland ,however ,will match anything.Query LanguageIn database management programs ,a retrieval and data-editing language you use to specify what information to retrieve andhow to arrange the retrieved information on-screen or when printing .The dot-prompt language of dBASE is a full-fledgedquery language ,as is Structured Query Language (SQL) ,which is used for minicomputer and mainframe databases and isgrowing in popularity in the world of personal computers .The ideal query language is a natural language ,such as English. ARPAnetA wide area network (WAN) .A network that connected Department of Defense research sites across America. Created in1969 with funding from the Advanced Research Projects Agency (ARPA) .Undergoing constant research and development inthe early-to mid-1970s,ARPAnet served as the test bed for the development of TCP/IP( the protocols that make the Internet possible ).A Major goal of the ARPAnet project was to increase the military's command and control capability by enabling communication across a variety of physically dissimilar media ,including satellites .An allied goal was to create a robustnetwork capable of withstanding outages ,such as those that might result from a nuclear exchange .ARPAnet met these objectives ,but it also surprised its creators :It was found in short order that most ARPAnet users preferred to use the network for communication ,such as electronic mail and discussion groups .Initially ,the ARPAnet was available only to government research institutes and to universities holding Department of Defense (DoD) research contracts .In 1983,ARPAnet was divided into a high-security military network (Milnet )and an ARPAnet that was recast as a research and development network .Although it formed the foundation of the Internet ,it was decommissioned in 1990.。
