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); visit(p);
if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }
}//LayerOrder 6.48
int found=FALSE;
Bitree* Find_Near_Ancient(Bitree T,Bitree p,Bitree q)//求二叉树T中结点p和q的最近共同祖先 {
Bitree pathp[ 100 ],pathq[ 100 ] //设立两个辅助数组暂存从根到p,q的路径 Findpath(T,p,pathp,0); found=FALSE;
Findpath(T,q,pathq,0); //求从根到p,q的路径放在pathp和pathq中
for(i=0;pathp[i]==pathq[i]&&pathp[i];i++); //查找两条路径上最后一个相同结点 return pathp[--i]; }//Find_Near_Ancient
void Findpath(Bitree T,Bitree p,Bitree path[ ],int i)//求从T到p路径的递归算法 {
if(T==p) {
found=TRUE; return; //找到 }
path[i]=T; //当前结点存入路径
if(T->lchild) Findpath(T->lchild,p,path,i+1); //在左子树中继续寻找
if(T->rchild&&!found) Findpath(T->rchild,p,path,i+1); //在右子树中继续寻找 if(!found) path[i]=NULL; //回溯 }//Findpath 6.49
int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 {
InitQueue(Q); flag=0;
EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) {
DeQueue(Q,p); if(!p) flag=1;
else if(flag) return 0; else {
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 }
}//while return 1;
}//IsFull_Bitree
分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针. 6.50
Status CreateBitree_Triplet(Bitree &T)//输入三元组建立二叉树 {
if(getchar()!='^') return ERROR; T=(BTNode*)malloc(sizeof(BTNode)); p=T;p->data=getchar(); getchar(); //滤去多余字符 InitQueue(Q); EnQueue(Q,T);
while((parent=getchar())!='^'&&(child=getchar())&&(side=getchar())) {
while(QueueHead(Q)!=parent&&!QueueEmpty(Q)) DeQueue(Q,e); if(QueueEmpty(Q)) return ERROR; //未按层序输入 p=QueueHead(Q);
q=(BTNode*)malloc(sizeof(BTNode)); if(side=='L') p->lchild=q;
else if(side=='R') p->rchild=q; else return ERROR; //格式不正确 q->data=child; EnQueue(Q,q); }
return OK;
}//CreateBitree_Triplet 6.51
Status Print_Expression(Bitree T)//按标准形式输出以二叉树存储的表达式 {
if(T->data是字母) printf(\ else if(T->data是操作符) {
if(!T->lchild||!T->rchild) return ERROR; //格式错误
if(T->lchild->data是操作符&&T->lchild->data优先级低于T->data) {
printf(\
if(!Print_Expression(T->lchild)) return ERROR;
printf(\
} //注意在什么情况下要加括号
else if(!Print_Expression(T->lchild)) return ERROR;
if(T->rchild->data是操作符&&T->rchild->data优先级低于T->data) {
printf(\
if(!Print_Expression(T->rchild)) return ERROR; printf(\ }
else if(!Print_Expression(T->rchild)) return ERROR; }
else return ERROR; //非法字符 return OK;
}//Print_Expression 6.52
typedef struct{
BTNode node; int layer;
} BTNRecord; //包含结点所在层次的记录类型
int FanMao(Bitree T)//求一棵二叉树的\繁茂度\{
int countd; //count数组存放每一层的结点数 InitQueue(Q); //Q的元素为BTNRecord类型 EnQueue(Q,{T,0});
while(!QueueEmpty(Q)) {
DeQueue(Q,r);
count[r.layer]++;
if(r.node->lchild) EnQueue(Q,{r.node->lchild,r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild,r.layer+1}); } //利用层序遍历来统计各层的结点数
h=r.layer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0],i=1;count[i];i++)
if(count[i]>maxn) maxn=count[i]; //求层最大结点数 return h*maxn; }//FanMao
分析:如果不允许使用辅助数组,就必须在遍历的同时求出层最大结点数,形式上会复杂一些,你能写出来吗? 6.53 int maxh;
Status Printpath_MaxdepthS1(Bitree T)//求深度等于树高度减一的最靠左的结点 {
Bitree pathd;
maxh=Get_Depth(T); //Get_Depth函数见6.44 if(maxh<2) return ERROR; //无符合条件结点 Find_h(T,1); return OK;
}//Printpath_MaxdepthS1
void Find_h(Bitree T,int h)//寻找深度为maxh-1的结点 {
path[h]=T; if(h==maxh-1) {
for(i=1;path[i];i++) printf(\ exit; //打印输出路径 } else {
if(T->lchild) Find_h(T->lchild,h+1); if(T->rchild) Find_h(T->rchild,h+1); }
path[h]=NULL; //回溯 }//Find_h 6.54
Status CreateBitree_SqList(Bitree &T,SqList sa)//根据顺序存储结构建立二叉链表 {
Bitree ptr[sa.last+1]; //该数组储存与sa中各结点对应的树指针 if(!sa.last) {
T=NULL; //空树 return; }
ptr[1]=(BTNode*)malloc(sizeof(BTNode)); ptr[1]->data=sa.elem[1]; //建立树根 T=ptr[1];
for(i=2;i<=sa.last;i++) {
if(!sa.elem[i]) return ERROR; //顺序错误 ptr[i]=(BTNode*)malloc(sizeof(BTNode)); ptr[i]->data=sa.elem[i]; j=i/2; //找到结点i的双亲j
if(i-j*2) ptr[j]->rchild=ptr[i]; //i是j的右孩子 else ptr[j]->lchild=ptr[i]; //i是j的左孩子 }
return OK;
}//CreateBitree_SqList 6.55
int DescNum(Bitree T)//求树结点T的子孙总数填入DescNum域中,并返回该数 {
if(!T) return -1;
else d=(DescNum(T->lchild)+DescNum(T->rchild)+2); //计算公式 T->DescNum=d; return d; }//DescNum
分析:该算法时间复杂度为O(n),n为树结点总数.注意:为了能用一个统一的公式计算子孙数目,所以当T为空指针时,要返回-1而不是0. 6.56
BTNode *PreOrder_Next(BTNode *p)//在先序后继线索二叉树中查找结点p的先序后继,并返回指针 {
if(p->lchild) return p->lchild; else return p->rchild; }//PreOrder_Next
分析:总觉得不会这么简单.是不是哪儿理解错了? 6.57
Bitree PostOrder_Next(Bitree p)//在后序后继线索二叉树中查找结点p的后序后继,并返回指针 {
if(p->rtag) return p->rchild; //p有后继线索 else if(!p->parent) return NULL; //p是根结点
else if(p==p->parent->rchild) return p->parent; //p是右孩子 else if(p==p->parent->lchild&&p->parent->tag) return p->parent; //p是左孩子且双亲没有右孩子 else //p是左孩子且双亲有右孩子 {
q=p->parent->rchild;
while(!q->ltag||!q->rtag) {
if(!q->ltag) q=q->lchild; else q=q->rchild;
} //从p的双亲的右孩子向下走到底 return q; }//else
}//PostOrder_Next 6.58
Status Insert_BiThrTree(BiThrTree &T,BiThrTree &p,BiThrTree &x)//在中序线索二叉树T的结点p下插入子树x {
if(!p->ltag&&!p->rtag) return INFEASIBLE; //无法插入 if(p->ltag) //x作为p的左子树 {
s=p->lchild; //s为p的前驱
p->ltag=Link; p->lchild=x; q=x;
while(q->lchild) q=q->lchild;
q->lchild=s; //找到子树中的最左结点,并修改其前驱指向s q=x;
while(q->rchild) q=q->rchild;
q->rchild=p; //找到子树中的最右结点,并修改其前驱指向p }
else //x作为p的右子树 {
s=p->rchild; //s为p的后继 p->rtag=Link; p->rchild=x; q=x;
while(q->rchild) q=q->rchild;
q->rchild=s; //找到子树中的最右结点,并修改其前驱指向s q=x;
while(q->lchild) q=q->lchild;
q->lchild=p; //找到子树中的最左结点,并修改其前驱指向p }
return OK;
}//Insert_BiThrTree 6.59
void Print_CSTree(CSTree T)//输出孩子兄弟链表表示的树T的各边 {
for(child=T->firstchild;child;child=child->nextsib) {
printf(\ Print_CSTree(child); }
}//Print_CSTree 6.60
int LeafCount_CSTree(CSTree T)//求孩子兄弟链表表示的树T的叶子数目 {
if(!T->firstchild) return 1; //叶子结点 else {
count=0;
for(child=T->firstchild;child;child=child->nextsib) count+=LeafCount_CSTree(child); return count; //各子树的叶子数之和 }
}//LeafCount_CSTree 6.61
int GetDegree_CSTree(CSTree T)//求孩子兄弟链表表示的树T的度 {
if(!T->firstchild) return 0; //空树 else {
degree=0;
for(p=T->firstchild;p;p=p->nextsib) degree++;//本结点的度 for(p=T->firstchild;p;p=p->nextsib) {
d=GetDegree_CSTree(p);
if(d>degree) degree=d; //孩子结点的度的最大值 }
return degree; }//else
}//GetDegree_CSTree 6.62
int GetDepth_CSTree(CSTree T)//求孩子兄弟链表表示的树T的深度 {
if(!T) return 0; //空树