3.【严题集6.17③】阅读下列算法,若有错,改正之 答:这是找结点后继的程序 BiTree In Succ( BiTree q)i 共有3处错误 ∥已知q是指向中序线索二叉树上某个结点的指针 注:当rtag=1时说明内装后继指针,可 ∥函数返回指向*q的后继的指针。 直接返回,第一句无错。 ∥应改为r=q 当rtag=0时说明内装右孩子指针,但孩 if(!r->rtag) 子未必是后继,需要计算。中序遍历应当 while(r-> etag)r=r> Achild;∥应改为 先左再根再右,所以应当找左子树直到叶 while(Ir->Ltag)r=r->Lchild return r;∥应改为 return r-> rchild 子处。r=r->lchl直到LTag=1 4.【严题集621②】画出和下列二叉树相应的森林 答:注意根右边的子树肯定是森林, 而孩子结点的右子树均为兄弟。 六、算法设计题(前5题中任选2题,第6题必做,每题8分,共24分) 1.【严题集6.42③】编写递归算法,计算二叉树中叶子结点的数目。 解:思路:输出叶子结点比较简单,用任何一种遍历递归算法,凡是左右指针均空者,则为叶子,将其打 印出来 法一:核心部分为: DLR( liuyu*root)*中序遍历递归函数 H if(root=NULL) i if((root->lchild=NULL)&&(root-rchild==NULL))(sum++; printf("%d\n", root->data): i DLR(root->lchild) DLR(root->rchild); i return(O) 法二: nt LeafCount BiTree( Bitree T∥求二叉树中叶子结点的数目 f(T) return0,∥空树没有叶子5 3.【严题集 6.17③】阅读下列算法，若有错，改正之。 4.【严题集 6.21②】画出和下列二叉树相应的森林。 答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。 六、算法设计题（前 5 题中任选 2 题，第 6 题必做，每题 8 分，共 24 分） 1.【严题集 6.42③】编写递归算法，计算二叉树中叶子结点的数目。 解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打 印出来。 法一：核心部分为： DLR(liuyu *root) /*中序遍历 递归函数*/ {if(root!=NULL) {if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",root->data);} DLR(root->lchild); DLR(root->rchild); } return(0); } 法二： int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 { if(!T) return 0; //空树没有叶子 BiTree InSucc(BiTree q){ //已知 q 是指向中序线索二叉树上某个结点的指针， //本函数返回指向*q 的后继的指针。 r=q->rchild; //应改为 r=q； if(!r->rtag) while(!r->rtag)r=r->rchild; // 应改为 while(!r->Ltag) r=r->Lchild; return r; //应改为 return r->rchild； }//ISucc 答：这是找结点后继的程序。 共有 3 处错误。 注：当 rtag＝1 时说明内装后继指针，可 直接返回，第一句无错。 当 rtag＝0 时说明内装右孩子指针，但孩 子未必是后继，需要计算。中序遍历应当 先左再根再右，所以应当找左子树直到叶 子处。r=r->lchild; 直到 LTag=1； 应改为：while(!r->Ltag)r=r->Lchild;