建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號「小明菜市場」，作者小明菜市場 。轉(zhuǎn)載本文請聯(lián)系小明菜市場公眾號。
創(chuàng)新互聯(lián)專業(yè)成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計，集網(wǎng)站策劃、網(wǎng)站設(shè)計、網(wǎng)站制作于一體，網(wǎng)站seo、網(wǎng)站優(yōu)化、網(wǎng)站營銷、軟文發(fā)稿等專業(yè)人才根據(jù)搜索規(guī)律編程設(shè)計，讓網(wǎng)站在運(yùn)行后，在搜索中有好的表現(xiàn)，專業(yè)設(shè)計制作為您帶來效益的網(wǎng)站！讓網(wǎng)站建設(shè)為您創(chuàng)造效益。
Hello ! 我是小小，今天總結(jié)一下什么是樹，以及關(guān)于樹的一些內(nèi)容。。
樹
樹是一種非常常用的數(shù)據(jù)結(jié)構(gòu)，與線性表，堆棧并駕齊驅(qū)。
樹的定義
樹是從自然界抽象出來的，它指的是N個父子節(jié)點(diǎn)的有限集合，對于這個有限集合，需要滿足如下條件：
- 當(dāng)N=0時，該節(jié)點(diǎn)集合為空，這棵樹也為空
- 在任意非空樹中，只能有一個根節(jié)點(diǎn)
- 當(dāng)N>1時，除去跟節(jié)點(diǎn)意外的其余節(jié)點(diǎn)本身也要集合成為一顆樹。即，樹具有遞歸特性，一棵樹是由若干子樹組成，每顆樹又是由若干顆更小的子樹組成，如圖所示
二叉樹
二叉樹指每個節(jié)點(diǎn)最多只能有兩個子樹的有序樹。通常左邊子樹稱之為左子樹，右邊樹稱之為右子樹。二叉樹最多只能有兩顆對稱的樹，二叉樹有左，右之分。樹和二叉樹的區(qū)別
1. 樹的節(jié)點(diǎn)的度數(shù)沒有限制，二叉樹限制為2，樹沒有限制。
2. 無序樹的節(jié)點(diǎn)沒有左右之分，二叉樹的節(jié)點(diǎn)有左右之分。
二叉搜索樹
二叉搜索樹，它是一顆空樹，具有以下性質(zhì)的二叉樹，稱之為二叉搜索樹
- 它的左子樹不為空，并且左子樹的所有節(jié)點(diǎn)值都要小于跟節(jié)點(diǎn)的值。
- 它的右子樹不為空，則右子樹的所有節(jié)點(diǎn)的值都要大于跟節(jié)點(diǎn)的值。
- 它的左右子樹分別為二叉排序樹。
平衡二叉樹
平衡二叉樹具有以下性質(zhì) 他是一顆控訴或者他的左右兩個子樹的高度差絕對值不超過1，并且左右兩個子樹都是一顆平衡二叉樹。平衡二叉樹實(shí)現(xiàn)有紅黑樹，AVL，伸展樹，最小二叉平衡樹的節(jié)點(diǎn)公示為：F(n)=F(n-1)+F(n-2)+1
B-樹
一顆m階B樹，是一顆平衡的m路搜索樹，或者是空樹，滿足以下性質(zhì)
- 1根節(jié)點(diǎn)至少有兩個子女
- 每個非跟節(jié)點(diǎn)包含k-1個元素和k個孩子，其中m/2 <= k <= m
- 所有的葉子結(jié)點(diǎn)都位于同一層。
- 每個節(jié)點(diǎn)中的元素從小到大排列，節(jié)點(diǎn)當(dāng)中k-1個元素正好是k個孩子包含的元素值域的劃分一般用于文件系統(tǒng)或者數(shù)據(jù)庫的索引
一般用于文件系統(tǒng)或者數(shù)據(jù)庫的索引
B+樹
B+樹具有以下特點(diǎn)
- 有k個子樹的中間節(jié)點(diǎn)包含k個元素，每個元素不保存數(shù)據(jù)，只用來保存索引，所有數(shù)據(jù)保存在葉子節(jié)點(diǎn)。
- 所有的葉子節(jié)點(diǎn)中包含了全部的元素信息，以及指向這些元素信息的執(zhí)政，并且葉子節(jié)點(diǎn)本身也是按照由大到小依次排列。
- 所有的中間節(jié)點(diǎn)元素都保存在葉子節(jié)點(diǎn)，在子元素中總是最大或者最小的元素。
紅黑樹
紅黑樹是平衡二叉樹的實(shí)現(xiàn)，具有以下特征
- 節(jié)點(diǎn)是紅色或者是黑色。
- 根節(jié)點(diǎn)時黑色。
- 每個葉子節(jié)點(diǎn)都是黑色節(jié)點(diǎn)的空節(jié)點(diǎn)
- 每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色，從每個葉子節(jié)點(diǎn)到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn)
- 從任意節(jié)點(diǎn)到每個葉子節(jié)點(diǎn)所有的路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
新聞標(biāo)題：樹|突然間，看了這篇文章，樹我懂了！
本文路徑：http://www.5511xx.com/article/cdpisdp.html
