数据结构考研分类复习真题 第六章 答案 (五)[41]

[题目分析] 双链就利用二叉树结点的左右指针重新定义左指针为指向前驱的指针右指针是指向后继的指针链表在遍历中建立下面采用中序遍历二叉树

BiTree head=nullpre; //全局变量链表头指针headpre

void CreatLeafList(BiTree bt) //将BiTree 树中所有叶子结点链成带头结点的双链表

{if（bt） //若bt不空

{CreatLeafList（bt>lchild）; //中序遍历左子树

if(bt>lchild==null && bt>rchild==null) //叶子结点

if(head==null)//第一个叶子结点

{head=(BiTree)malloc(sizeof(BiNode)); //生成头结点

head>lchild=null; head>rchild=bt; //头结点的左链为空右链指向第一个叶子结点

bt>lchild=head; pre=bt; //第一个叶子结点左链指向头结点pre指向当前叶子结点

}

else //已不是第一个叶子结点

{pre>rchild=bt; bt>lchild=pre; pre=bt;} //当前叶子结点链入双链表

CreatLeafList(bt>rchild); //中序遍历右子树

pre>rchild=null; //最后一个叶子结点的右链置空（链表结束标记）

}//if(bt) }//结束CreatLeafList;

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []