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

[题目分析]叶子结点只有在遍历中才能知道这里使用中序递归遍历设置前驱结点指针pre初始为空第一个叶子结点由指针head指向遍历到叶子结点时就将它前驱的rchild指针指向它最后叶子结点的rchild为空

LinkedList headpre=null; //全局变量

LinkedList InOrder(BiTree bt)

//中序遍历二叉树bt将叶子结点从左到右链成一个单链表表头指针为head

{if(bt){InOrder(bt>lchild); //中序遍历左子树

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

if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点

else{pre>rchild=bt; pre=bt; } //将叶子结点链入链表

InOrder(bt>rchild); //中序遍历左子树

pre>rchild=null; //设置链表尾

}

return(head); } //InOrder

时间复杂度为O(n)辅助变量使用head和pre栈空间复杂度O(n)

层次遍历参见上面算法第题中序遍历序列和后序序列可确定一棵二叉树详见上面应用题第题先序序列和后序序列无法确定一棵二叉树因为无法将二叉树分成左右子树如先序序列AB和后序序列BAA是根但B可以是左子女也可以是右子女

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