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

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

示法;根结点是父,根无右子女,左子女表示妻,妻的右子女(右子女的右子女等)均可看成兄弟(即父的所有儿子),兄弟结点又成为新的父,其左子女是兄弟(父的儿子)妻,妻的右子女(右子女的右子女等)又为儿子的儿子等等。首先递归查找某父亲结点,若查找成功,则其左子女是妻,妻的右子女及右子女的右子女等均为父亲的儿子。

BiTree Search(BiTree t,ElemType father)//在二叉树上查找值为father的结点 {if(t==null) return (null); //二叉树上无father结点 else if(t->data==father) return(t); //查找成功

p=Search(t->lchild,father); p=Search(t->rchild,father); } }//结束Search

void PrintSons(BiTree t,ElemType p) //在二叉树上查找结点值为p的所有的儿子 {p=Serach(t,p); //在二叉树t上查找父结点p if(p!=null) //存在父结点

{q=p->lchild; q=q->rchild; //先指向其妻结点,再找到第一个儿子 while(q!=null) {printf(q->data); q=q->rchild;} //输出父的所有儿子 }

}//结束PrintSons

18.[题目分析]后序遍历最后访问根结点,当访问到值为x的结点时,栈中所有元素均为该结点的祖先。

void Search(BiTree bt,ElemType x) //在二叉树bt中,查找值为x的结点,并打印其所有祖先

{typedef struct

{BiTree t; int tag; }stack;//tag=0表示左子女被访问,tag=1表示右子女被访问 stack s[]; //栈容量足够大 top=0;

while(bt!=null||top>0)

{while(bt!=null && bt->data!=x) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下

if(bt->data==x){ printf(“所查结点的所有祖先结点的值为:\\n”); //找到x

for(i=1;i<=top;i++) printf(s[i].t->data); return; } //输出祖先值后结束

while(top!=0 && s[top].tag==1) top--; //退栈(空遍历) if(top!=0) {s[top].tag=1;bt=s[top].t->rchild;} //沿右分枝向下遍历 }// while(bt!=null||top>0) }结束search

因为查找的过程就是后序遍历的过程,使用的栈的深度不超过树的深度,算法复杂度为O(logn)。

19.[题目分析] 先序遍历二叉树的非递归算法,要求进栈元素少,意味着空指针不进栈。 void PreOrder(Bitree bt)//对二叉数bt进行非递归遍历

{int top=0; Bitree s[]; //top是栈s的栈顶指针,栈中元素是树结点指针,栈容量足够大

while(bt!=null || top>0)

{while(bt!=null)

{printf(bt->data); //访问根结点

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

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

if(bt->rchlid) s[++top]=bt->rchild; //若有右子女,则右子女进栈 bt=bt->lchild; }

if (top>0) bt=s[top--]; }

本题中的二叉树中需进栈的元素有 C,H,K,F。

20.[题目分析]二叉树的顺序存储是按完全二叉树的顺序存储格式,双亲与子女结点下标间有确定关系。对顺序存储结构的二叉树进行遍历,与二叉链表类似。在顺序存储结构下,判二叉树为空时,用结点下标大于n(完全二叉树)或0(对一般二叉树的“虚结点”)。本题是完全二叉树。

void PreOrder(ElemType bt,int n)//对以顺序结构存储的完全二叉树bt进行前序遍历

{int top=0,s[]; //top是栈s的栈顶指针,栈容量足够大 while(i<=n||top>0) {while(i<=n)

{ printf(bt[i]); //访问根结点;

if (2*i+1<=n) s[++top]=2*i+1; //右子女的下标位置进栈 i=2*i; } //沿左子女向下 if(top>0) i=s[top--]; } //取出栈顶元素 }//结束PreOrder

21.[题目分析] 本题使用的存储结构是一种双亲表示法,对每个结点,直接给出其双亲(的下标),而且用正或负表示该结点是双亲的右子女或左子女。该类结构不适于直接进行前序遍历(即若直接前序遍历,算法要很复杂),较好的办法是将这类结构转为结点及其左右子女的顺序存储结构,即

Tree2=ARRAY[1..max] OF RECORD data: char; //结点数据

lc,rc: integer; END;//结点的左右子女在数组中的

下标

void Change (Tree t, Tree2 bt, int *root) //先将t转为如上定义类型的变量bt; {for(i=1;i<=max;i++) {bt[i].lc=bt[i].rc=0;} //先将结点的左右子女初始化为0 for(i=1;i<=max;i++) //填入结点数据,和结点左右子女的信息 {bt[i].data=t[i].data;

if(t[i].parent<0) bt[-t[i].parent].lc=i; //左子女 else if(t[i].parent>0) bt[t[i].parent].rc=i; //右子女 else *root=i; //root记住根结点 } }//change

void PreOrder(Tree2 bt) //对二叉树进行前序遍历 {int *root,top=0; int s[]; //s是栈 change(t,bt,root); int i=*root; while(i!=0||top>0) {while (i!=0)

{printf (bt[i].data);if(bt[i].rc!=0) s[++top]=bt[i].rc; //右子女进栈 i=bt[i].lc;

}

if (top>0) i=s[top--];

} }//结束preorder

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

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

[算法讨论]本题的前序递归算法如下

void PreOrder(int root)//root是二叉树根结点在顺序存储中的下标,本算法前序遍历二叉树bt

{if(root!=0){printf(bt[root].data);//访问根结点

PreOrder(bt[root].lc);//前序遍历左子树 PreOrder(bt[root].rc);//前序遍历右子树

} }//结束preorder,初始调用时,root是根结点的下标

这类问题的求解方法值得注意。当给定数据存储结构不合适时,可由已给结构来构造好的数据结构,以便于运算。象上面第5题也是这样,先根据L和R数组,构造一个结点的双亲的数组T。

22.[题目分析]二叉树先序序列的最后一个结点,若二叉树有右子树,则是右子树中最右下的叶子结点;若无右子树,仅有左子树,则是左子树最右下的叶子结点;若二叉树无左右子树,则返回根结点。

BiTree LastNode(BiTree bt)//返回二叉树bt先序序列的最后一个结点的指针 {BiTree p=bt;

if(bt==null) return(null); else while(p)

if (p->rchild) p=p->rchild; //若右子树不空,沿右子树向下

else if (p->lchild) p=p->lchild; //右子树空,左子树不空,沿左子树向下

else return(p); //p即为所求

}//结束lastnode

K

23.[题目分析]高度为K的二叉树,按顺序方式存储,要占用2–1个存储单元,与实际结点个数n关系不大,对不是完全二叉树的二叉树,要增加“虚结点”,使其在形态上成为完全二叉树。

K

int m=2–1; //全局变量

void PreOrder(ElemType bt[],i )

//递归遍历以顺序方式存储的二叉树bt, i是根结点下标(初始调用时为1)。 {if (i<=m) //设虚结点以0表示 {printf(bt[i]); //访问根结点

if(2*i<=m && bt[2*i]!=0) PreOrder(bt,2*i); //先序遍历左子树 if(2*i+1<=m && bt[2*i+1]!=0) PreOrder(bt,2*i+1);// 先序遍历右子树 } }//结束PreOrder

二叉树中最大序号的叶子结点,是在顺序存储方式下编号最大的结点

void Ancesstor(ElemType bt[]) //打印最大序号叶子结点的全部祖先

{c=m; while(bt[c]==0) c--; //找最大序号叶子结点,该结点存储时在最后 f=c/2; //c的双亲结点f

while(f!=0) //从结点c的双亲结点直到根结点,路径上所有结点均为祖先结点 {printf(bt[f]); f=f/2; }//逆序输出,最老的祖先最后输出 } //结束

24. void InOrder(BiTree bt)

{BiTree s[],p=bt; //s是元素为二叉树结点指针的栈,容量足够大

int top=0;

while(p || top>0)

{while(p) {s[++top]=p; bt=p->lchild;} //中序遍历左子树

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

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

if(top>0){p=s[top--]; printf(p->data); p=p->rchild;} //退栈,访问,转右子树

} }

25.[题目分析] 二叉树用顺序方式存储,其遍历方法与用二叉链表方式存储类似。判空时,在二叉链表方式下用结点指针是否等于null,在顺序存储方式下, 一是下标是否是“虚结

H

点”,二是下标值是否超过最大值(高为H的二叉树要有2-1个存储单元,与实际结点个数关系不大)。当然,顺序存储方式下,要告诉根结点的下标。

void InOrder(int i) //对顺序存储的二叉树进行中序遍历,i是根结点的下标 {if(i!=0)

{InOrder(ar[i].Lc); //中序遍历左子树 printf(ar[i].data); //访问根结点

InOrder(ar[i].Rc); //中序遍历左子树 } } // 结束InOrder 26.[题目分析] 借助队列和栈,最后弹出栈中元素实现对二叉树按自下至上,自右至左的层次遍历

void InvertLevel(biTree bt) // 对二叉树按自下至上,自右至左的进行层次遍历 {if(bt!=null)

{StackInit(s); //栈初始化,栈中存放二叉树结点的指针 QueueInit(Q); //队列初始化。队列中存放二叉树结点的指针 QueueIn(Q,bt);

while(!QueueEmpty(Q)) //从上而下层次遍历 {p=QueueOut(Q); push(s,p); //出队, 入栈

if(p->lchild) QueueIn(Q,p->lchild); //若左子女不空,则入队列 if(p->rchild) QueueIn(Q,p->rchild);} //若右子女不空,则入队列

while(!StackEmpty(s)) {p=pop(s); printf(p->data);} //自下而上,从右到左的层次遍历

}//if(bt!=null)

} //结束InvertLevel

27. int Level(BiTree bt) //层次遍历二叉树,并统计度为1的结点的个数

{int num=0; //num统计度为1的结点的个数

if(bt){QueueInit(Q); QueueIn(Q,bt);//Q是以二叉树结点指针为元素的队列

while(!QueueEmpty(Q))

{p=QueueOut(Q); printf(p->data); //出队,访问结点

if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++;//度为

1的结点

if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队 } }//if(bt)

return(num); }//返回度为1的结点的个数

28. void exchange(BiTree bt)//将二叉树bt所有结点的左右子树交换 {if(bt){BiTree s;

s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; //左右子女交换 exchange(bt->lchild); //交换左子树上所有结点的左右子树 exchange(bt->rchild); //交换右子树上所有结点的左右子树

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

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

} }

[算法讨论]将上述算法中两个递归调用语句放在前面,将交换语句放在最后,则是以后序遍历方式交换所有结点的左右子树。中序遍历不适合本题。下面是本题(1)要求的非递归算法

(1)void exchange(BiTree t) //交换二叉树中各结点的左右孩子的非递归算法

{int top=0; BiTree s[],p; //s是二叉树的结点指针的栈,容量足够大 if(bt)

{s[++top]=t; while(top>0)

{t=s[top--];

if(t->lchild||t->rchild){p=t->lchild;t->lchild=t->rchild;t->rchild=p;}

//交换左右

if(t->lchild) s[++top]=t->lchild; //左子女入栈 if(t->rchild) s[++top]=t->rchild; //右子女入栈 }//while(top>0)

}//if(bt) }// 结束exchange

29.[题目分析]对一般二叉树,仅根据一个先序、中序、后序遍历,不能确定另一个遍历序列。但对于满二叉树,任一结点的左右子树均含有数量相等的结点,根据此性质,可将任一遍历序列转为另一遍历序列(即任一遍历序列均可确定一棵二叉树)。

void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)

//将满二叉树的先序序列转为后序序列,l1,h1,l2,h2是序列初始和最后结点的下标。

{if(h1>=l1)

{post[h2]=pre[l1]; //根结点

half=(h1-l1)/2; //左或右子树的结点数

PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列

PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列

} }//PreToPost

30.BiTree IntoPost(ElemType in[],post[],int l1,h1,l2,h2)

//in和post是二叉树的中序序列和后序序列,l1,h1,l2,h2分别是两序列第一和最后结点的下标

{BiTree bt=(BiTree)malloc(sizeof(BiNode));//申请结点

bt->data=post[h2];//后序遍历序列最后一个元素是根结点数据

for(i=l1;i<=h1;i++) if(in[i]==post[h2])break;//在中序序列中查找根结点 if(i==l1) bt->lchild=null; //处理左子树

else bt->lchild=IntoPost(in,post,l1,i-1,l2,l2+i-l1-1); if(i==h1) bt->rchild=null; //处理右子树

else bt->rchild=IntoPost(in,post,i+1,h1,l2+i-l1,h2-1); return(bt); }

31.TYPE bitreptr=^binode;

binode=RECORD data:ElemType; lchild,rchlid:bitreptr END; PROC PreOrder(bt:bitreptr); //非递归前序遍列二叉树

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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4