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

樹 - 樹的概念(三)

2013-11-15 15:45:00  來源: 數據結構 

  樹結構的基本術語

  () 結點的度(Degree)

  樹中的一個結點擁有的子樹數稱為該 結點的度 (Degree)

  一棵 樹的度 是指該樹中結點的最大度數

  度為零的結點稱為 葉子 (Leaf)或 終端結點

  度不為零的結點稱 分支結點 或 非終端結點

  除根結點之外的分支結點統稱為 內部結點

  根結點又稱為 開始結點

  () 孩子(Child)和雙親(Parents)

  樹中某個結點的子樹之根稱為該結點的 孩子 (Child)或兒子相應地該結點稱為孩子的雙親(Parents)或父親

  同一個雙親的孩子稱為兄弟(Sibling)

  ()祖先(Ancestor)和子孫(Descendant)

  ①路徑(path)

  若樹中存在一個結點序列k k k i 使得k i 是k i+ 的 雙親 (≤i

  條 路徑 (Path)或 道路 。tw.WiNGWIt.COM

  路徑的長度 指路徑所經過的邊(即連接兩個結點的線段)的數目,等於j-1。

  注意:

  若一個結點序列是路徑,則在樹的樹形圖表示中,該結點序列"自上而下"地通過路徑上的每條邊。

  從樹的根結點到樹中其余結點均存在一條惟一的路徑。

  ②祖先(Ancestor)和子孫(Descendant)

  若樹中結點k到k s 存在一條路徑,則稱k是k s 的 祖先 (Ancestor),k s 是k的 子孫 (Descendant)。

  一個結點的祖先是從根結點到該結點路徑上所經過的所有結點,而一個結點的子孫則是以該結點為根的子樹中的所有結點。

  約定:

  結點k的祖先和子孫不包含結點k本身。

  (4)結點的層數(Level)和樹的高度(Height)

  結點的層數 (Level)從根起算:

  根的層數為1

  其余結點的層數等於其雙親結點的層數加1。

  雙親在同一層的結點互為 堂兄弟 。

  樹中結點的最大層數稱為 樹的高度 (Height)或 深度 (Depth)。

  注意,

  很多文獻中將樹根的層數定義為0。

  (5)有序樹(OrderedTree)和無序樹(UnoderedTree)

  若將樹中每個結點的各子樹看成是從左到右有次序的(即不能互換),則稱該樹為 有序樹 (OrderedTree);否則稱為 無序樹

  (UnoderedTree)。

  注意:

  若不特別指明,一般討論的樹都是有序樹。

  (6)森林(Forest)

  森林 (Forest)是m(m≥0)棵互不相交的樹的集合。

  樹和森林的概念相近。刪去一棵樹的根,就得到一個森林;反之,加上一個結點作樹根,森林就變為一棵樹。

  5.樹形結構的邏輯特征

  樹形結構的邏輯特征可用樹中結點之間的父子關系來描述:

  (1) 樹中任一結點都可以有零個或多個直接後繼(即孩子)結點,但至多只能有一個直接前趨(即雙親)結點。

  (2) 樹中只有根結點無前趨,它是開始結點;葉結點無後繼,它們是終端結點。

  (3) 祖先與子孫的關系是對父子關系的延拓,它定義了樹中結點之間的縱向次序。

  (4) 有序樹中,同一組兄弟結點從左到右有長幼之分。

  對這一關系加以延拓,規定若k 1 和k 2 是兄弟,且k 1 在k 2 的左邊,則k l 的任一子孫都在k 2 的任一子孫的左邊,那麼就定

  義了樹中結點之間的橫向次序。


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