tft每日頭條

 > 科技

 > 數據結構和樹的相關概念

數據結構和樹的相關概念

科技 更新时间:2024-12-24 09:37:48

樹是數據結構中的一種,其屬于非線性數據結構結構的一種,我們前文所提到的數據結構多數都是線性的,這也是較為簡單的數據結構,而接下來的樹與圖均屬于非線性數據結構,也是概念極多的一類。

關鍵詞:節點, 結構, 數據結構, 術語, 子樹

1.什麼是樹

樹是數據結構中的一種,其屬于非線性數據結構結構的一種,我們前文所提到的數據結構多數都是線性的,這也是較為簡單的數據結構,而接下來的樹與圖均屬于非線性數據結構,也是概念極多的一類。

樹是由結點或頂點和邊組成的(可能是非線性的)且不存在着任何環的一種數據結構。沒有結點的樹稱為空(null或empty)樹。一棵非空的樹包括一個根結點,還(很可能)有多個附加結點,所有結點構成一個多級分層結構。

樹的定義:n個節點組成的有限集合。n=0,空樹;n>0,1個根節點,m個互不相交的有限集,每個子集為根的子樹。

如圖所示,圖為一棵樹:

數據結構和樹的相關概念(數據結構之樹的概念)1

2.樹的基本術語

l 節點的度:樹中某個節點的子樹的個數。

l 樹的度:樹中各節點的度的最大值。

l 分支節點:度不為零的節點。

l 葉子節點:度為零的節點。

l 路徑:i->j;路徑長度:路徑經過節點數目減1。

l 孩子節點:某節點的後繼節點;雙親節點:該節點為其孩子節點的雙親節點(父母節點);兄弟節點:同一雙親的孩子節點;子孫節點:某節點所有子樹中的節點;祖先節點:從樹節點到該節點的路徑上的節點。

l 節點的層次:根節點為第一層(以此類推);樹的高度:樹中節點的最大層次。

l 有序樹:樹中節點子樹按次序從左向右安排,次序不能改變;無序樹:與之相反

l 森林:互不相交的樹的集合。

3.樹的性質

l 樹的節點樹為所有節點度數加1(加根節點)。

l 度為m的樹中第i層最多有m^(i-1)個節點。

l 高度為h的m次樹至多(m^h-1)/(m-1)個節點。

l 具有n個節點的m次樹的最小高度為logm( n(m-1) 1 ) 向上取整。

,

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关科技资讯推荐

热门科技资讯推荐

网友关注

Copyright 2023-2024 - www.tftnews.com All Rights Reserved