}//Bitree_Revolute 6.44
int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 {
if(T->data==x)
{
printf(\找到了值为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); 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});
相关推荐：
loading