数据结构树与二叉树算法汇总

考研视频网考研视频网考研视频网考研视频网----阿里考研网阿里考研网阿里考研网阿里考研网 www.Alikaoyan.comwww.Alikaoyan.comwww.Alikaoyan.comwww.Alikaoyan.com荣誉出品荣誉出品荣誉出品荣誉出品 第1111页 共21212121页 树与二叉树算法汇总 1．以二叉树 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示算术表达式，根结点用于存储运算符。若能先分别求出左子树和右子树表示的子表达式的值，最后就可以根据 根结点的运算符的要求，计算出表达式的最后结果。 typedef struct node {ElemType data; float val; char optr; //只取‘+’， ‘-’， ‘*’，‘/’ struct node *lchild，*rchild }BiNode,*BiTree; float PostEval(BiTree bt) // 以后序遍历算法求以二叉树表示的算术表达式的值 {float lv,rv; if(bt!=null) {lv=PostEval(bt->lchild); // 求左子树表示的子表达式的值 rv=PostEval(bt->rchild); // 求右子树表示的子表达式的值 switch(bt->optr) { case ‘+’: value=lv+rv; break; case ‘-’: value=lv-rv;break; case ‘*’: value=lv*rv;break; case ‘/’: value=lv/rv; } } return(value); } 32.二叉树采取顺序结构存储，是按完全二叉树格式存储的。对非完全二叉树要补上“虚结点”。由于不是完全二叉树，在顺序结 构存储中对叶子结点的判定是根据其左右子女为 0。叶子和双亲结点下标间的关系满足完全二叉树的性质。 int Leaves(int h) //求深度为 h以顺序结构存储的二叉树的叶子结点数 { int BT[]; int len=2h-1, count=0; //BT 是二叉树结点值一维数组，容量为 2h for (i=1;i<=len;i++) //数组元素从下标 1开始存放 if (BT[i]!=0) //假定二叉树结点值是整数，“虚结点”用 0填充 if(i*2)>len) count++; //第 i 个结点没子女，肯定是叶子 else if(BT[2*i]==0 && 2*i+1<=len && BT[2*i+1]==0) count++; //无左右子女的结点是叶子 return (count) } //结束 Leaves ★★建立二叉树算法★★ 6．二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结 点无左子女就不应有右子女”的原则进行判断。 BiTree Creat() //建立二叉树的二叉链表形式的存储结构 {ElemType x；BiTree bt; scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0) {bt=(BiNode *)malloc(sizeof(BiNode)); bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } else error(“输入错误”)； return(bt); }//结束 BiTree int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回 1，否则，返回 0 {int tag=0; BiTree p=bt, Q[]; // Q 是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1); QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队 while (!QueueEmpty(Q)) { p=QueueOut(Q); //出队 if (p->lchild && !tag) QueueIn(Q,p->lchild); // tag==0 结点不空，左子入队 else {if (p->lchild) return 0; //tag==1 前边已有结点为空，本结点不空 else tag=1;} // p->lchild==null 首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); // tag=0 结点不空，右子女入队 else {if (p->rchild) return 0; else tag=1; } } //while return 1; //是完全二叉树 } //JudgeComplete 2 [算法讨论]完全二叉树证明还有其它 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必 是完全二叉树的错误结论。 7．BiTree Creat(ElemType A[],int i) //n 个结点的完全二叉树存于一维数组 A 中，本算法据此递归建立以二叉链表表示的完全二叉树 { BiTree tree; if (i<=n){tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i]; if(2*i>n) tree->lchild=null；else tree->lchild=Creat(A,2*i)； if(2*i+1>n) tree->rchild=null；else tree->rchild=Creat(A,2*i+1)； } return (tree)； }//Creat [算法讨论]初始调用时,i=1。 9.二叉树采用顺序存储结构（一维数组）是按完全二叉树的形状存储的，不是完全二叉树的二叉树顺序存储时，要加“虚结点”。 数组中的第一个元素是根结点。本题中采用队列结构。 typedef struct {BiTree bt; //二叉树结点指针 int num; }tnode // num 是结点在一维数组中的编号 tnode Q[maxsize]; //循环队列,容量足够大 void creat(BiTree T,ElemType BT[ ]) //深度 h的二叉树存于一维数组 BT[1:2h-1]中，本算法生成该二叉树的二叉链表存储结构 {tnode tq; //tq 是队列元素 int len=2h-1; //数组长度 T=(BiTree)malloc(sizeof(BiNode)); //申请结点 T->data=BT[1]; //根结点数据 tq.bt=T; tq.num=1; Q[1]=tq; //根入队列 front=0;rear=1; //循环队列头、尾指针 while(front!=rear) //当队列不空时循环 { front=(front+1) % maxsize ; tq=Q[front] ; p=tq.bt; i=tq.num ; //出队，取出结点及编号 if (BT[2*i]==‘#’||2*i>len) p->lchild=null; //左子树为空，‘#’表示虚结点 else //建立左子女结点并入队列 { p->lchild=(BiTree) malloc(sizeof(BiNode)); //申请结点空间 p->lchild�data=BT[2*i]; // 左子女数据 tq.bt=p->lchild; tq.num=2*i; rear=(rear+1) % maxsize ;//计算队尾位置 Q[rear]=tq; //左子女结点及其编号入队 } if(BT[2*i+1]==‘#’|| 2*i+1>len) p->rchild=null; //右子树为空 else //建立右子女结点并入队列 { p->rchild=(BiTree)malloc(sizeof (BiNode); //申请结点空间 p->rchild->data=BT[2*i+1]; tq.bt=p->rchild; tq.num=2*i+1; rear=(rear+1)%maxsize; Q[rear]=tq; //计算队尾位置,右子女及其编号入队 } } //while }//结束 creat [算法讨论] 本题中的虚结点用‘#’表示。应根据二叉树的结点数据的类型而定。 10．本题静态链表中结点是按动态二叉链表的前序遍历顺序存放的。首先对动态二叉链表的二叉树进行前序遍历，填写静态链表 的“下标”和 data 域，再对动态二叉链表的二叉树进行层次遍历，设队列 Q，填写静态链表的 lchild 域和 rchild 域。 typedef struct node //静态链表结点结构 { ElemType data; //结点数据 int row,lchild,rchild ; //下标，左右子女 }component； component st[]; //st 容量足够大 struct node {BiTree t; int idx; }qbt; static int num=0; ● void PreOrder(BiTree bt); // 前序遍历二叉树，填写静态链表的“下标”和 data 域 { if (bt) { st[++num].data=bt->data; st[num].row=num; PreOrder(bt->lchild); PreOrder(bt->rchild); 3 } } ● int Locate(ElemType x) //在静态链表中查二叉树结点的下标 { for (i=1;i<=num;i++) if (st[i].data==x) return (i); } ● void DynaToST (BiTree bt) //将二叉树的动态二叉链表结构转为静态链表结构 { int i=0; //i 为静态链表 st 的下标 if (bt!=null) { QueueInit(Q); //Q 是队列，容量足够大，队列元素是 qbt qbt.t=bt; qbt.idx=1; QueueIn(Q,qbt); st[1].data=bt->data; while(!QueueEmpty(Q)) { qbt=QueueOut(Q); //出队列 p=qbt.t; i=qbt.idx; //二叉树结点及在静态链表中的下标 if (p->lchild!=null) //若左子存在,查其在静态链表中的下标, 填 lchild 域值 { lch=Locate(p->lchild->data)； st[i].lchild=lch; //下标填入“静态链表” qbt.t=p->lchild; qbt.idx=lch; QueueIn(Q,qbt); } else st[i].lchild=0; //无左子，其 lchild 域填 0 if (p->rchild!=null) //若右子存在,查其在静态链表中的下标，填 rchild 域值 { rch=Locate(p->->rchild->data)； st[i].rchild=rch; qbt.t=p->rchild; qbt.idx=rch; QueueIn(Q,qbt); } else st[i].rchild=0; //无右子，其 lchild 域填 0 }//while }//结束 DynaToST 49.二叉树按完全二叉树格式输入，对非完全二叉树，要补上“虚结点”。按完全二叉树双亲和子女存储下标间的关系，完成双亲 和子女间指针的链接。‘#’是输入结束标志，‘$’是虚结点标志。 BiTree creat()/ /生成三叉链表的二叉树 { 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 ★★高度深度算法★★ 8.二叉树高度可递归计算如下：若二叉树为空，则高度为零，否则，二叉树的高度等于左右子树高度的大者加 1。这里二叉树为 空的标记不是 null 而是 0。设根结点层号为 1，则每个结点的层号等于其双亲层号加 1。 现将二叉树的存储结构定义如下: typedef struct node {int L[];//编号为 i 的结点的左儿子 int R[];//编号为 i 的结点的右儿子 int D[];//编号为 i 的结点的层号 int i; //存储结点的顺序号（下标） }tnode; （1）int Height(tnode t,int i)//求二叉树高度，调用时 i=1 {int lh,rh; if (i==0) return (0); else{ lh=Height(t,t.L[i]); 4 rh=Height(t,t.R[i]); if(lh>rh) return(lh+1); else return(rh+1); } }//结束 Height （2）int Level（tnode t）//求二叉树各结点的层号，已知编号为 1的结点是根，且层号为 1 { t.D[1]=1; for(i=1;i<=n;i++) { depth=t.D[i]； //取出根结点层号 if(t.L[i]!=0) t.D[t.L[i]]=depth+1; //i 结点左儿子层号 if(t.R[i]!=0) t.D[t.R[i]]=depth+1; } //i 结点右儿子层号 }结束 level int Height(btre bt)// 递归求二叉链表二叉树 bt 的深度 { int hl,hr; if (bt==null) return(0); else { hl=Height(bt->lch); hr=Height(bt->rch); if(hl>hr) return (hl+1); else return(hr+1); } } 14．由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一子女为空，高度为 1和兄弟子树的高度的大 者；否则，高度为第一子女树高度加 1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。 ● int Height(CSTree bt) //递归求以孩子兄弟链表表示的树的深度 { int hc,hs; if (bt==null) return (0); else if(!bt->firstchild) return ( 1+height(bt->nextsibling) );//子女空，查兄弟的深度 else // 结点既有第一子女又有兄弟，高度取子女高度+1和兄弟子树高度的大者 { hc=height(bt->firstchild)； //第一子女树高 hs=height(bt->nextsibling)；//兄弟树高 if(hc+1>hs) return(hc+1); else return (hs); } }//结束 height ● int height(CSTree t) //非递归遍历求以孩子兄弟链表表示的树的深度 { if(t==null) return(0); else{ int front=1,rear=1; //front,rear 是队头队尾元素的指针 int last=1,h=0; //last 指向树中同层结点中最后一个结点，h 是树的高度 Q[rear]=t; //Q 是以树中结点为元素的队列 while(front<=last) { t=Q[front++]; //队头出列 while(t!=null) //层次遍历 { if (t->firstchild) Q[++rear]=t->firstchild; //第一子女入队 t=t->nextsibling; //同层兄弟指针后移 } if(front>last) //本层结束，深度加 1（初始深度为 0） { h++; last=rear;} //last 再移到指向当前层最右一个结点 }//while(front<=last) }//else }//Height 11.由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树有深度。对 每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为 0为止。 int Depth(Ptree t) //求以双亲表示法为存储结构的树的深度 { int maxdepth=0; for(i=1;i<=t.n;i++) //n 为叶子结点个数 { temp=0; f=i; while(f>0) { temp++; f=t.nodes[f].parent; } // 深度加 1,并取新的双亲 if(temp>maxdepth) maxdepth=temp; //最大深度更新 } return(maxdepth);//返回树的深度 } //结束 Depth 13．求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。 5 int Width(BiTree bt)//求二叉树 bt 的最大宽度 { if (bt==null) return (0); //空二叉树宽度为 0 else { BiTree Q[];//Q 是队列，元素为二叉树结点指针，容量足够大 front=1; rear=1; last=1; //front 队头指针,rear 队尾指针,last 同层最右结点在队列中的位置 temp=0; maxw=0; //temp 记局部宽度, maxw 记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last) { p=Q[front++]; temp++; //同层元素数加 1 if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队 if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束， { last=rear; if(temp>maxw) maxw=temp; //last 指向下层最右元素, 更新当前最大宽度 temp=0; }//if }//while return (maxw); }//结束 width ★★后序遍历算法★★ 36.二叉树结点 p所对应子树的第一个后序遍历结点 q的求法如下：若p有左子树，则 q是 p的左子树上最左下的叶子结点；若p 无左子树，仅有右子树，则 q是 p的右子树上最左下的叶子结点。 BiTree PostFirst(p) { BiTree q=p; if (!q) return(null); else while(q->lchild || q->rchild); //找最左下的叶子结点 if(q->lchild) q=q->lchild; //优先沿左分枝向下去查“最左下”的叶子结点 else q=q->rchild; //沿右分枝去查“最左下”的叶子结点 return(q); } [算法讨论]题目“求 p所对应子树的第一个后序遍历结点”，蕴涵 p是子树的根。若 p是叶子结点，求其后继要通过双亲。 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)。 15.后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问 到某结点时，栈中所有元素均为该结点的祖先。本题要找 p 和 q 的最近共同祖先结点 r ,不失一般性，设 p在 q的左边。后序遍 历必然先遍历到结点 p，栈中元素均为 p 的祖先。将栈拷入另一辅助栈中。再继续遍历到结点 q 时，将栈中元素从栈顶开始逐个 到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点 p 和 q的最近公共祖先。 typedef struct { BiTree t; int tag; //tag=0 表示结点的左子女已被访问，tag=1 表示结点的右子女已被访问 }stack; stack s[],s1[];//栈，容量够大 BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点 p和 q 的最近的共同祖先结点 r。 { top=0; bt=ROOT; 6 while(bt!=null ||top>0) { while(bt!=null && bt!=p && bt!=q) //结点入栈 { s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下 if(bt==p) //不失一般性，假定 p在 q的左侧,遇结点 p时，栈中元素均为 p的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈 s 的元素转入辅助栈 s1 保存 if(bt==q) //找到 q 结点。 for(i=top;i>0;i--)//；将栈中元素的树结点到 s1 去匹配 { pp=s[i].t; for (j=top1;j>0;j--) if(s1[j].t==pp) {printf(“p 和 q的最近共同的祖先已找到”)；return (pp);} } 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) return(null);// q、p 无公共祖先 }//结束 Ancestor 16.二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系，求下标为 i 和 j 的两结 点的双亲，双亲的双亲，等等，直至找到最近的公共祖先。 void Ancestor(ElemType A[],int n,i,j) //二叉树顺序存储在数组 A[1..n]中，本算法求下标分别为 i 和 j的结点的最近公共祖先结点的值。 { while(i!=j) if(i>j) i=i/2; //下标为 i的结点的双亲结点的下标 else j=j/2; //下标为 j的结点的双亲结点的下标 printf(“所查结点的最近公共祖先的下标是%d，值是%d”,i,A[i]);//设元素类型整型。 }// Ancestor 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 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; 7 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 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.打印由根结点到叶子结点的所有路径。只要在 58基础上把 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.因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶 指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。 void LongestPath(BiTree bt) //求二叉树中的第一条最长路径长度 { BiTree p=bt,l[],s[]; //l, s 是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点 int i，top=0,tag[],longest=0; while(p || top>0) { while(p) { s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下 if(tag[top]==1) //当前结点的右分枝已遍历 { if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度 if(top>longest) { for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;} //保留当前最长路径到 l栈，记住最高栈顶指针，退栈 } else if(top>0) { tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0) }//结束 LongestPath ★★先序遍历算法★★ 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 19.先序遍历二叉树的非递归算法，要求进栈元素少，意味着空指针不进栈。 8 void PreOrder(Bitree bt)//对二叉数 bt 进行非递归先序遍历 { int top=0; Bitree s[]; //top 是栈 s的栈顶指针，栈中元素是树结点指针，栈容量足够大 while(bt!=null || top>0) { while(bt!=null) { printf(bt->data); //访问根结点 if(bt->rchlid) s[++top]=bt->rchild; //若有右子女，则右子女进栈 bt=bt->lchild; } if (top>0) bt=s[top--]; } } //本题中的二叉树中需进栈的元素有 C,H,K,F。 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 [算法讨论]本题的前序递归算法如下 ●void PreOrder(int root) //root 是二叉树根结点在顺序存储中的下标，本算法前序遍历二叉树 bt { if(root!=0) { printf(bt[root].data);//访问根结点 PreOrder(bt[root].lc);//前序遍历左子树 PreOrder(bt[root].rc);//前序遍历右子树 } }//结束 preorder，初始调用时，root 是根结点的下标 当给定数据存储结构不合适时，可由已给结构来构造好的数据结构，以便于运算。 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 23.高度为 K的二叉树，按顺序方式存储，要占用 2K –1个存储单元，与实际结点个数 n 关系不大，对不是完全二叉树的二叉树， 9 要增加“虚结点”，使其在形态上成为完全二叉树。 int m=2K –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; } //逆序输出，最老的祖先最后输出 } //结束 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); //交换右子树上所有结点的左右子树 } } [算法讨论]将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。 中序遍历不适合本题。下面是非递归算法 （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 ★★中序遍历算法★★ 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;} //中序遍历左子树 if(top>0) { p=s[top--]; printf(p->data); p=p->rchild;} //退栈，访问，转右子树 } } 25.二叉树用顺序方式存储，其遍历方法与用二叉链表方式存储类似。判空时，在二叉链表方式下用结点指针是否等于 null，在 顺序存储方式下， 一是下标是否是“虚结点”，二是下标值是否超过最大值（高为 H的二叉树要有 2H-1 个存储单元，与实际结点 个数关系不大）。顺序存储方式下，要告诉根结点的下标。 void InOrder(int i) //对顺序存储的二叉树进行中序递归遍历，i是根结点的下标 { if(i!=0) { InOrder(ar[i].Lc); //中序遍历左子树 printf(ar[i].data); //访问根结点 InOrder(ar[i].Rc); //中序遍历右子树 } } // 结束 InOrder 35.BiTree creat() //生成并中序输出二叉排序树 { scanf(“%c”,&ch); //ch 是二叉排序树结点值的类型变量，假定是字符变量 BiTree bst=null,f=null; while(ch!=‘#’) //‘#’是输入结束标记 10 { s=(BiTree)malloc(sizeof(BiNode)); //申请结点 s->data=ch; s->lchild=s->rchild=null; if (bst==null) bst=s; //根结点 else //查找插入结点 { p=bst; while(p) if (ch>p->data) { f=p; p=p->rchild;} //沿右分枝查,f 是双亲 else { f=p; p=p->lchild;} //沿左分枝查 if(f->datarchild=s; else f->lchild=s; //将 s 结点插入树中 } scanf(“%c”,&ch); //读入下一数据 } //while (ch!=‘#’) return(bst); } //结束 creat void InOrder(BiTree bst) //bst 是二叉排序树，中序遍历输出二叉排序树 { if(bst) { InOrder (bst->lchild); printf(bst->data); InOrder(bst->rchild); } }//结束 InOrder 41.叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针 pre，初始为空。第一个叶子结点由指针 head 指向，遍历到叶子结点时，就将它前驱的 rchild 指针指向它，最后叶子结点的 rchild 为空。 LinkedList head,pre=null; //全局变量 LinkedList InOrder(BiTree bt) //中序遍历二叉树 bt，将叶子结点从左到右链成一个单链表，表头指针为 head { if(bt) { InOrder(bt->lchild); //中序遍历左子树 if(bt->lchild==null && bt->rchild==null) //叶子结点 if(pre==null) { head=bt; pre=bt;} //处理第一个叶子结点 else{ pre->rchild=bt; pre=bt; } //将叶子结点链入链表 InOrder(bt->rchild); //中序遍历右子树 pre->rchild=null; //设置链表尾 } return(head); } //InOrder 时间复杂度为 O(n),辅助变量使用 head 和 pre,栈空间复杂度 O(n) ★★层次遍历算法★★ 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 借助队列和栈，最后弹出栈中元素实现对二叉树按自下至上，自右至左的层次遍历 33.计算每层中结点值大于 50 的结点个数，应按层次遍历。设一队列 Q，用 front 和 rear 分别指向队头和队尾元素，last 指向 各层最右结点的位置。存放值大于 50 的结点结构为 typedef struct {int level,value,idx; } node; //元素所在层号、值和本层中的序号 node a[],s; void ValueGT50(BiTree bt) //查各层中结点值大于 50 的结点个数，输出其值及序号 { if(bt!=null) { int front=0, last=1, rear=1, level=1, i=0, num=0; //num 记>50 的结点个数 BiTree Q[]; Q[1]=bt; //根结点入队 while(front<=last) { bt=Q[++front]; if(bt->data>50) { s.level=level; s.idx=++i; s.value=bt->data; a[++num]=s;} if(bt->lchild!=null) Q[++rear]=bt->lchild; //左子女入队列 if(bt->rchild!=null) Q[++rear]=bt->rchild; //右子女入队列 11 if(front==last) { last=rear; level++; i=0;} //本层最后一个结点已处理完 } //初始化下层：last 指向下层最右结点，层号加 1，下层>50 的序号初始为 0 for(i=1;i<=num;i++) //输出 data 域数值大于 50 的结点的层号、data 域的数值和序号 printf(“层号=%3d,本层序号=%3d，值=%3d”，a[i].level,a[i].idx,a[i].value); } }//算法 ValueGT50 结束 54.对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。 int L