第6章 树与二叉树
void CreateLeafList(BiTree t){ if(t){
CreateLeafList(t->lchild);//中序遍历左子树 if(t->lchild==NULL&&t->rchild==NULL)//叶子结点
if(head==NULL){//第一个叶子结点 }
else{pre->rchild=t;t->lchild=pre;pre=t;};
head=new BiTNode; //生成头结点
head->lchild=NULL; head->rchild=t;//头结点的左链为空，右链指向第一个叶子结点 t->lchild=head;pre=t;//第一个叶子结点左链指向头结点，pre指向当前叶子结点
CreateLeafList(t->rchild);
pre->rchild=NULL;
} }
18.假设二叉链表为二叉树的存储结构，编写算法，按照括号表示法输出二叉树的所有结点。 解：其过程是：对于非空二叉树t，先输出其元素值，当存在左孩子结点或右孩子结点时，输出一个“（”符号，然后递归处理左子树，输出一个“，”符号，递归处理右子树，最后输出一个“）”符号。
void DispBiTree(BiTree t){ if(t){ } }
19.假设二叉链表为二叉树的存储结构，编写算法，输出二叉树的所有叶子结点。 解：
void DispLeaf(BiTree t){ if(t){
if(t->lchild==NULL&&t->rchild==NULL)printf(\
6
printf(\
if(t->lchild!=NULL||t->rchild!=NULL){ }
printf(\
DispBiTree(t->lchild);
if(t->rchild!=NULL) printf(\DispBiTree(t->rchild); printf(\
第6章 树与二叉树
DispLeaf(t->lchild); DispLeaf(t->rchild); } }
20.假设二叉链表为二叉树的存储结构，编写算法，输出值为x的结点的所有祖先。 解：
int Ancestor(BiTree t,ElemType x){ if(t==NULL)return 0; if(t->data==x)return 1;
if(Ancestor(t->lchild,x)||Ancestor(t->rchild,x)){ } }
21.假设二叉链表为二叉树的存储结构，编写算法，输出所有叶子结点到根结点的路径。
解：利用后序非递归遍历的特点，将其中访问结点改为判断结点是否为叶子结点，若是，输出栈中所有结点值
void AllPathAncestor(BiTree t){ BiTNode *St[100]; BiTNode *p;
int flag,i,top=-1;//栈指针初始化 if(t){
printf(\return 1;
do{
while(t){ //t的所有左结点进栈 }
p=NULL; //p指向栈顶结点的前一个已访问的结点 flag=1; //设置t的访问标记为已访问过 while(top!=-1&&flag){
t=St[top]; //出栈 if(t->rchild==p){
if(t->lchild==NULL&&t->rchild==NULL){ //若为叶子结点
7
top++; St[top]=t; t=t->lchild;
第6章 树与二叉树
} }
22.编写算法，将二叉树的顺序存储结构转化为二叉链表存储结构。 解：typedef char ElemType; typedef struct {//结点结构 ElemType *data;//数据元素 int n;//左右孩子指针 }SqBTree;
BiTree Trans(SqBTree a,int i){//数据元素放在数组a的从下标为1开始的单元中 BiTree t;
if(i>a.n)return NULL;//当i大于a的结点个数 if(a.data[i]=='#')return NULL;//当i对于的结点为空 t=new BiTNode; t->data=a.data[i]; t->lchild=Trans(a,2*i); t->rchild=Trans(a,2*i+1); return t; }
23.写出在中序线索二叉树中找指定结点在后序下的前驱结点的算法。
解：在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若p左右子女均无，设其中序左线索指向其祖先结点f（p是f右子树中按中序遍历的第一个结点），
8
}
}
}
for(i=top;i>0;i--) printf(\输出栈中所有结点 printf(\
top--;
p=t;//p指向刚访问过的结点
else{ }
t=t->rchild; //t指向右孩子结点 flag=0; //设置未访问标记
}while(top!=-1); printf(\
第6章 树与二叉树
若f有左子女，则其右子女是p在后序下的前驱，若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，p在中序和后序下均无前驱。
BiThrTree InPostPre(BiThrTree t,BiThrTree p){ BiThrNode *q;
if(p->RTag==0)q=p->rchild;//若p有右子女，则右子女是其后序前驱
else if(p->LTag==0)q=p->lchild; //若p无右子女而有左子女，则左子女是其后序前驱 else if(p->lchild==NULL)q=NULL;//p是中序序列第一个结点，无后序前驱 else {//顺左线索向上找p的祖先，若存在，再找祖先的左子女 } return q; }
24.写出按后序序列遍历中序线索二叉树的算法。 解：
BiThrTree LeftMost(BiThrTree t){//求结点t的最左子孙的左线索 BiThrTree p=t;
while(p->LTag==0)p=p->lchild;
if(p->lchild!=NULL&&p->lchild!=t)return(p->lchild); else return NULL; }
BiThrTree RightMost(BiThrTree t){//求结点t的最右子孙的右线索 BiThrTree p=t;
while(p->RTag==0)p=p->rchild;
if(p->rchild!=NULL&&p->rchild!=t)return(p->rchild); else return NULL; }
int ISRightChild(BiThrTree t,BiThrTree &father){//若t是father的右孩子，返回1，否则返回0
father=LeftMost(t);
if(father&&father->rchild==t)return 1; else return 0;
9
while(p->LTag==1&&p->lchild!=NULL)p=p->lchild;
if(p->LTag==0)q=p->lchild; //p结点的祖先的左子女是其后序前驱 else q=NULL; //仅右单支树（p是叶子），已上到根结点，p结点无后序前驱
第6章 树与二叉树
}
void PostOrderInThr(BiThrTree t){//后序遍历中序线索二叉树t BiThrTree father,p=t->lchild; int flag; while(p!=t){ } }
25.已知中序线索二叉树T的右子树不空。设计算法，将s所指结点作为T的右子树的一个叶子结点插入进去，并使之成为T的右子树的(中序序列)第一个结点。
解：若使新插入的结点S成T右子树中序序列的第一个结点，则应在T的右子树中最左边的结点（设为p）处插入，使S成为结点p的左孩子。则S的前驱是T，后继是p。
void ThrTreeInsert(BiThrTree T, BiThrTree S){
BiThrTree p=T->rchild;//用p指向T的右子树中最左边的结点 while(p->LTag==0)p=p->lchild;
S->LTag=1;S->RTag=1;//S是叶子结点，其左右标记均为1
S->lchild=p->lchild; S->rchild=p;//S的前驱是根结点T，后继是结点p p->lchild=S; p->LTag=0;//将p的左指针指向S，并修改左标记为0 }
26.写出在中序线索二叉树中找指定结点在中序下的前驱结点的算法。 解：BiThrTree InorderPre(BiThrTree p){ BiThrTree q;
if(p->LTag==1)//结点的左子树为空，结点左指针域为左线索，指向其前驱
10
while(p->LTag==0)p=p->lchild;//沿左分子向下
if(p->RTag==0)flag=0;//左孩子为线索，右孩子为链，相当从左返回，p为叶子，相当从右返回 else flag=1; while(flag==1){
printf(\访问结点
if(ISRightChild(p,father)){p=father;flag=1;} //修改p指向双亲 else{//p是左孩子，用最右子孙的右线索找双亲 }
p=RightMost(p);
if(p&&p->RTag==1)flag=1;else flag=0;
}//while(flag==1)
if(flag==0&&p!=t)p=p->rchild;//转向当前结点的右分支
第6章 树与二叉树
return(p->lchild);
else{ q=p->lchild;//p结点左子树最右边结点时p结点的中序前驱 while(q->RTag)q=q->rchild;
return q;
}//if }
11