樹 - 樹的概念（一）

　　本章簡介

　　樹形結構是一類重要的非線性結構樹形結構是結點之間有分支並具有層次關系的結構它非常類似於自然界中的樹

　　樹結構在客觀世界中是大量存在的例如家譜行政組織機構都可用樹形象地表示

　　樹在計算機領域中也有著廣泛的應用例如在編譯程序中用樹來表示源程序的語法結構;在數據庫系統中可用樹來組織信息;

　　在分析算法的行為時可用樹來描述其執行過程

　　本章重點討論二叉樹的存儲表示及其各種運算並研究一般樹和森林與二叉樹的轉換關系最後介紹樹的應用實例

　　樹的概念

　　家族樹

　　在現實生活中有入如下血統關系的家族可用樹形圖表示

　　張源有三個孩子張明張亮和張麗;

　　張明有兩個孩子張林和張維;

　　張亮有三個孩子張平張華和張群;

　　張平有兩個孩子張晶和張磊

　　

　　以上表示很像一棵倒畫的樹其中樹根是張源樹的分支點是張明張亮和張平該家族的其余成員均是樹葉而樹枝(即圖

　　中的線段)則描述了家族成員之間的關系顯然以張源為根的樹是一個大家庭它可以分成張明張亮和張麗為根的三個小家庭;

　　每個小家庭又都是一個樹形結構

　　樹的定義

　　樹的遞歸定義

　　樹(Tree)是n(n≥)個結點的有限集TT為空時稱為空樹否則它滿足如下兩個條件

　　()有且僅有一個特定的稱為根(Root)的結點;

　　()其余的結點可分為m(m≥)個互不相交的子集T l T …T m 其中每個子集本身又是一棵樹並稱其為根的 子樹

　　(Subree)

　　注意

　　樹的遞歸定義刻畫了樹的固有特性一棵非空樹是由若干棵子樹構成的而子樹又可由若干棵更小的子樹構成

From:http://tw.wingwit.com/Article/program/sjjg/201311/23895.html