题目:
利用结点的右孩子指针将一个二叉树的叶子结点从左向右链接成一个单链表。(head指向第一个,tail指向最后一个)
分析:
根据题意,可以分为第一个结点和剩余结点两种情况来处理,其中head一直指向第一个叶子结点,而tail递归过程中会指向所有剩余结点,最终停留在最后一个叶子结点上,要不然无法确定最后一个叶子结点的位置。
如图所示,head一直指向H结点,而tail会分别指向H,E,F,G结点,最后停留在G上。
算法思想:通过递归将所有叶子结点串成一个单链表。
代码:
void link(BTNode *p,BTNode *head,BTNode *tail){
if(p!=NULL){ // 如果不为空树
if(p->lchild==NULL && p->rchild==NULL){ // 找叶子结点的条件,即叶子结点的左右子树都为空
// 处理第一个叶子结点
if(head==NULL){ // 刚开始head还没有指向任何结点时
head=p; // head和tail都指向p
tail=p;
}
// 处理剩余的叶子结点
else{ // head不为空了,head不动,只移动tail
tail->rchild=p; // 和尾插法类似
tail=p;
}
// 先序遍历递归算法改的
link(p->lchild,head,tail); // 递归左子树
link(p->rchild,head,tail); // 递归右子树
}
}
}