2013级DS作业和实验参考答案总汇(1)(4)

#C#F## Sample Output BDAC

DBEACF

//9063ANSWER CODE1 #include using namespace std; struct Binode{ char data; Binode *lchild,*rchild;}; Binode *Great() { Binode *bt;char ch; cin>>ch; if(ch=='#')bt=NULL; else { bt=new Binode; bt->data=ch; bt->lchild=Great(); bt->rchild=Great(); } return bt; }

Binode *copy(Binode *bt) { Binode *bt1; if(bt==NULL) return NULL; else { bt1=new Binode; bt1->data=bt->data; bt1->lchild=copy(bt->lchild); bt1->rchild=copy(bt->rchild); } return bt1; }

void Inorder(Binode *bt1) { if(bt1==NULL) return; else { Inorder(bt1->lchild); cout<data; Inorder(bt1->rchild); } };

int main() { int n; cin>>n; while(n--) { Binode *bt=Great(); Binode *bt1=copy(bt); Inorder(bt1); if(bt1!=NULL)

}

cout<

return 0;

//9063ANSWER CODE2 #include using namespace std;

struct BiNode{ char data; BiNode *lchild, *rchild;}; BiNode *Creat() { BiNode *bt;char ch; cin>>ch; if(ch=='#')bt=NULL; else { bt=new BiNode; bt->data=ch; bt->lchild=Creat(); bt->rchild=Creat(); } return bt; }

void InOrder(BiNode *root) {

if (root==NULL) return; //递归调用的结束条件 else{ InOrder(root->lchild); //中序递归遍历root的左子树 cout<data; InOrder(root->rchild); //中序递归遍历root的右子树 } }

//层序遍历复制二叉树

BiNode * copy_bitree(BiNode * root) { int front=-1,rear=-1,newfront=-1,newrear=-1; BiNode * Q[100],* newQ[100],*oldp,* newp,*newroot;

if(root==NULL ) return NULL;//空二叉树 oldp=root;

newp=new BiNode;

newp->data=oldp->data; newroot=newp;//新二叉树的根指针 Q[++rear]=oldp;//入队

newQ[++newrear]=newp;//入队 while(rear!=front) {

oldp=Q[++front];//出队

newp=newQ[++newfront];//出队

if(oldp->lchild==NULL) newp->lchild=NULL; else {

newp->lchild=new BiNode; newp->lchild->data=oldp->lchild->data; Q[++rear]=oldp->lchild; newQ[++newrear]=newp->lchild; } if(oldp->rchild==NULL) newp->rchild=NULL; else { newp->rchild=new BiNode; newp->rchild->data=oldp->rchild->data; Q[++rear]=oldp->rchild; newQ[++newrear]=newp->rchild; } } return newroot; }

void main() { int n; BiNode * root,*newroot; cin>>n; while(n--) { root=Creat(); newroot=copy_bitree(root); if(newroot==NULL) continue; }

}

InOrder(newroot);//中序遍历新二叉树 cout<

第九次作业：二叉树的高度宽度9057，9067

9057:Tree's Depth

Problem Description

一个名字叫Small Green的同学，很喜欢研究树的问题。某一天，他随意地在纸上乱涂乱画，画出了各不相同的二

叉树，他同时在想：一颗满的二叉树的深度并不难求。但如果要求出一颗二叉树（可能不是满二叉树）的深度，那么该如何求呢？ Input

输入包含多个例子，每个例子的第一行为一个整数n，表示以下有n组数据，每组数据占一行，为扩展二叉树的前序遍历序列（长度小于50，若节点为NULL则用'#'表示，否则用小写字母表示）。 Output

输出该二叉树的深度。 Sample Input 2

abcd####efg#### abcd####efg#h###i##

Sample Output

4 5

//9057ANSWER CODE1 #include using namespace std;

struct BiNode{char data;BiNode *lchild,*rchild;}; BiNode *Creat() { BiNode *p; char ch; cin>>ch; if(ch=='#') return NULL; else { p=new BiNode; p->data=ch; p->lchild=Creat(); p->rchild=Creat(); } return p; }

int Depth(BiNode *bt) { int l,r; if(bt==NULL) return 0; else { l=Depth(bt->lchild); r=Depth(bt->rchild); return (l>=r)?(l+1):(r+1); } }

main() { int n; while(cin>>n) { while(n--) { BiNode *p=Creat(); cout<

//9057ANSWER CODE2 #include using namespace std;

struct BiNode{char data;BiNode *lchild,*rchild;}; int deep;

BiNode *Creat(int i) { BiNode *p; char ch; cin>>ch; if(ch=='#') return NULL;