数据结构学习指导2(算法指导-线性表和树)

1、数据结构学习指导（2）数据结构算法学习参考（线性表和树）1 线性表（一）线性表的定义n（n=0）个元素的有限集合，(a1,a2,.,ai-1,ai,ai+1,.,an)。每个数据元素的类型是相同的，数据元素之间的相对位置是一维的(线性的)（二）存储结构（1） 顺序结构datatype asize+1; / 线性表的容量int n ; / 线性表的长度（2） 链式结构typedef struct node datatype data; / 数值域 struct node * next; / 指针域 node, *linklist;（三）算法设计2.1 设线性表存于a1。size的前n个分量中,

2、且递增有序，将x插入到线性表的适当位置, 以保持线性表的有序性。设计思想：(1) 查找x的插入位置i。从an处开始，边比较边后移 。(2) 将x查入到ai+1中，表长加1。void insert( datatype a,int n,datatype x) /在有序表a1.an中插入x, 并保持线性表的有序性 if ( n = size) cout”array overflow”=1) & (x=1） & （i=1） & （i+k-1=n） ) for (j=i+k ;j=n;j+) aj-k=aj; /前移k个元素 n-=k; /表长-kelse cout”入口参数错误”endl;2.3已知两

3、个线性表la和lb，且顺序存储，其值递增排列，要求将它们归并成一个新的有序表lc。设计思想：(1) 当线性表la和线性表lb均未结束时，比较，将较小数存于线性表lc;(2) 若一线性表结束，将另一线性表存于lc。void merge_1( datatype la,datatype lb,datatype &lc,int na, int nb, int &nc) /将长度为na的有序表la和长度为nb的有序表lb归并为一个长度为nc的有序表lc/ 设lc表的存储空间足够大 int i=1,j=1,k=0; /指针初始化while (（i=na） & （j=nb）) /归并 if (lai=lbj

4、) lc+k=lai+; else lc+k=lbj+; while (i=na ) lc+k=lai+; / 插入la的剩余段 while (j=nb ) lc+k=lbj+; /插入lb的剩余段 nc = k; /k为lc中元素个数 2.4 一个有序表以顺序结构存储，删除该表中所有大于min且小于max的元素。设计思想：(1) 首先找到第1个被删元素（大于min且小于max的元素）；(2) 记住这个位置k;(3) 从k+1开始将小于min 或 大于 max 的元素前移（要注意移动位置），并计被删元素的个数n1(4) 表长-n1Void delete_2 ( int a,int n, int

5、 min, int max) /删除线性表中所有大于min且小于max的元素。 int k=1,n1=0,j; while (k=n&(akmin|akmax)k+; /(1) 找到第一个被删条件元素的位置k j=k+1;while (j=n) if (aj=max) ak+=aj+; / 删除所有大于min且小于max的元素,也即将aj=max的元素前移else n1+; j+; / 当 minmin且aknext; /p:指向第一个元素结点 while ( p & p-data!=x) p=p-next; /当p不空并且p-data不等于x时, p后移 return(p); /成功: p

6、; 失败:p=NULL LENGTH: 逐一访问每一结点并计数, 即可得此链表的长度。int length(listlink &ha) / ha:带头结点的单链表的头指针 node *p=ha; /p:指向头结点 int len=0; while (p-next) p=p-next; +len; /当p不空x时, 访问其结点, 并计数 return(len);/len:即为此链表的长度 2.12已知ha和hb分别指向两个单链表的头结点, 且头结点的数据域(整型)中存放链表的长度, 写一算法将这两个链表接在一起, 并要求以尽可能短的时间完成。设计思想： (1) 比较ha和hb两链表, 找较短链；

7、(2) 沿较短链找到最后一个结点；(3) 将两链连接上。 void concat( linklist ha, linklist hb, linklist &hc) if ( ha-data data ) p=ha; q=hb-next else p=hb; q=ha-next / p指向较短链, q指向较长链hc=p;/ 将头指针指向较短链, hc:新生成的链表的头指针, 利用原空间while (p-next) p=p-next;/ 沿较短的链表查找至链表尾端(当p-next=NULL),若p不空, 则p后移, 直到最后一个结点p-next = q； /两链表链接上2.13已知线性表中的元素按

8、值递增排列, 并以单链表作存储结构， 写一高效算法, 删除表中所有值大于min且小于max的元素(若表中存在这样的元素)。设计思想：(1) 从第一个结点开始找其值min的结点p(它的前趋结点为pre)；(2) 保存pre, 从p开始找所有值next指向p。void delete_3(linklist &h,int min, int max) / h:带头结点的单链表的头指针 node *pre=h, *p=h-next; while (p & p-datanext; /p:其值min的结点, pre是p的前趋while (p & p-datanext; delete u; / 删除所有的其值m

9、in并且next=p; 2.14已知线性表中的元素按值递增排列, 并以单链表作存储结构， 写一高效算法, 删除表中的多余元素, 使得运算后的线性表中所有元素的值均不相同。设计思想：从第一个结点开始, 每一结点的值与后一结点的值作比较 , 若相等, 则删除后一结点, 直至整个链表结束。void delete_4(linklist &h) / h:带头结点的单链表的头指针 linklist u,p=h-next; while (p-next) if (p-data=p-next-data ) u=p-next; p-next=u-next; delete u; / 删除元素的值相同值的结点 els

10、e p=p-next; /p后移 2.15以单链表作存储结构, 实现线性表就地逆置的算法, 即将线性表 (a1,a2,.an)=(an,.,a2,a1)设计思想：(1) 首先建立一个空链表 ( 逆置后链表的初值)；(2) 取出原链表(a1,.,an)中的一结点；(3) 插入到新链表(an,.,a1序)的表头处;(4) 重复(2)和(3)步, 直到原链表空止。Void exchange( linklist ha, linklist &hb)/ (a1,a2,.an)=(an,.,a2,a1) /ha:原链表的头指针，hb：逆置后新链表的头指针。两链表均不带头结点node *p;hb=NULL;

11、/新链表置初值 while (ha) p=ha; ha=ha-next; / 从原链表的表头中取出一个结点pp-next=hb; hb=p; / 将p插入到新链表的表头处 2.16设有两个按元素值递增有序排列的线性表A和B, 均以单链表作存储结构, 写一算法将A表和B表归并成一个按元素值递增有序排列(表中各值均不相同)的线性表C。设计思想：(1) 当A表和B表都不空时, 进行比较, 将较小数链入C表表尾, 以保证其递增性;(2) 若某一链表空, 将另一链表接在C表之后。void merge_2 ( linklist ha, linklist hb, linklist &hc)/ha,hb是两个

12、链表（有序表）的头指针,hc是归并后的新链表（有序表）的头指针，均带头结点 node *pa,*pb,*rc;pa=ha-next; pb=hb-next; hc=ha; rc=hc; /利用原链表A的头结点，得新链表C的头结点, hc:头指针, rc:尾指针while (pa & pb) if (pa-datadata) s=pa; pa=pa-next; else if (pa-data=pb-data) s=pa; pa=pa-next; pb=pb-next; else s=pb; pb=pb-next; rc-next=s; rc=s; / 当A表和B表都不空时, 进行比较, 将较小

13、数链入C表表尾, 以保证其递增性; if （!pa） rc-next=pb； else rc-next=pa; delete hb;2.16 已知A、B和C为以链表存储的三个递增有序的线性表，对A作如下运算：删除那些在B中出现又在C中出现的元素。设计思想 : 从A表中取出每一个元素p-data，检查是否出现在B表和C表中，是，则删除P。 注意：应保留p的前趋。void delete_5(linklist &ha,linklist hb,linklist hc) / ha,hb,hc分别为A链、B链和C链的头指针, 3个链表均带头结点 node *pre, *p, *pb, *pc; pre=h

14、a; p=ha-next; /pre:p的前趋 pb=hb-next; pc=hc-next; /pb,pc:总指向hb,hc链的最后一个已考查的结点 while( p ) /A表不空 x=p-data; while ( pb & pb-datanext; /当pb不空时，找等于x的结点pb while ( pc & pc-datanext; /当pc不空时，找等于x的结点pc if (pb & pb-data=x) & (pc & pc-data=x) /x在B中出现同时又在c中出现 pre-next=p-next; free(p); /删除p p=pre-next /p后移，考察下一结点

15、else pre=p; p=p-next; /p后移 ，考察下一结点 2.17 已知由单链表表示的线性表中，含有三类字符的数据元素（字母、数字、其它字符）,编写算法构造三个循环链表。设计思想：检查每一结点，若是字母字符，链入h1链，若是数字字符，链入h2链，若是其它字符，链入h3链。void ds0217(linklist &h1,&h2,&h3)/ h1:原链表的头指针，后存放字母 h2,h3:数字和其它链表的头指针 p=h1-next; h1-next=h1;p1=h1 /利用h1作为字母链的头结点 h2=(linklist)malloc(sizeof(node); h2-next=h2;

16、 p2=h2;/生成数字链表的头结点 h3=(linklist)malloc(sizeof(node); h3-next=h3; p3=h3;/生成其它链表的头结点 p=h-next; /p指向第一个元素结点 q=h; /q是p的前趋 while (p) s=p; p=p-next; /p后移，将s插入相应的链表中 if (s-data=A & s-datadata=a & s-datanext=p1-next; p1-next=s; else if (s-data=0 & s-datanext=p2-next; p2-next=s; else s-next=p3-next; p3-next=

17、s; /ds02172.18 n个人坐在圆桌边, 从第s人开始报数, 报到第m人出列, 再从下一人开始报, 直至所有的人都出列为止。 设n=8,s=1,m=4 。 则出列次序为: 4,8,5,2,1,3,7,6设计思想：以循环链表存储，且不应有头结点； 在循环链表中查找，到第m处，删除（报数）void ds0218(linklist &r)/ r: 循环链表的尾指针 p=r;/从第p人开始报数 for (i=1;i=n;+i) for (j=1;jnext; /p定位于要出列人之前 printf(p-next-data); /报数 s=p-next; p-next=s-next; free(s

18、); /出列2.19 已知单向循环链表表示的线性表中含有三全域:pre、data和next, 其中 data为数据域,next为指针域,其为后继, pre也是指针域, 其值为NULL。 写一算法, 将此链改为双向链表。设计思想： 检查链表中的每一结点, 若其pre为空, 则将它指向其前趋结点。 void ds0219(linklist &ha)/ ha:链表的头指针 p=ha; while (p-next-pre=NULL) p-next-pre=p; p=p-next; 2.20 写出双向链表倒置的算法。设计思想：p从next方向，q从pre方向逐一对两个结点的数据进行交换，直至p=q或p-

19、pre=q止，使得双向链表被倒置。void ds0220(dlinklist &dh);/dh:指向双向循环链表的头结点 q=dh-pre; p=dh-next; / /q沿前趋指针方向,p沿后继指针方向 while (p!=q & p-pre!=q) q-datap-datat; p=p-next; q=q-pre 2.21 在其元素值按递增排序的双向链表中增加一个freq频度域(初值为0), 每当进行LOCATE(L,X)运算时, X结点的freq加1, 写一算法完成LOCATE(L,X), 并保证其有序性。设计思想：(1) 从第一个结点开始，逐一比较每一结点的数据中是否当等于x，若相等，

20、则转(2)。(2) x结点的freq+1。(3) 删除值为x的结点。(4) 从x结点开始向前以freq比较，找到x结点的恰当位置，插入该结点， 保证其递减性。void ds0221(dlinklist &h,elemtype x ) / h带头结点的链表的头指针, 头结点的freq=max p=h-next; /p指向第一个元素结点 while (p & p-data!=x) p=p-next; if （p=NULL）error(“没找到”)else p-freq=p-freq+1;q=p-pre; while (q-freq freq ) q=q-pre; if (q-next!=p ) p

21、-pre-next=p-next; p-next-pre=p-pre; /删p q-next-pre=p; p-next=q-next; p-pre=q;q-next=p; /p插入到q之后 思考题：2.22 已知值为整数的若干结点构成了带表头结点的单向链表A。请建立单向链表B和C，结点的值从A链表中拷贝，并且B链表中各结点的值都是奇数，C链表中各结点的值都是偶数。2.23 已知值为整数的若干结点构成了带表头结点的单向链表A。请将值为奇数的结点从A链表中分离出来，构成单向链表B，同时，从A链表中删除这些结点。2.24 已知A,B是两个不带表头结点的单向链表，表中各结点按值非降顺序排列。请将B链

22、表并入A链表中。2.25 设非空线性表（a1，a2，an）用带表尾指针的循环单向链表表示。请将该线性表改造成 （an，an1,a1）。2.26 从键盘输入n个整数，建立带表头结点的循环双向链表。要求链表中n个整数的排列顺序与它们的输入顺序相反。2.27 设非空线性表（a1，a2，an）用带表头指针的循环双向链表表示。请设计算法，判断该线性表是否为对称表（满足条件a1=an，a2=an1，）。2.28 用带表头结点的单向链表表示集合，实现集合的交运算：C=A*B。2.29 用带表头结点的单向链表表示集合，实现集合的差运算：C=AB。2.30 用带表头结点的单向链表表示集合，实现集合的并运算：C=

23、A+B。2 树和二叉树（一）树和二叉树的定义树的定义：树中n(n=0)个结点的有穷集T, 且在T上定义了一个关系R:(1) 仅的一个根结点；(2) 其余结点可分为m(m=0)个互不相交的有限集T1,.Tm, Ti子树。二叉树的定义：二叉树或空,或由根和两棵互不相交的左子树和右子树组成.（二）存储结构typedef struct bitnode datatype data struct bitnode *lchild,*rchild; /二叉树的左、右孩子 或 树的左孩子、右兄弟 Bnode,*Btree（三）涉及的有关算法1 栈的基本运算（1） push(S,x): x入栈（在n+1处插入x）

24、（2） pop(S,x):栈顶元素x出队（3） gettop(S):取栈顶元素（4） initstack(S):初始化栈（设置一个空栈）（5） emety(S):判栈空否2 队列的基本运算（1） enqueue(Q,x): x入队（在队尾处插入x）（2） delqueue(Q，x):队首元素x出队（3） getfront(Q):取队首元素（4） initqueue(Q):初始化队列（设置一个空队列）（5） emety(Q):判队列Q空否（四）算法设计6.1已知一棵完全二叉树存于顺序存储结构a1.an中, a1.an含结点值。 编一算法建立二叉链存储结构.方法一:借助队列实现void ex6_1

25、(Bnode *bt, datatype a) initqueue(Q);/置空队列 bt = (Bnode*)malloc(sizeof(Bnode); /生成头结点，bt:头指针 bt-data=a1; enqueue(Q,bt);/根结点入队 for （i=1;idata=a2*i; q-lchild=p;/建立左子树 enqueue(Q,p); /左孩子入队 if (2*i+1data=a2*i+1; q-rchild=p;/建立右子树 enqueue(Q,p);/右孩子入队 /ex6_1方法二:用递归算法实现void create(Bnode *bt,int i,datatp a)

26、bt = (Bnode*)malloc(sizeof(Bnode); /生成一个新结点 bt-lchile=bt-rchile=NULL; if (2*ilchild,2*i,a); if (2*i+1rchild,2*i+1,a);6.2 以二叉链表作为存储结构, 编一算法判别给定二叉树是否为完全二叉树.int ex6_2( Bnode *bt) b=1; initqueue(Q); / 初始化队列enqueue(Q,bt);/根结点入队 while ( getfront(Q)!=NULL) /当队首元素列不空时 delqueue(Q,bt);/队首结点出队 enqueue(Q,bt-lch

27、ild);/左孩子入队 enqueue(Q,bt-rchild);/右孩子入队/ 依二叉树性质5可知，若队首元素已为空，则队中所有的元素应该都是空，否则，该树就不是一个完全二叉树 while ( ! empty(Q) ) delqueue(Q,bt); if (bt) b=0; return(b);/ex6_26.3 已知一棵以二叉链为存储结构的二叉树,编写按求每一结点所在的层次的算法.void ex6_3(Bnode *bt) initqueue(Q);/初始化队列 enqueue(Q,(bt,1);/根及所在层1（bt,1）入队 while ( ! empty(Q) ) /当队列不空时 d

28、elqueue(Q,(f,level); / 队首元素（f,level）出队列 printf(f-data,level);/按层次访问每一结点,并输出它所在的层次 level+; if (f-lchild!=NULL) enqueue（Q,(f-child,level)）; /左孩子及层数入队 if (f-rchild!=NULL) enqueue（Q,(f-rchild,level)）;/右孩子及所在层入队 /ex6_36.4 已知一棵以二叉链为存储结构的二叉树,编写按层次顺序(同一层自左至右)遍历二叉树的算法.void ex6_4(Bnode *bt) initqueue(Q);/设置一个

29、空队列 enqueue(Q,bt);/根结点入队 while ( ! empty(Q) ) / 当队不空时 delqueue(Q,f); /队首结点出队列 VISITE(f-data); /按层次顺序（第一层从左至右的顺序）访问每一结点 if (f-lchild) p=f-lchild; enqueue(Q,p); /非空左孩子入队 if (f-rchild) p=f-rchild; enqueue(Q,p); /非空右孩子入队 /ex6_46.5 假设以三元组(F,C,L/R)形式输入一棵二叉树的各边(F:双亲, C:孩子, L/R:C是F的左或右孩子),且C是按层次顺序出现的. C=NUL

30、L时输入结束. 用一算法建立二叉链.void ex6_5(Bnode *bt)/ initqueue(Q);/设置一个空队列Q read(f,c,lr); / 以三元组形式读入。f:c的双亲结点，lr：c的左/右孩子 bt = (Bnode*)malloc(sizeof(Bnode); bt-data=c; /生成根结点; enqueue(Q,bt);/根结点入队 read(f,c,lr); / 以三元组形式读入。f:c的双亲结点，lr：c的左/右孩子 while ( c!= )/:结束标志 while ( getfornt(Q)!=f ) delqueue(Q,f); /保持队首元素是双亲结

31、点 p = (Bnode*)malloc(sizeof(Bnode);/生成新结点p p-data=c; p-lchild=p-rchild=NULL; enqueue(Q,p);/p入队 if (lr=l) getfront(Q)-lchild=p; /建立左子树 else getfront(Q)-rchild=p; /建立右子树 read(f,c,lr); / 以三元组形式读入。f:c的双亲结点，lr：c的左/右孩子 /ex6_56.6 以二叉链为存储结构, 写出先根遍历二叉树的非递归算法.void preorder(Bnode *bt) initstack(s);/设置一个空栈 whil

32、e ( bt|! empty(s) if (bt) visite(bt); push(s,bt); bt=bt-lchild; /访问根结点，根结点入栈，遍历左子树 else pop(s,bt); bt=bt-rchild ; / 栈顶结点出栈，遍历右子树 /preorder6.7 以二叉链为存储结构, 写出中序遍历二叉树的非递归算法void inorder(Bnode *bt) initstack(s); while ( (bt) | !empty(s) if (bt) push(s,bt); bt=bt-lchild ; else pop(s,bt); visite(bt); bt=bt-

33、rchild; 6.8 以二叉链为存储结构, 写出后根遍历二叉树的非递归算法.void postorder(Bnode *bt)/ 以非递归算法实现 i. 当右子对为空时, 可访问根结点; ii. 当右子树已访时, 可访问根结点. initstack(s);/设置一个空栈 do while ( (bt!=NULL) ) push(s,bt); bt=bt-lchild ; /沿着左子树，找到空止。也即访问空的左子树 p=NULL;/p：访问标志，初值为空。若某一结点的右子树为空也是如此。 while ( ! empty(s) )/当栈不空时 bt=gettop(s); /取栈顶结点if (bt

34、-rchild=p) /若p已访或p为空，则可以出栈，并访问根结点 visite (bt); p=pop(s); / p:访问标志，记最后访问过的结点 else bt=bt-rchild ; /遍历右子树break ; while （!empty(s)）; /postorder6.9 以二叉链为存储结构, 编写求二叉树的结点数目的递归算法。 一.用递归函数实现int nodes(Bnode *bt) /bt:二树的根 if (bt=NULL ) n=0; /空的二叉树中，有0个结点 else n=1+nodes(bt-lchild)+nodes(bt-rchild) ;/ 1（有且仅有1个根结

35、点）+ 左子树的结点数 + 右子树的结点数 return n;/nodes二.用递归过程实现void nodes(Bnode *bt) / bt:指向二叉树的根结点。 n:全程量, 计二叉树的结点个数，初值=0。/ 可以用先序遍历、中序遍历和后序遍历方法实现 if (bt!=NULL ) n+; /按先序遍历的次序访问二叉树中的每一个结点，并计数 nodes(bt-lchild); nodes(bt-rchild) ; 三.用带变参的递归过程来实现void nodes(Bnode *bt,int &n) /bt:二树的根 if (bt!=NULL ) nodes(bt-lchild,n); n

36、odes(bt-rchild,n); n=n+1; /nodes6.10 以二叉链为存储结构, 编写求二叉树的叶子数的递归算法。 一.用递归过程实现VOID leaf(Bnode *bt) /bt:二树的根, i:全程量, 初值=0 IF (bt!=NULL ) if (bt-lchild=NULL & bt-rchild=NULL) i=i+1; leaf(bt-lchild); leaf(bt-rchild) ; 二.用递归函数实现int leaf(Bnode *bt) /bt:二树的根 if (bt=NULL ) f=0; else if (bt-lchild=NULL & bt-rch

37、ild=NULL) f=1; else f=leaf(bt-lchild)+leaf(bt-rchild); return f;6.11 以二叉链为存储结构, 写出将二叉树中所有结点的左、右孩子相互交换的递归算法.VOID exchang(Bnode *bt) IF (bt!=NULL ) bt-lchild bt-rchild; exchang(bt-lchild); exchild(bt-rchild); / 只能用先序遍历和后序遍历方法实现。注意不能用中序遍历方法实现。6.12 写一算法, 求二叉树中每一结点的子孙个数.void count(Bnode *bt) /bt:二树的根, 在结

38、点结构中增加一个num域，计该结点的子孙个数 if (bt!=NULL ) count(bt-lchild); count(bt-rchild); if (bt-lchild!=NULL ) p1=bt-lchild.num+1; ELSE p1=0; if (bt-rchild!=NULL ) p2=bt-rchild.num+1; ELSE p2=0;bt.num=p1+p2 ; / 注意，只能用后序遍历方法实现6.13 以二叉链为存储结构, 写一个求二叉树深度的递归算法.一.借助队列实现int depth(Bnode *bt) initqueue(Q); enqueue(Q,（bt,1）

39、); while ( ! empty(Q) (f,h)=delqueue(Q); if (f-lchild!=NULL) p=f-lchild; enququq(Q,（p,h+1）); if (f-rchild!=NULL) p=f-rchild; enququq(Q,（p,h+1）); ; retuern(h);/depth_1二.用递归函数实现int depth(Bnode *bt) if (bt=NULL ) h=0;else h=max(depth(bt-lchild),depth(bt-rchild)+1 ;/左、右子树较大（深）值 + 1（根比子树深1层） return h;三.用

40、带变参的递归过程来实现void depth(Bnode *bt,int &h) if (bt=NULL ) h=0; else nodes(bt-lchild,hl); nodes(bt-rchild,hr); h=max(hl,hr)+1; 四.用非递归方法实现int depth(Bnode *bt) high=0;/计二叉树有高度（深度） level=0;/计某一结点所在的层次 t=bt; initstack(s); while (t!=NULL | ! empty(S) ) if (t!=NULL ) push(s,(t,+level); t=t-lchild; else (t,leve

41、l)=pop(s); if (levelhigh ) high=level; t=t-rchild; 6.14 以二叉链为存储结构, 写出逻辑表达式求值的算法.void eval(Bnode *bt)/!V分别表示非或与 if (bt!=NULL ) eval(bt-lchild); eval(bt-rchild); if ( bt-data=!) bt-result=!bt-rchild-result; else if ( bt-data=v) bt-result=( bt-lchild-result | bt-rchild-result); else if ( bt-data=) bt-r

42、esult=( bt-lchild-result & bt-rchild-result); else bt-result=bt-data; 6.15已知一棵二叉树以二叉链作为存储结构,编写完成下列操作的算法: 对于树中每一个元素值为x的结点, 删去以它为根的子树, 并释放相应的空间.void del(Bnode *,x:datatp) if (bt!=NULL ) if (bt-data=x ) dis(bt); del(bt-lchild); del(bt-rchild) ; void dis(Bnode *bt) if (bt!=NULL ) dis(bt-lchild); dis(bt-

43、rchild); free(bt); / dis 6.16以二叉链作为存储结构, 写一个算法，输出二叉树前序遍历中前k个结点的值.void point(Bnode *bt，int k) / n:全程量，初值=0 if (bt!=NULL ) n+;if (ndata); print(bt-lchild); print(bt-rchild) ; 6.17 已知一棵二叉树以二叉链作为存储结构, 设计一个算法，按中序次序依次输出各结点的值及对应的序号。 void inorder(Bnode *bt) initstack(s); n=0;while ( (bt) | !empty(s) ) if (bt) push(s,bt); bt=bt-lchild ; else pop(s,bt); printf(bt-data,+n); bt=bt-rchild; 思考题：6.18 以二叉链为存储