数据结构课本习题答案

《数据结构课本习题答案》由会员分享，可在线阅读，更多相关《数据结构课本习题答案（41页珍藏版）》请在装配图网上搜索。

1、数据结构第一章 绪论一、 单项选择题1、（1）A（2）B 2、（1）B（2）D 3、C 4、A 5、A 6、（1）C（2）A 7、（1）C（2）A 8、C 9、C 10、B 11、D二、填空题1、存储结构 、算法2、非线性结构3、线性、树型、 图形4、映射5、线性结构、树型结构 、图形结构6、有穷性、确定性 、可行性7、错误三、算法分析1、（1）O(n）、 (2)O(n) 、（3）O(n） 、（4）O(n)、 （5）O（） 、 （6）O（log3n）、 （7） O（log2n） 2、(1) order()函数是一个递归排序过程，设T（n）是排序n个元素所需要的时间。在排序n个元素时，算法的计算

2、时间主要花费在递归调用order()上。第一调用时，处理的元素序列个数为n-1，也就是对余下的n-1个元素进行排序，所需要的计算时间应为T(n-1)。又因为在其中的循环中，需要n-1次比较。所以排序n个元素所需要的时间为：T(n)=T(n-1)+n-1 n1据此可得：T(1)=0 T(2)=T(1)+1=0+1=1 T(n)=T(n-1)+n-1 n1求解过程为： T(n)=T(n-2)+(n-2)+n-1 =T(n-3)+(n-3)+(n-2)+n-1 = =(T(1)+1)+2+ n-1 =0+1+2+ n-1 =n(n-1)2 =O(n2)故order函数的时间复杂度为O(n2)（2）解

3、：设fact(n)数是T(n)。该函数中语句If (n1),return1;的运行时间是O（1），语句return(n*fact(n-1); 运行时间是T(n-1）+O(1),其中O(1)为乘法运算的时间。因此 T(n)=O（1） n1 T(n)= T(n-1)+O(1) n1则 T(n)=O(1)+T(n-1) =2*O(1)+T(n-2) = =(n-1)*O(1)+T(1) =n*O(1) =O(n)即fact(n)的时间复杂度为O(n)。（3）解：设Fn的时间复杂度为T(n)，有： T(n)=T(n-1)+T(n-2)2T(n-1) 2T(n-2) 2T(0) =O（2）又：T(n)=

4、T(n-1)+T(n-2)2T(n-2) 2T(n-4) 2T(1) （n为奇数时，或2T(0)，n为偶数时）即： T(n) O（2） 则：O（2）T(n) O(2)取最坏情况上限，即T(n) = O(2)。第二章、线性表一、单项选择题1、A 2、B 3、C 4、A 5、D 6、D 7、D 8、B 9、B 10、C 11、A 12、A 13、A 14、D 15、C 16、B 17、B 18、D二、判断题1、F 2、T 3、F 4、F 5、F 6、F 7、F 8、F 9、F 10、F三、填空题1、顺序2、n-123、pynext=pxnext; pxnext=py;4、n-i+15、（1）便于处

5、理首元结点，使得在创建链表和删除结点时，可以将首元结点与其他结点同等对待。 （2）利用头结点的数据域存储链表的相关信息6、O（1） O（n）7、单链表和多重链表 动态链表和静态链表8、fnext=pnext; fprior=p; pnextprior=f; pnext=f;9、指针10、物理上相邻 指针四、简答题1、（1）由于链式存储结构可以用任意的存储空间来存储线性表中的各数据元素，且其存储空间可以是连续的，也可以是不连续，此外，这种存储结构对元素进行插入和删除操作时都无需移动元素，而仅仅修改指针即可，所以很适用于线性表容量变化的情况。 （2）由于顺序存储结构一旦确定了起始位置，线性表中的任

6、何一个元素都可以进行随机存取，即存取速度较高；并且，由于线性表的总数基本稳定，且很少进行插入和删除，故这一特点恰好避开了顺序存储结构的缺点，因此，应选用顺序存储结构。2、不一定，由于链式存储需要额外的空间来存储指针，所以要比顺序存储多占用空间。在空间允许的情况下，链式存储结构可以克服顺序存储结构弱点，但空间不允许时，链表存储结构会出现新的问题。3、该线性表宜采用链表存储结构。因为采用链式存储结构的线性表，插入和删除操作只需要改变指针，时间复杂度为O（1），而采用顺序存储结构的线性表插入和删除涉及到数据的大量移动，时间复杂度为O（n）4、线性结构包括线性表、栈、队列、串，线性表的存储结构又分成顺

7、序存储和链式存储。用C语言描述顺序存储类型：Typedef struct ElemType datamaxlen; /存放元素 int len; /存放长度Sqlist;链式存储类型：Typedef struct node ElemType data ; /数据域 struct node*next; /指针域SNode;5、先找到值为23和15的两个结点，q指向值为23 的结点， p指向值为15 的结点，p和q结点互换： qllinkrlink=p; pllink=qllink; prlink=q;qllink=p; qrlink!=null;6、(1) prlinkllink=pllink；

8、 pllinkrlink= prlink； dispose (p) ; (2) new (q); qllink=p; qrlink=prlink; prlinkllink=q; prlink=q;五、算法分析1、Void Insert (Lnode *head , ElemType x, ElemType y) Lnode *q, p; q = head; p = qnext; while(pdata!=x & p!=null) q = p ; p = pnext ; if (p = = null) pnext=s;else s=( Lnode *) malloc(sizeof(Lnode )

9、; sdata=x; snext=p;qnext=s;2、Void getVoionList(SqList &A, SqList &B,SqList &C) node pa, pb, pc, q; pa=Anext; pb=Bnext;C = A;Anext=null;while (pa!=null & pb!=null)if (pa data = pbdata) q=pa; pa=panext;qnext=Cnext; Cnext=q; else q=pb; pb=pbnext;qnext=Cnext; Cnext=q; if (pa!= null) while (pa!= null) q=

10、pa; pa=panext;qnext=Cnext; Cnext=q; if (pb!=null)while (pb!=null)q=pb; pb=pbnext ;qnext =Cnext ;Cnext =q; 3、State changeList (SqList &heada,SqList &headb,int i,int len int j)node *a,*b ,p , q; a= heada ;b= headb; count=1; if(i= =1) for (k=1; k=len; k+) q= heada if (q= =NULL) return Error; heada= hea

11、danext; free(q); else while (a !=null & count i-1)a=anext; count+; if (a = = NULL) return Error; for (k=1; k=len; k+) qanext; if (q= =NULL) return Error; anext=qnext; free(q); if (pa = = NULL) return ok;p=pa;while(pnext!=NULL) p=pnext;if(j = =1)pnext =headb; headb=heada;else q = headb; count=1; whil

12、e (q!=null & countj-1) qqnext ;count+; If(q= =NULL) return Error; pnext=qnext; qnext=heada; return ok;4、在递增有序的顺序表中插入一个元素x，首先应查找待插入元素的位置。因顺序表元素递增有序，采用折半查找法比顺序查找效率高，查到插入位置后，从此位置直到线性表尾依次向后移动一个元素位置，之后将元素X插入即可。查找算法的时间复杂度为O（log n），而插入时的移动操作的时间复杂度为O（n），若用顺序查找，则查找的时间复杂度为O（n）。Void Insert(ElemType A,int size,

13、 ElemType x)low =1; high= num; while(lowx)high=mid-1; else low=mid+1; for(i=num; i=low; i- -) Ai+1=Ai; Ai+1=x;5、Struct pnode int coef; /系数 int exp; /指数 Struct pnode *Link;Struct pnode *padd(Struct pnode *heada, Struct pnode *headb) Struct pnode *headc, *p , *q , *r ,*s; int x; p=heada ;q=headb; head

14、c=( Struct pnode *)malloc(sizeof (Struct pnode ); r=headc; / R始终指向新链表中的最后一个节点 while (p!=NULL & q!=NULL)if(pexp= =qexp) /两指数相等时，将两系数相加生成一新节点插入C中 x=pcoef + qcoef; if(x!=0) s=( Struct pnode *)malloc(sizeof (Struct pnode ); scoef=x; sexp=pexp; rLink=s;r=s;p=pLink; q=qLink;p=pLink; q=qLink;else if(pexp q

15、exp) s=( Struct pnode *)malloc(sizeof (Struct pnode ); scoef= qcoef; sexp=pexp; rLink=s;r=s; q=qLink;elses=( Struct pnode *)malloc(sizeof (Struct pnode ); scoef= qcoef; sexp=pexp; rLink=s;r=s; p=pLink; if(p!=NULL) q=p;while(q!=NULL)s=( Struct pnode *)malloc(sizeof (Struct pnode ); rLink=s;r=s; q=qLi

16、nk;rLink=NULL;s=headc;headc= headcLink;free(s);return(headc);第三章、栈和队列一、单项选择题1、C 2、B 3、D 4、C 5、D 6、A 7、B 8、C 9、B 10、D 11、C 12、D 13、B 14、C 15、A 16、A 17、A 18、C 19、A 20、D二、填空题1、栈2、队尾、 队首、 栈顶、 栈顶3、删除运算的不同4、先移动栈顶指针，后存入元素5、先取出元素，后移动栈顶指针6、不可能的7、可能的8、O（1）9、S=NULL10、先取出元素，后移动队尾指针11、先存放元素，后移动队尾指针12、MAX-113、STf

17、ront= = STrear三、简答题1、解：Initstack(st); /空栈 Push(st , A); /栈内容: A Push(st , B); /栈内容: A 、B Push(st , C); /栈内容: A 、B、C Pop(st , x); /栈内容: A 、B Pop(st , x); /栈内容: A Push(st , D); /栈内容: A、D Push(st , E); /栈内容: A、D、E Push(st , F); /栈内容: A、D、E、F Pop(st , x); /栈内容: A、D、E Push(st , G); /栈内容: A、D、E、G Pop(st ,

18、 x); /栈内容: A、D、E Pop(st , x); /栈内容: A、D Pop(st , x); /栈内容: A2、解，本题利用栈的“后进先出”的特点，有如下几点情况： A进，A出，B进，B出，C进，C出，产生输出序列ABC A进，A出，B进，C进，C出，B出，产生输出序列ACB A进，B进，B出，A出，C进，C出，产生输出序列BAC A进，B进，B出，C进，C出，A出，产生输出序列BCAA进，B进，C进，C出，B出，A出，产生输出序列CBA不可能的输出序列CAB3、解显示队列中的内容如下：InitQueue(Q); /空队列Add Q (Q, A); /队中内容：AAdd Q (Q,

19、 B); /队中内容：A、BAdd Q (Q, C); /队中内容：A、B、CDel (Q); /队中内容：B、CDel (Q); /队中内容：CAdd Q (Q, D); /队中内容：C、DAdd Q (Q, E); /队中内容：C、D、EAdd Q (Q, F); /队中内容：C、D、E、FDel (Q); /队中内容：D、E、FAdd Q (Q, G); /队中内容：D、E、F、GDel (Q); /队中内容：E、F、GDel (Q); /队中内容：F、GDel (Q); /队中内容：G4、当元素d、 e、 b、 g、h入队后，rear=5, front=0; 元素d,e出队，rear=

20、5, front=2; 元素i、 j、 k、 l、m入队后，rear=10, front=2;元素b出队，rear=10, front=3;此时若再让n、 o、 p入队，由于rear=10,故队列溢出，入队和出队的变化函数如下图所示：（a）初始状态 （b）元素d、e、b、g、h入队 （c）元素d、e出队（d）元素i、j、k、l、m入队 （e）元素b出队5、解当元素d、 e、 b、 g、h入队后，rear=5, front=0; 元素d,e出队，rear=5, front=2; 元素i、 j、 k、 l、m入队后，rear=10, front=2;元素b出队，rear=10, front=3;此

21、时若再让n、 o、 p入队，rear=2, front=3;队列不会溢出。（a）初始状态 （b）元素d、e、b、g、h入队 （c）元素d、e出队（d）元素i、j、k、l、m入队 （e）元素b出队 （f）元素n、o、p入队四、算法分析1、解假设采用顺序栈结构。先退栈ST中所有元素，利用一个临时栈tmpst存放从ST栈中退出的元素，最后的一个元素即为所求，然后将临时栈tmpst中的元素逐一出栈并进栈到ST中，这样恢复ST栈中原来的元素。算法如下：ElemType bottom(stack ST) ElemType X, Y; Stack tmpst;InitStack (tmpst); /初始化临

22、时栈while (!Stack Empty (ST) /临时栈tmpst中包含ST栈中逆转元素 pop(ST,x); push(tmpst ,x);While(!Stack Empty (tmpst) /恢复ST栈中原来的内容 pop(tmpst,y); push(ST,y);return x;2、解：假设栈不带头结点，求栈中元素个数算法如下： Int count(SNode *top) SNode *p=top;int n=0;while (!=NULL) n + +; p=pnext; return (n);3、解：假设是循环顺序队列，建立一个临时栈tmpst，将指定队列Q中的所有元素出队

23、并入栈到tmpst栈中，这样Q中队列为空，再将栈tmpst中的所有元素出栈并入队Q中，这样Q队列中的内容发生了反转。算法如下：Viod reverse(Queue &Q) ElemType x; Stack tmpst;InitStack (tmpst); /初始化栈tmpstwhile(! QueueEmpty (Q)DeQueue (Q,x);push(tmpst,x); while(! Queue Empty (tmpst)pop (tmpst,x); EnQueue(Q,x);4、解：假设是循环顺序队列，没有取队尾元素的基本运算。建立一个临时队列tmpqu,将指定队列qu的所有元素出队

24、并如队到tmpqu这样qu队列为空，再将队列 tmpqu中的所有元素出队并入队到 qu队中，最后的一个元素即为所求。算法如下：ElemType last (Queue qu) ElemType x; queue tmpqu; initQueue(tmpqu); while (!QueueEmpty (qu) DeQueue (qu,x); EnQueue(tmpqu,x);while (!QueueEmpty (tmpqu)DeQueue (tmpqu,x); EnQueue(qu,x); return x;5、解：该共享栈的结构如下图所示： 两栈的最多元素个数为m, top1是栈1的栈指针，

25、top2是栈2的栈指针，当top2= top1+1时出现上溢出，当top1=0时栈1出现下溢出，当top2=m+1时栈2出现下溢出。算法如下：/top1，top2和m均为已赋初值的int 全局变量Int push(ElemType x,int i)if(top1= =top2-1) /上溢出return 0; /返回出错信息else if(i= =1) /对第一个栈进行进栈操作 top1 +; Ctop1=x; else /对第二个栈进行进栈操作 top2 - -; Ctop2=x; return 1; /返回成功信息int pop(int i, ElemType &x)if(i= =1) /

26、对第一个栈进行出栈操作 if(top1= =0) /栈1下溢出 return 0; /返回出错信息 else x=ctop1; top1- -; else /对第二个栈进行出栈操作if(top2 = =m+1) /栈2下溢出 return 0; /返回出错信息else x=ctop2; top2+ +; return 1; /返回成功信息Void set null(int i)if(i= =1) top1=0; else top2=m+1;6、解：定义队列类型如下：Typedef struct SNode *rear;QType 2;（1）队列插入一个结点的操作是在队尾进行的，所以应在该循环链

27、队的尾部插入一个结点，算法如下：EnQueue (QType 2 *&qu, ElemType x) /向队列中插入X结点SNode *s;s=( SNode *)malloc(sizeof (SNode ); /建立一个新结点sdata=x;if(qurear = =NULL) /循环队列为空，则建立一个结点的循环队列qurear=s; qurearnext=s; else /循环队列不为空，则将*S插到后面snext= qurearnext; qurearnext=s; qurearnext rear=s; / qurear始终指向最后一个结点(2)队列的删除结点是在队头进行的，所以删除该

28、循环链表的第一个结点，算法如下：Int DeQueue (QType 2 *&qu, ElemType &x) SNode *p;if (qurear = =NULL) /队列下溢出 return 0; /返回出错信息 elsep=qurearnext; / p指向队头结点x=pdata; if(p= =qurear) /队列只有一个结点，则直接删除该结点qurear = =NULL;else qurearnext = pnext; /否则删除第一个结点free(p); /释放队头结点 return 1; /返回成功信息7、解：求该链队中结点个数实际上是计算以top front 为头指针的单链

29、表中结点个数。算法如下：Int Qucount (LQueue *top) SNode *p= topfront; int n=0; while (p ! = NULL)n+ +; p=pnext; return (n);8、解：写递归函数要清楚结束递归的条件是什么，在此处已知n为大于等于零的正整数，递归算法如下：Int f (int n) if (n0) return 0;if (n= =0) return 1;else return n*f (n/2);9、解：void tranf (int a ,int r)/ a是十进制，r是任意进制数 SeqStrack s; int m, int

30、x; InitStrack (&s); stop =0; while (a!=0) m =a % r; /进行求余运算 push (&s , m); /把取得的的余数进栈 a=a / r; /进行取整运算 While (s.top ! = 0) /当栈不空，依次出栈 pop(&s ,&x); printf (“%d”, x);第四章 串一、单项选择题1、C 2、D 3、D 4、B 5、C 6、28 7、 8、B 9、B二、填空题1、顺序存储方式和链式存储方式2、两个串的长度相等且对应位置的字符相3、由一个或多个空格字符组成的串 ， 其包含的空格个数4、不相同的5、196、7、01122312

31、三、算法分析1、2、void strcopy (Stringtype *s, Stringtype t ) /串复制 int i;for (i=0; i0) sj+=stki- /将第偶数个字符逆序填入原字符数组第五章、数组和广义表一、单项选择题1、B 2、(1) L 、(2)J 、(3)C、(4)I、（5）C 3、B 4、B 5、A 6、H、 C 、E 、A、F 7、B 8、B 9、B 10、B 11、B 12、A 13、B 14、B 15、D 16、C、B 17、A 二、判断题1、F 2、T 3、T 4、F 5、F 6、F 7、T 8、F 9、F 10、F三、填空题1、顺序2、9572 1

32、2283、9174 87884、其余元素组成的表5、（1）原子是结构上不可再分的，可以是一个数或一个结构；而表带结构本质上就是广义表，因作为广义表的元素故称为子表。 （2）大写字母 （3）小写字母 （4）表中元素个数 （5）表展开后所含括号的层数6、深度7、（1）（） （2）（） （3）2 （4）28、head(tail(head(tail(H)9、(b)10 、(x, y, z)四、简答题1、答：元素A4、2、3的存储首地址为958。三维数组以行为主序存储，其地址公式loc(Aijk)=loc(Aclc2c3)+(i-C1)V2V3+(j-C2)V3+(k-C3) 其中 Ci 、di是各维的

33、下界和上界，vi =di-ci+1是元素个数，L是一个元素所占的存储单元数。2、答：b对角矩阵的b条对角线在主对角线上方和下方各有b/2条对角线。从第1行至第a行，每行上的元素依次是a+1，a+2，, b-2, b-1,最后的a行上的元素个数是b-1, b-2, a+1。中间的（n-2a）行，每行的元素个数是b，故b条对角线上的个数为（n-2a）b+ a*（a+b）。存放在一维数组V1nb-a (b-a)中,其下标k与元素在二维数组中的下标i和j的关系为: k= k=a(2i-a)+j, 当a+1in-a+1时 k= a(2i-a)-, 当n-a+1in时3、答：1784 (公式：loc(Ai

34、jkl)=100(基地址)+(Ci-C1)V2V3V4+(j-C2)V3V4+(k-C3)V4+(1-C4)*4)4、答：1210+108L（公式：loc(A1,3,-2=1210+(k-C3)V2V1+(j-C2)V1+(i-C1)*L(设每个元素占L个存储单元)5、答：数组占的存储字节数=10*9*7*4=2520；A5，0，7的存储地址=100+4*9*7+2*7+5*4=11846、答：广义表的第一种存储结构的理论基础是，非空广义表可唯一分解成表头和表尾两部分，而由表头和表尾可唯一构成一个广义表。在这种存储结构中，原子和表采用不同的结点结构，原子结点两个域；子表结点三个域；对非空广义表

35、不断进行表头和表尾的分解，表头可以是原子也可以是子表，而表尾一定是表。下面是本题的第一种存储结构图：1 1 1 1 1 0 A AA 1 1 1 1 0 C0 E 0 B 1 1 0 F 0 D广义表的第二种存储结构的理论基础是，非空广义表最高层元素间具有逻辑关系；第一个元素无前驱有后继，最后一个元素无后继有前驱，其余元素有唯一前驱和唯一后继。在这种存储结构中，原子和表均采用三个域的结点结构，结点中都有一个指针指向后继结点。在画这种存储时，从左往右一个元素一个元素地画，直至最后一个元素。1 1 0 A 1 1 0 B1 0 E 0 F 0 C 0 D 五、算法分析1、本题要求从n个数中，取出所

36、有k个数的所有组合。设数已存于数组A1A中.为使结果唯一,可以分别求出包括An和不包括An的所有组合.即包括An时,求出从A1n-1中取出k-1个元素的所有组合,不包括An时,求出从A1n-1中取出k个元素的所有组合.Const n=10; k=3;Type Arr=Array1n of integerVAR A, B:ARR;PROC outresult; /输出结果FOR j:=1 TO k DO write(Bj); write(n);ENDP; PROC nkcombination(i, j, k:integer); IF k=0 THEN outresult ELSE IF(j-k0

37、) THEN Bj:=Ai; j:=j+1; nkcombination(i-1, k-1,j);nkcombination(i-1, k,j-1);ENDP;2、void Translation(float *matrix,int n) int i, j, k, 1; f loat sum, min; float *p, *pi, *pk; for(i=0; in; i+)sum=0.0; pk=matrix +i*n; for (j=0;jn; j+) sum+=*(pk); pk+; *(p+i)=sum; / for ifor (i=0; in-1;i+)min= *(p+i); k=

38、I; for (j=i+1; jn; j+) if (pjmin) k=j; min=pj; if(i!=k)pk=matrix +n*k; pi = matrix +n*I; for (j=0;jn; j+)sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;Sum=pi; pi=pk; pk=sum;/if/for ifree (p);/TranSlation3、（1）int BiForm(int n,k) if (n0 | k=n) printf (“参数错误n”);exit(0);if (k= =0 | k= =n) return(1);else ret

39、urn(BiForm(n-1,k)+ BiForm(n-1,k-1);(2)C(6,4)的递归树: C(6,4) C（5，4） + C（5，3） C（4，4）+ C（4，3 C（4，3）+ C（4，2） C（3，3）+ C（3，2） C（3，3）+C（3，2） C（3，2） + C（3，1） C（2，2）+ C（2，1） C（2，2）+C（2，1）C（2，2）+C（2，1）C（2，1）+C（2，0） C（1，1）+C（1，0）C（1，1）+C（1，0）C（1，1）+C（1，0）C（1，1）+C（1，0） (3)计算C(n,k) (0kn)的非递归算法: int cnk(int n,int k)

40、int i; long x=1, y=1;for (i=1;i=k; i+) x*=i;for(i=n-k+1; idep2)return dep+1;else return dep2+1;2.解答：使用一个栈stack，首先将根节点入栈，开始循环：从栈中退出当前节点p，先访问它，然后将其右节点入栈，再将其左节点入栈，如此直到栈空为止。算法如下：void porder(BTree *b) BTree *stackMaxsize,*p;int top=1;if (b!=NULL) top+; stacktop=b; while(top-1) P=stacktop; top-; cout data

41、 right!=NULL) top+; stacktop=p-right;if(p-left!=NULL)top+;stacktop=p-left;3.根据后序遍历二叉树的递归定义，转换成非递归函数时采用一个栈保存返回的节点，先扫描根节点的所有左节点并入栈，出栈一个节点，然后扫描该节点的右节点并入栈，再扫描该右节点的所有左节点并入栈，当一个节点的左右子树均访问后再访问该节点，如此这样，直到栈空为止。其中的难点是如何判断一个节点t的右节点已访问过，为此用p保存刚访问过的节点（初值为NULL），若t-right=p成立（在后序遍历中，t的右节点一定刚好在t之前访问），说明t的左右子树均已访问，现在

42、应访问t。算法如下：void psorder(BTree *t) BTree *stackMaxsize;BTree *p;int flag, top=-1;do while (t) top+; stacktop=t; t=t-left; p=NULL;flag=1;while(top!=-1 & flag) t=stacktop;if (t-right!=p) cout data right; flag=0;while(top!=-1) ;4. 解析：本题采用递归算法，设h指定p所指结点的高度，其初值为-1。找到指定的结点返回其层次；否则返回-1。作为一个中间变量在计算其搜索层次时使用，其初值为1。算法如下:void level(Btree *p，int &h，int lh) if (b=NULL)h=-1；else if (p=b)h=lh；else level(b-left， p， h，lh+1) ；if(h=-1) level(b-right， p，h， lh+1) ；5.解析：本算法要用一个队列q，先将二叉树根节点入队列，然后退队列，输出该节点，若它有左子树，便将左子树根节点入队列，若它有右子树，便将右子树根节点入队列，如此直到队列空为止。因为队列的特点是先进先出，从