熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第六章 答案 (四)[15]

2013-11-15 14:59:09  來源: 數據結構 

  .(

  ()設二叉樹的前序遍歷序列為PPPm中序遍歷序列為SSSm因為前序遍歷是根左右中序遍歷是左根右則前序遍歷序列中第一個結點是根結點(P到中序序列中查詢到Si=P根據中序遍歷時根結點將中序序列分成兩部分的原則

  若i=即S=P則這時的二叉樹沒有左子樹; 否則SSSi是左子樹的中序遍歷序列用該序列和前序序列PPPi去構造該二叉樹的左子樹

  若i=m即Sm=P則這時的二叉樹沒有右子樹; 否則Si+Si+Sm是右子樹的中序遍歷序列用該序列和前序序列中Pi+Pi+Pm去構造該二叉樹的右子樹算法描述請參見下面算法設計第

  ()若前序序列是abcd並非由這四個字母的任意組合(!=)都能構造出二叉樹因為以abcd為輸入序列通過棧只能得到/(n+)*n!/(n!*n!)=即以abcd為前序序列的二叉樹的數目是任取以abcd作為中序遍歷序列並不全能與前序的abcd序列構成二叉樹例如若取中序列dcab就不能

  該棵二叉樹的形態及中序序列略

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


From:http://tw.wingwit.com/Article/program/sjjg/201311/22656.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.