1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈
中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找
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;
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
2、(1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild) (5)ADDQ(Q,p->rchild)
25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild)
26. .(1)top++ (2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild
27. (1)*ppos // 根结点(2)rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1
3、本题要求建立有序的循环链表。从头到尾扫描数组A,取出A[i](0<=i 中去查找值为A[i]的结点,若查找失败,则插入。 LinkedList creat(ElemType A[],int n) //由含n个数据的数组A生成循环链表,要求链表有序并且无值重复结点 {LinkedList h; h=(LinkedList)malloc(sizeof(LNode));//申请结点 h->next=h; //形成空循环链表