第6章习题答案(2)

第6章 树与二叉树

void CreateLeafList(BiTree t){ if(t){

CreateLeafList(t->lchild);//中序遍历左子树 if(t->lchild==NULL&&t->rchild==NULL)//叶子结点

if(head==NULL){//第一个叶子结点 }

else{pre->rchild=t;t->lchild=pre;pre=t;};

head=new BiTNode; //生成头结点

head->lchild=NULL; head->rchild=t;//头结点的左链为空，右链指向第一个叶子结点 t->lchild=head;pre=t;//第一个叶子结点左链指向头结点，pre指向当前叶子结点

CreateLeafList(t->rchild);

pre->rchild=NULL;

} }

18.假设二叉链表为二叉树的存储结构，编写算法，按照括号表示法输出二叉树的所有结点。 解：其过程是：对于非空二叉树t，先输出其元素值，当存在左孩子结点或右孩子结点时，输出一个“（”符号，然后递归处理左子树，输出一个“，”符号，递归处理右子树，最后输出一个“）”符号。

void DispBiTree(BiTree t){ if(t){ } }

19.假设二叉链表为二叉树的存储结构，编写算法，输出二叉树的所有叶子结点。 解：

void DispLeaf(BiTree t){ if(t){

if(t->lchild==NULL&&t->rchild==NULL)printf(\

6

printf(\

if(t->lchild!=NULL||t->rchild!=NULL){ }

printf(\

DispBiTree(t->lchild);

if(t->rchild!=NULL) printf(\DispBiTree(t->rchild); printf(\

第6章 树与二叉树

DispLeaf(t->lchild); DispLeaf(t->rchild); } }

20.假设二叉链表为二叉树的存储结构，编写算法，输出值为x的结点的所有祖先。 解：

int Ancestor(BiTree t,ElemType x){ if(t==NULL)return 0; if(t->data==x)return 1;

if(Ancestor(t->lchild,x)||Ancestor(t->rchild,x)){ } }

21.假设二叉链表为二叉树的存储结构，编写算法，输出所有叶子结点到根结点的路径。

解：利用后序非递归遍历的特点，将其中访问结点改为判断结点是否为叶子结点，若是，输出栈中所有结点值

void AllPathAncestor(BiTree t){ BiTNode *St[100]; BiTNode *p;

int flag,i,top=-1;//栈指针初始化 if(t){

printf(\return 1;

do{

while(t){ //t的所有左结点进栈 }

p=NULL; //p指向栈顶结点的前一个已访问的结点 flag=1; //设置t的访问标记为已访问过 while(top!=-1&&flag){

t=St[top]; //出栈 if(t->rchild==p){

if(t->lchild==NULL&&t->rchild==NULL){ //若为叶子结点

7

top++; St[top]=t; t=t->lchild;

第6章 树与二叉树

} }

22.编写算法，将二叉树的顺序存储结构转化为二叉链表存储结构。 解：typedef char ElemType; typedef struct {//结点结构 ElemType *data;//数据元素 int n;//左右孩子指针 }SqBTree;

BiTree Trans(SqBTree a,int i){//数据元素放在数组a的从下标为1开始的单元中 BiTree t;

if(i>a.n)return NULL;//当i大于a的结点个数 if(a.data[i]=='#')return NULL;//当i对于的结点为空 t=new BiTNode; t->data=a.data[i]; t->lchild=Trans(a,2*i); t->rchild=Trans(a,2*i+1); return t; }

23.写出在中序线索二叉树中找指定结点在后序下的前驱结点的算法。

解：在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若p左右子女均无，设其中序左线索指向其祖先结点f（p是f右子树中按中序遍历的第一个结点），

8

}

}

}

for(i=top;i>0;i--) printf(\输出栈中所有结点 printf(\

top--;

p=t;//p指向刚访问过的结点

else{ }

t=t->rchild; //t指向右孩子结点 flag=0; //设置未访问标记

}while(top!=-1); printf(\

第6章 树与二叉树

若f有左子女，则其右子女是p在后序下的前驱，若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，p在中序和后序下均无前驱。

BiThrTree InPostPre(BiThrTree t,BiThrTree p){ BiThrNode *q;

if(p->RTag==0)q=p->rchild;//若p有右子女，则右子女是其后序前驱

else if(p->LTag==0)q=p->lchild; //若p无右子女而有左子女，则左子女是其后序前驱 else if(p->lchild==NULL)q=NULL;//p是中序序列第一个结点，无后序前驱 else {//顺左线索向上找p的祖先，若存在，再找祖先的左子女 } return q; }

24.写出按后序序列遍历中序线索二叉树的算法。 解：

BiThrTree LeftMost(BiThrTree t){//求结点t的最左子孙的左线索 BiThrTree p=t;

while(p->LTag==0)p=p->lchild;

if(p->lchild!=NULL&&p->lchild!=t)return(p->lchild); else return NULL; }

BiThrTree RightMost(BiThrTree t){//求结点t的最右子孙的右线索 BiThrTree p=t;

while(p->RTag==0)p=p->rchild;

if(p->rchild!=NULL&&p->rchild!=t)return(p->rchild); else return NULL; }

int ISRightChild(BiThrTree t,BiThrTree &father){//若t是father的右孩子，返回1，否则返回0

father=LeftMost(t);

if(father&&father->rchild==t)return 1; else return 0;

9

while(p->LTag==1&&p->lchild!=NULL)p=p->lchild;

if(p->LTag==0)q=p->lchild; //p结点的祖先的左子女是其后序前驱 else q=NULL; //仅右单支树（p是叶子），已上到根结点，p结点无后序前驱

第6章 树与二叉树

}

void PostOrderInThr(BiThrTree t){//后序遍历中序线索二叉树t BiThrTree father,p=t->lchild; int flag; while(p!=t){ } }

25.已知中序线索二叉树T的右子树不空。设计算法，将s所指结点作为T的右子树的一个叶子结点插入进去，并使之成为T的右子树的(中序序列)第一个结点。

解：若使新插入的结点S成T右子树中序序列的第一个结点，则应在T的右子树中最左边的结点（设为p）处插入，使S成为结点p的左孩子。则S的前驱是T，后继是p。

void ThrTreeInsert(BiThrTree T, BiThrTree S){

BiThrTree p=T->rchild;//用p指向T的右子树中最左边的结点 while(p->LTag==0)p=p->lchild;

S->LTag=1;S->RTag=1;//S是叶子结点，其左右标记均为1

S->lchild=p->lchild; S->rchild=p;//S的前驱是根结点T，后继是结点p p->lchild=S; p->LTag=0;//将p的左指针指向S，并修改左标记为0 }

26.写出在中序线索二叉树中找指定结点在中序下的前驱结点的算法。 解：BiThrTree InorderPre(BiThrTree p){ BiThrTree q;

if(p->LTag==1)//结点的左子树为空，结点左指针域为左线索，指向其前驱

10

while(p->LTag==0)p=p->lchild;//沿左分子向下

if(p->RTag==0)flag=0;//左孩子为线索，右孩子为链，相当从左返回，p为叶子，相当从右返回 else flag=1; while(flag==1){

printf(\访问结点

if(ISRightChild(p,father)){p=father;flag=1;} //修改p指向双亲 else{//p是左孩子，用最右子孙的右线索找双亲 }

p=RightMost(p);

if(p&&p->RTag==1)flag=1;else flag=0;

}//while(flag==1)

if(flag==0&&p!=t)p=p->rchild;//转向当前结点的右分支

第6章 树与二叉树

return(p->lchild);

else{ q=p->lchild;//p结点左子树最右边结点时p结点的中序前驱 while(q->RTag)q=q->rchild;

return q;

}//if }

11

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第6章习题答案(2)在线全文阅读。