目前最完整的数据结构1800题包括完整答案树和二叉树答案 下载本文

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

{Balance(bt->lchild); //后序遍历左子树 Balance(bt->rchild); //后序遍历右子树

hl=Height(bt->lchild); hr=Height(bt->rchild);//求左右子树的高度 bt->bf=hl-hr; //结点的平衡因子bf } }//算法结束

45.[题目分析]本题应采用层次遍历方式。若树不空,则二叉树根结点入队,然后当队列不空且队列长不超过n,重复如下操作:出队,若出队元素不为空,则记住其下标,且将其左右子女入队列;若出队元素为空,当作虚结点,也将其“虚子女”入队列。为节省空间,就用树T的顺序存储结构A[1..n]作队列,队头指针front,队尾指针rear,元素最大下标last.

void Traverse(BiTree bt ,int n)

// 求二叉树bt的顺序存储结构A[1..n],下标超过n报错,给出实际的最大下标 {BiTree A[], p; if(bt!=null)

{int front=0,rear=1,last=1; A[1]=bt; while(front<=rear)

{p=A[++front]; if(p) last=front; // 出队;用last记住最后一个结点的下标

rear=2*front;//计算结点(包括虚结点)“左子女”下标 if (p) //二叉树的实际结点

{if(rear>n) printf(“%c结点无左子女”); else A[rear]=p->lchild; if(rear+1>n) printf(“%c结点无右子女”); else A[rear+1]=p->rchild; }

else //p是虚结点

{ if(rear<=n) A[rear]=null; if(rear+1<=n) A[rear+1]=null; } }// while(front<=rear)

printf(“实际的最大下标是%d”,last); }//if(bt!=null) }//Traverse

46. [题目分析]两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树是否相似,采用递归算法。

int Similar(BiTree p,q) //判断二叉树p和q是否相似 {if(p==null && q==null) return (1);

else if(!p && q || p && !q) return (0); else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild))

}//结束Similar

47.[题目分析] 根据树的双亲表示法创建树的孩子兄弟链表表示法,首先给出根结点在双亲表示法中的下标,但找根结点的子女要遍历双亲表示法的整个静态链表,根结点的第一个子女是孩子兄弟表示法中的孩子,其它子女结点作兄弟。对双亲表示法中的任一结点,均递归建立其孩子兄弟链表子树。

CSTree PtreeToCstree (PTree pt,int root)

//本算法将双亲表示法的树pt转为孩子兄弟链表表示的树,root是根结点在双亲表示法中的下标。

{CSTree child , sibling; int firstchild;

CSTree cst=(CSTree)malloc(sizeof(CSNode)); //申请结点空间

31文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

cst->data=pt.nodes[root].data; cst->firstchild=null; cst->nextsibling=null;//根结点

firstchild=1;

for(i=1;i<=pt.n;i++) //查找root的孩子 if(pt.nodes[i].parent==root) {child=PtreetoCstree(pt,i); if(firstchild) {cst->firstchild=child; firstchild=0;sibling=cst->firstchild;}

else //child不是root的第一个孩子,作兄弟处理

{sibling->nextsibling=child; sibling=sibling->nextsibling;}

}//if }//end for

return cst; }//结束PtreetoCstree

48.[题目分析] 删除以元素值x为根的子树,只要能删除其左右子树,就可以释放值为x的根结点,因此宜采用后序遍历。删除值为x结点,意味着应将其父结点的左(右)子女指针置空,用层次遍历易于找到某结点的父结点。本题要求删除树中每一个元素值为 x的结点的子树,因此要遍历完整棵二叉树。

void DeleteXTree(BiTree bt) //删除以bt为根的子树 {DeleteXTree(bt->lchild); DeleteXTree(bt->rchild);//删除bt的左子树、右子树 free(bt); }// DeleteXTree //释放被删结点所占的存储空间

void Search(B:Tree bt,ElemType x)

//在二叉树上查找所有以x为元素值的结点,并删除以其为根的子树 {BiTree Q[];//Q是存放二叉树结点指针的队列,容量足够大 if(bt)

{if(bt->data==x) {DeleteXTree(bt); exit(0);}//若根结点的值为x,则删除整棵树

{QueueInit(Q); QueueIn(Q,bt); while(!QueueEmpty(Q))

{p=QueueOut(Q);

if(p->lchild) // 若左子女非空

if(p->lchild->data==x) //左子女结点值为 x,应删除当前结点的左子树

{DeleteXTree(p->lchild); p->lchild=null;} //父结点的左子女置空

else Enqueue (Q,p->lchild);// 左子女入队列 if(p->rchild) // 若右子女非空

if(p->rchild->data==x) //右子女结点值为 x,应删除当前结点的右子树

{DeleteXTree(p->rchild); p->rchild=null;} //父结点的右子女置空

else Enqueue (Q,p->rchild);// 右子女入队列

}//while

}//if(bt) }//search

49.[题目分析]在二叉树上建立三叉链表,若二叉树已用二叉链表表示,则可象48题那样,给每个结点加上指向双亲的指针(根结点的双亲指针为空)。至于删除元素值为x的结点以

32文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

及以x为根的子树,与48题完全一样,请参照48题。下面给出建立用三叉链表表示的二叉树的算法。二叉树按完全二叉树格式输入,对非完全二叉树,要补上“虚结点”。按完全二叉树双亲和子女存储下标间的关系,完成双亲和子女间指针的链接。‘#’是输入结束标志,‘$’是虚结点标志。 BiTree creat()/ /生成三叉链表的二叉树(题目给出PASCAL定义,下面的用类C书写) {BiTree p,Q[],root; //Q是二叉树结点指针的一维数组,容量足够大 char ch; int rear=0; //一维数组最后元素的下标 scanf(&ch);

while(ch!=‘#’) {p=null;

if(ch!=‘$’){p=(BiTree)malloc(sizeof(nodetp));

p->data=ch; p->lchild=p->rchild=null; }

Q[++rear]=p; //元素或虚结点

if(p){if(rear==1) {root=p;root->parent=null; } //根结点

else{Q[rear]->parent=Q[rear/2]; /双亲结点和子女结点用指针链上 if (rear%2==0) Q[rear/2]->lchild=Q[rear]; else Q[rear/2]->rchild=Q[rear];

}

scanf(“%c”,&ch); }//while

return(root); }//结束creat

50.int BTLC(BiTree T,int *c)//对二叉树T的结点计数

{if(T) {*c++;

BTLC(T->lchild,&c); //统计左子树结点 BTLC(T->rchild,&c); //统计右子树结点 } }//结束Count,调用时*c=0

51. int Count(CSTree t)//统计以孩子兄弟链表表示的树的叶子结点个数

{if(t==null) return(0);

else if(t->firstlchild==null) //左子女为空,结点必为叶子

return(1+Count(t->nextsibling)); //(叶子)+兄弟子树上的叶子结点 else return(Count(t->firstchild)+Count(t->nextsibling));//子女子树+兄弟子树

}//Count

52.void Count(BiTree bt,int *n0,*n) //统计二叉树bt上叶子结点数n0和非叶子结点数n

{if(bt)

{if (bt->lchild==null && bt->rchild==null) *n0++;//叶子结点 else *n++; //非叶结点 Count(bt->lchild,&n0,&n); Count(bt->rchild,&n0,&n); } }//结束 Count

53.int Count (BiTree bt) // 非递归遍历求二叉树上的叶子结点个数

{int num=0;

33文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

BiTree s[]; //s是栈,栈中元素是二叉树结点指针,栈容量足够大 whlie(bt!=null || top>0)

{while(bt!=null) {push(s,bt);bt=bt->lchild;} //沿左分支向下

if(!StackEmpty(s))

{bt=pop(s);if(bt->lchild==null && bt->rchild==null) num++;//叶子结点 bt=bt->rchild; }

} return(num);

}//结束Count

54.[题目分析]对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。 int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数 {if(bt==null || k<1) return(0);

BiTree p=bt,Q[]; //Q是队列,元素是二叉树结点指针,容量足够大 int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数

int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针,level 是二叉树的层数

while(front<=rear) {p=Q[++front];

if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点 if(p->lchild) Q[++rear]=p->lchild; //左子女入队 if(p->rchild) Q[++rear]=p->rchild; //右子女入队

if(front==last) {level++; //二叉树同层最右结点已处理,层数增1 last=rear; } //last移到指向下层最右一元素 if(level>k) return (leaf); //层数大于k 后退出运行 }//while }//结束LeafKLevel

55.[题目分析]按题目要求,每个结点的编号大于其左右孩子的编号,结点左孩子的编号小于右孩子的编号。由此看出,从小到大按“左右根”顺序,这正是后序遍序的顺序,故对二叉树进行后序遍历,在遍历中对结点进行编号,现将二叉树结点结构定义如下:

typedef struct node

{ElemType data; int num; struct node *lchild, *rchild; }Bnode,*Btree; void PostOrder(Btree t)

//对二叉树从1开始编号,结点编号大于其左右子女结点编号,结点的左子女编号小于其右子女编号

{typedef struct {Btree t; int tag; }node;

Btree p=t; node sn,s[]; //s为栈,容量足够大 int k=0,top=0; //k为结点编号,top为栈顶指针 while(p!=null || top>0)

{while(p) {sn.t=p; sn.tag=0; s[++top]=sn; p=p->lchild;} //沿左分枝向下 while(top>0 && s[top].tag==1){sn=s[top--];sn.t->num=++k;}//左右孩子已遍历,结点赋编号

if (top>0) {s[top].tag=1; p=s[top].t->rchild;} }//while(p!=null || top>0) }结束PostOrder

34文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

56. [题目分析]非递归算法参考上面第37题。下面给出递归算法。

void PreInCreat(BiTree root,ElemType pre[],in[],int l1,h1,l2,h2)

//根据二叉树前序序列pre和中序序列in建立二叉树。l1,h1,l2,h2是序列第一和最后元素下标。

{root=(BiTree)malloc(sizeof(BiNode)); //申请结点 root->data=pre[l1]; //pre[l1]是根

for(i=l2;i<=h2;i++) if(in[i]==pre[l1]) break; //在中序序列中,根结点将树分成左右子树

if(i==l2) root->lchild=null; //无左子树 else PreInCreat(root->lchild,pre,in,l1+1,l1+(i-l2),l2,i-1); //递归建立左子树

if(i==h2) root->rchild=null; //无右子树 else PreInCreat((root)->rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2) //递归建立右子树

}//结束PreInCreat

57(1)略 (2) 根据中序和后序序列,建立二叉树的递归算法见上面第30题,非递归算法见第38题。

58.[题目分析]采用后序非递归遍历二叉树,栈中保留从根结点到当前结点的路径上的所有

结点。

void PrintPath(BiTree bt,p) //打印从根结点bt到结点p之间路径上的所有结点 {BiTree q=bt,s[]; //s是元素为二叉树结点指针的栈,容量足够大

int top=0; tag[];//tag是数组,元素值为0或1,访问左、右子树的标志,tag和s同步

if (q==p) {printf(q->data); return;} //根结点就是所找结点 while(q!=null || top>0)

{while(q!=null) //左子女入栈,并置标记

if(q==p) //找到结点p,栈中元素均为结点p 的祖先 {printf(“从根结点到p结点的路径为\\n”);

for(i=1;i<=top;i++) printf(s[i]->data); printf(q->data); return; }

else {s[++top]=q; tag[top]=0; q=q—>lchild;} //沿左分支向下

while(top>0 && tag[top]==1)) top--;//本题不要求输出遍历序列,这里只退栈 if (top>0) {q=s[top]; q=q->rchild; tag[top]=1; } //沿右分支向下 }//while(q!=null || top>0) }//结束算法PrintPath

59.[题目分析]上题是打印从根结点到某结点p的路径上所有祖先结点,本题是打印由根结点到叶子结点的所有路径。只要在上题基础上把q是否等于p的判断改为q是否是叶子结点即可。其语句段如下:

if(q->lchild==null&&q->rchild==null) //q为叶子结点 {printf(“从根结点到p结点的路径为\\n”);

for(i=1;i<=top;i++) printf(s[i]->data);//输出从根到叶子路径上,叶子q的所有祖先

printf(q->data); }

60.[题目分析]因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶

35文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.