28468.二叉樹的布局圖畫法及其性能研究

1、分類號：UDC：01密級：51華東理工大學(xué)學(xué)位論文二叉樹的布局圖畫法及其性能研究周陸樂指導(dǎo)教師姓名：劉朝暉教授華東理工大學(xué)申請學(xué)位級別：碩士專業(yè)名稱：數(shù)學(xué)一級學(xué)科論文定稿日期：2013—12—05論文答辯日期：2014—01—09學(xué)位授予單位：華東理工大學(xué)學(xué)位授予日期：答辯委員會主席：魯習(xí)文教授評閱人：單而芳教授蘇純潔副教授華東理工大學(xué)碩士學(xué)位論文第1頁二叉樹的布局圖畫法及其性能研究摘要本文主要研究二叉樹的布局圖畫法，分為三部分內(nèi)容。第

2、一部分簡單介紹了布局圖研究的背景知識、當(dāng)前的研究進(jìn)展以及研究的預(yù)備知識，包括圖的表示、美學(xué)標(biāo)準(zhǔn)、樹的定義、畫法及其效用分析等，并展示了本文的主要研究結(jié)果。第二部分給出了給定高度最小化寬度的二叉樹嚴(yán)格向上直線網(wǎng)格畫法問題的數(shù)學(xué)定義及其判定問題，并證明此問題是NP問題；給出此問題的枚舉法，并由枚舉法衍生出兩種啟發(fā)式算法一一貪婪算法及鄰域搜索算法；證明了枚舉法的時(shí)間復(fù)雜性為D(壘掣l。g：玎)，貪婪算法的時(shí)間復(fù)雜性為D(玎z辦)，鄰域搜索算法