二叉樹概述

各種實現和應用以后放鏈接

一、二叉樹的基本概念

二叉樹:二叉樹是每個節點最多有兩個子樹的樹結構。

根節點:一棵樹最上面的節點稱為根節點。

父節點子節點:如果一個節點下面連接多個節點,那么該節點稱為父節點,它下面的節點稱為子 節點。

葉子節點:沒有任何子節點的節點稱為葉子節點。

兄弟節點:具有相同父節點的節點互稱為兄弟節點。

節點度:節點擁有的子樹數。上圖中,13的度為2,46的度為1,28的度為0。

樹的深度:從根節點開始(其深度為0)自頂向下逐層累加的。上圖中,13的深度是1,30的深度是2,28的深度是3。

樹的高度:從葉子節點開始(其高度為0)自底向上逐層累加的。54的高度是2,根節點23的高度是3。

對于樹中相同深度的每個節點來說,它們的高度不一定相同,這取決于每個節點下面的葉子節點的深度。上圖中,13和54的深度都是1,但是13的高度是1,54的高度是2。

二、二叉樹的類型

類型定義圖示

滿二叉樹

Full Binary Tree

除最后一層無任何子節點外,每一層上的所有節點都有兩個子節點,最后一層都是葉子節點。滿足下列性質:

1)一顆樹深度為h,最大層數為k,深度與最大層數相同,k=h;

2)葉子節點數(最后一層)為2k?1;

3)第 i 層的節點數是:2i?1;

4)總節點數是:2k?1,且總節點數一定是奇數。

完全二叉樹

Complete Binary Tree

若設二叉樹的深度為h,除第 h 層外,其它各層 (1~h-1) 的結點數都達到最大個數,第 h 層所有的結點都連續集中在最左邊,這就是完全二叉樹。滿足下列性質:

1)只允許最后一層有空缺結點且空缺在右邊,即葉子節點只能在層次最大的兩層上出現;

2)對任一節點,如果其右子樹的深度為j,則其左子樹的深度必為j或j+1。 即度為1的點只有1個或0個;

3)除最后一層,第 i 層的節點數是:2i?1;

4)有n個節點的完全二叉樹,其深度為:log2n+1或為log2n+1;

5)滿二叉樹一定是完全二叉樹,完全二叉樹不一定是滿二叉樹。

平衡二叉樹

Balanced Binary Tree

又被稱為AVL樹,它是一顆空樹或左右兩個子樹的高度差的絕對值不超過 1,并且左右兩個子樹都是一棵平衡二叉樹。

二叉搜索樹

Binary Search Tree

又稱二叉查找樹、二叉排序樹(Binary Sort Tree)。它是一顆空樹或是滿足下列性質的二叉樹:

1)若左子樹不空,則左子樹上所有節點的值均小于或等于它的根節點的值;

2)若右子樹不空,則右子樹上所有節點的值均大于或等于它的根節點的值;

3)左、右子樹也分別為二叉排序樹。

紅黑樹

Red Black Tree

是每個節點都帶有顏色屬性(顏色為紅色或黑色)的自平衡二叉查找樹,滿足下列性質:

1)節點是紅色或黑色;

2)根節點是黑色;

3)所有葉子節點都是黑色;

4)每個紅色節點必須有兩個黑色的子節點。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。)

5)從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。

?

?

?

?

?

?

?

?

?

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/445599.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/445599.shtml
英文地址,請注明出處:http://en.pswp.cn/news/445599.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Java設計模式(1 / 23):策略模式

定義 策略(Strategy)模式定義了算法族,分別封裝起來,讓它們之間可以互相替換 ,此模式讓算法的變化獨立于使用算法的客戶。 案例:模擬鴨子應用 一開始 新需求:模擬程序需要會飛的鴨子 在父類新…

Java設計模式(3 / 23):裝飾者模式

文章目錄定義案例1:三點幾啦首次嘗試再次嘗試設計原則:類應該對擴展開放,對修改關閉嘗用裝飾者模式裝飾者模式特征本例的類圖放碼過來飲料類HouseBlendDarkRoastEspressoDecaf調料裝飾類MilkMochaSoyWhip運行測試類案例2:編寫自己…

c語言知識體系

原文:https://blog.csdn.net/lf_2016/article/details/80126296#comments

《游戲編程入門 4th》筆記(1 / 14):Windows初步

文章目錄Windows編程概述獲取Windows理解Windows消息機制多任務多線程事件處理DirectX快速概覽Direct3D是什么Window程序基礎創建第一個Win32項目理解WinMainWinMain函數調用完整的WinMainGetMessage函數調用尋求幫助Windows編程概述 DirectX,流行的游戲編程庫。它…

17校招真題題集(1)1-5

注:本系列題目全是按照通過率降序來排列的,基本保證題目難度遞增。 1、 題目名稱:游戲任務標記 來源:騰訊 題目描述 游戲里面有很多各式各樣的任務,其中有一種任務玩家只能做一次,這類任務一共有1024個…

《游戲編程入門 4th》筆記(2 / 14):監聽Windows消息

文章目錄編寫一個Windows程序理解InitInstanceInitInstance函數調用InitInstance的結構理解MyRegisterClassMyRegisterClass函數調用MyRegisterClass的作用揭露WinProc的秘密WinProc函數調用WinProc的大秘密什么是游戲循環The Old WinMain對持續性的需要實時終止器WinMain和循環…

17校招真題題集(2)6-10

注:本系列題目全是按照通過率降序來排列的,基本保證題目難度遞增。 6、 題目名稱:Fibonacci數列 來源:網易 題目描述 Fibonacci數列是這樣定義的: F[0] 0 F[1] 1 for each i ≥ 2: F[i] F[i-1] F[i-2] 因此&am…

QT5的數據庫

#include <QtSql> QT sql QSqlDatabase類實現了數據庫連接的操作 QSqlQuery類執行SQL語句 QSqlRecord類封裝數據庫所有記錄 QSqlDatabase類 [cpp] view plaincopy print?QSqlDatabase db QSqlDatabase::addDatabase("QOCI"); db.setHostName("localh…

數據結構課上筆記6

本節課介紹了單鏈表的操作實現細節&#xff0c;介紹了靜態鏈表。 鏈表帶頭的作用&#xff1a;對鏈表進行操作時&#xff0c;可以對空表、非空表的情況以及 對首元結點進行統一處理&#xff0c;編程更方便。 下面給出帶頭的單鏈表實現思路&#xff1a; 按下標查找&#xff1a; …

《Unity2018入門與實戰》筆記(9 / 9):個人總結

個人總結 腳本語言學習的竅門 盡可能多讀、多寫、多說腳本語言&#xff01; Link 游戲制作步驟 設計游戲時一般會遵循5個步驟&#xff1a; 羅列出畫面上所有的對象。確定游戲對象運行需要哪些控制器腳本。確定自動生成游戲對象需要哪些生成器腳本。準備好用于更新UI的調度…

17校招真題題集(3)11-15

注&#xff1a;本系列題目全是按照通過率降序來排列的&#xff0c;基本保證題目難度遞增。 11、 題目名稱&#xff1a;買蘋果 來源&#xff1a;網易 題目描述 小易去附近的商店買蘋果&#xff0c;奸詐的商販使用了捆綁交易&#xff0c;只提供6個每袋和8個每袋的包裝(包裝不…

Qt學習:QDomDocument

QDomDocument類代表了一個XML文件 QDomDocument類代表整個的XML文件。概念上講&#xff1a;它是文檔樹的根節點&#xff0c;并提供了文檔數據的基本訪問方法。由于元素、文本節點、注釋、指令執行等等不可能脫離一個文檔的上下文&#xff0c;所以文檔類也包含了需要用來創建這些…

《事實:用數據思考,避免情緒化決策》筆記

文章目錄一分為二負面思維直線思維恐懼本能規模錯覺以偏概全命中注定單一視角歸咎他人情急生亂一分為二 要做到實事求是&#xff0c; 就要做到當你聽到一分為二的說法時&#xff0c; 你就能迅速認識到這種說法描述的是一種兩極分化的圖畫&#xff0c; 而兩極之間存在一道巨大的…

順序存儲線性表實現

在計算機中用一組地址連續的存儲單元依次存儲線性表的各個數據元素,稱作線性表的順序存儲結構。 順序存儲結構的主要優點是節省存儲空間&#xff0c;因為分配給數據的存儲單元全用存放結點的數據&#xff08;不考慮c/c語言中數組需指定大小的情況&#xff09;&#xff0c;結點之…

QT5生成.exe文件時,出現缺少QT5core.dll文件解決方法

在 http://qt-project.org/downloads 下載Qt SDK安裝需要Qt版本。在QtCreator下&#xff0c;程序可以正常運行&#xff0c;但是當關閉QtCreator后&#xff0c;在DeBug目錄下再運行相應的*.exe程序時&#xff0c;會提示缺少Qt5Core.dll錯誤。解決方法&#xff1a;添加電腦環境變…

《基于Java實現的遺傳算法》筆記(7 / 7):個人總結

文章目錄為何采用遺傳算法哪些問題適合用遺傳算法解決遺傳算法基本術語一般遺傳算法的過程基本遺傳算法的偽代碼為何采用遺傳算法 遺傳算法是機器學習的子集。在實踐中&#xff0c;遺傳算法通常不是用來解決單一的、特定問題的最好算法。對任何一個問題&#xff0c;幾乎總有更…

單鏈表不帶頭標準c語言實現

鏈表是一種物理存儲單元上非連續、非順序的存儲結構&#xff0c;數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點&#xff08;鏈表中每一個元素稱為結點&#xff09;組成&#xff0c;結點可以在運行時動態生成。每個結點包括兩個部分&#xff1a;一個是…

Java設計模式(4 / 23):單例模式

文章目錄單例模式的應用場景餓漢式單例模式懶漢式單例模式改進&#xff1a;synchronized改進&#xff1a;雙重檢查鎖改進&#xff1a;靜態內部類破壞單例用反射破壞單例用序列化破壞單例解密注冊式單例模式枚舉式單例模式解密容器式單例線程單例實現ThreadLocal單例模式小結參考…

約瑟夫環-(數組、循環鏈表、數學)

約瑟夫環&#xff08;約瑟夫問題&#xff09;是一個數學的應用問題&#xff1a;已知n個人&#xff08;以編號1&#xff0c;2&#xff0c;3...n分別表示&#xff09;圍坐在一張圓桌周圍。從編號為k的人開始報數&#xff0c;數到m的那個人出列&#xff1b;他的下一個人又從1開始報…

Ubuntu麒麟下搭建FTP服務

一.怎么搭建FTP服務&#xff1a; 第一步>>更新庫 linuxidclinuxidc:~$ sudo apt-get update 第二步>>采用如下命令安裝VSFTPD的包 linuxidclinuxidc:~$ sudo apt-get install vsftpd 第三步>>安裝完成后打開 /etc/vsftpd.conf 文件&#xff0c;按如下所述…