数据结构试题库集及答案

导读:严蔚敏《数据结构习题集》解答,的mark域值决定做何种动作.6.39typedefstruct{严蔚敏《数据结构习题集》解答intdata;EBTNode*lchild;EBTNode*rchild;EBTNode*parent;enum{0,1,2}mark;第58页共124页}EBTNode,EBitree;//有mark域和双亲指针域的二叉树结点类型voidPostOrder_No

数据结构试题库集及答案

的mark 域值决定做何种动作.

6.39

typedef struct {

严蔚敏《数据结构习题集》解答

int data;

EBTNode *lchild;

EBTNode *rchild;

EBTNode *parent;

enum {0,1,2} mark;

第 58 页 共 124 页

} EBTNode,EBitree; //有mark 域和双亲指针域的二叉树结点类型 void PostOrder_Nonrecursive(EBitree T)//后序遍历二叉树的非递归算法,不用栈

{

p=T;

while(p)

switch(p->mark)

{

case 0:

p->mark=1;

if(p->lchild) p=p->lchild; //访问左子树

break;

case 1:

p->mark=2;

if(p->rchild) p=p->rchild; //访问右子树

break;

case 2:

visit(p);

p->mark=0; //恢复mark 值

p=p->parent; //返回双亲结点

}

}//PostOrder_Nonrecursive

分析:本题思路与上一题完全相同,只不过结点的mark 值是储存在结点中的,而不是暂存在堆 栈中,所以访问完毕后要将mark 域恢复为0,以备下一次遍历.

6.40

typedef struct {

int data;

PBTNode *lchild;

PBTNode *rchild;

PBTNode *parent;

} PBTNode,PBitree; //有双亲指针域的二叉树结点类型

void Inorder_Nonrecursive(PBitree T)//不设栈非递归遍历有双亲指针的二叉树

{

p=T;

while(p->lchild) p=p->lchild; //向左走到尽头

while(p)

{

visit(p);

{

严蔚敏《数据结构习题集》解答

p=p->rchild;

while(p->lchild) p=p->lchild; //后继就是在右子树中向左走到尽头

}

第 59 页 共 124 页

else if(p->parent->lchild==p) p=p->parent; //当自己是双亲的左孩子时后继就是双亲 else

{

p=p->parent;

while(p->parent&&p->parent->rchild==p) p=p->parent;

p=p->parent;

} //当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中的祖先 }//while

}//Inorder_Nonrecursive

6.41

int c,k; //这里把k 和计数器c 作为全局变量处理

void Get_PreSeq(Bitree T)//求先序序列为k 的结点的值

{

if(T)

{

c++; //每访问一个子树的根都会使前序序号计数器加1

if(c==k)

{

printf("Value is %d\n",T->data);

exit (1);

}

else

{

Get_PreSeq(T->lchild); //在左子树中查找

Get_PreSeq(T->rchild); //在右子树中查找

}

}//if

}//Get_PreSeq

main()

{

...

scanf("%d",&k);

c=0; //在主函数中调用前,要给计数器赋初值0

Get_PreSeq(T,k);

...

}//main

6.42

int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目

{

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

严蔚敏《数据结构习题集》解答

第 60 页 共 124 页

else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶 子数

}//LeafCount_BiTree

6.43

void Bitree_Revolute(Bitree T)//交换所有结点的左右子树

{

T->lchild<->T->rchild; //交换左右子树

if(T->lchild) Bitree_Revolute(T->lchild);

if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树

}//Bitree_Revolute

6.44

int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x 的结点为根的子树深度

{

if(T->data==x)

{

printf("%d\n",Get_Depth(T)); //找到了值为x 的结点,求其深度

exit 1;

}

else

{

if(T->lchild) Get_Sub_Depth(T->lchild,x);

if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找

}

}//Get_Sub_Depth

int Get_Depth(Bitree T)//求子树深度的递归算法

{

if(!T) return 0;

else

{

m=Get_Depth(T->lchild);

n=Get_Depth(T->rchild);

return (m>n?m:n)+1;

}

}//Get_Depth

6.45

void Del_Sub_x(Bitree T,int x)//删除所有以元素x 为根的子树

{

if(T->data==x) Del_Sub(T); //删除该子树

else

{

if(T->lchild) Del_Sub_x(T->lchild,x);

if(T->rchild) Del_Sub_x(T->rchild,x); //在左右子树中继续查找

}//else

}//Del_Sub_x

严蔚敏《数据结构习题集》解答

void Del_Sub(Bitree T)//删除子树T

{

if(T->lchild) Del_Sub(T->lchild);

if(T->rchild) Del_Sub(T->rchild);

free(T);

}//Del_Sub

6.46

void Bitree_Copy_Nonrecursive(Bitree T,Bitree &U)//非递归复制二叉树 {

InitStack(S1);InitStack(S2);

push(S1,T); //根指针进栈

U=(BTNode*)malloc(sizeof(BTNode));

U->data=T->data;

q=U;push(S2,U);

while(!StackEmpty(S))

{

while(Gettop(S1,p)&&p)

{

q->lchild=(BTNode*)malloc(sizeof(BTNode));

q=q->lchild;q->data=p->data;

push(S1,p->lchild);

push(S2,q);

} //向左走到尽头

pop(S1,p);

pop(S2,q);

if(!StackEmpty(S1))

{

pop(S1,p);pop(S2,q);

q->rchild=(BTNode*)malloc(sizeof(BTNode));

q=q->rchild;q->data=p->data;

push(S1,p->rchild); //向右一步

push(S2,q);

}

}//while

}//BiTree_Copy_Nonrecursive

分析:本题的算法系从6.37 改写而来.

6.47

void LayerOrder(Bitree T)//层序遍历二叉树

{

InitQueue(Q); //建立工作队列

EnQueue(Q,T);

while(!QueueEmpty(Q))

{

DeQueue(Q,p);

第 61 页 共 124 页

严蔚敏《数据结构习题集》解答

五星文库wxphp.com包含总结汇报、办公文档、IT计算机、考试资料、文档下载、党团工作、资格考试、教程攻略、计划方案、教学研究以及数据结构试题库集及答案等内容。

本文共54页1<<36373839404142>>54