数据结构答案(耿国华)

右之分?二叉树的孩子有左右孩子之分Р6Р2、对题6.1所得各种形态的二叉树,分别写出前序、中序和后序的遍历序列Р先:ABC?中:CBA?后:CBAР数据结构Р第6章树和二叉树习题РAРBРCРAРBРCРAРBРCРAРBРCРAРBРCР先:ABC?中:BCA?后:CBAР先:ABC?中:ACB?后:CBAР先:ABC?中:ABC?后:CBAР先:ABC?中:BAC?后:BCAР7Р数据结构Р第6章树和二叉树习题Р3.已知一棵度为k的树中有n1个度为1的结点,n2个度?为2的结点,…nk个度为k的结点,则该树中有多少个?叶子结点,并证明之。Р解:设n为总结点数,则有Р(总结点数) n=n0+n1+n2+…nkР(总边数) n-1=1*n1+2*n2+…k*nkР两式相减得:Р1=n0-n2-2n3-…-(k-1)nkРn0=1+n2+2n3+…+(k-1)nkР=1+∑(i-1)niРi=1РkР8Р数据结构Р第6章树和二叉树习题Р4.假设一棵二叉树的先序序列和中序序列,试画出该二叉树,并写出后序遍历序列。Р先序序列:E B A D C F H G I K JР中序序列:A B C D E F G H I J KРEРBРAРDРFРHРGРCРIРKРJР9Р6、给出满足下列条件的所有二叉树Р1)前序和中序相同?空树、只有一个结点的树、只有右枝的单枝树Р2)中序和后序相同?空树、只有一个结点的树、只有左枝的单枝树Р3)前序和后序相同?空树、只有一个结点的树Р数据结构Р第6章树和二叉树习题Р10Р补充:写出下面二叉树的前序、中序、后序遍历序列Р先序序列:? A B C D E F G H I JР中序序列:? B C D A F E H J I GР后序序列:? D C B F J I H G E AР数据结构Р第6章树和二叉树习题РAРBРDРCРFРEРGРHРIРJ