堆和二叉樹的區別堆個二叉樹的區別

2021-03-06 22:51:47 字數 934 閱讀 5639

1樓:崎嶇的世界

在二叉排序樹中,每個結點的值均大於其左子樹

上所有結點的值,小於其右子樹上所有結點的值,對二叉排序樹進行中序遍歷得到一個有序序列。所以,二叉排序樹是結點之間滿足一定次序關係的二叉樹;

堆是一個完全二叉樹,並且每個結點的值都大於或等於其左右孩子結點的值(這裡的討論以大根堆為例),所以,堆是結點之間滿足一定次序關係的完全二叉樹。

具有n個結點的二叉排序樹,其深度取決於給定集合的初始排列順序,最好情況下其深度為log n(表示以2為底的對數),最壞情況下其深度為n;

具有n個結點的堆,其深度即為堆所對應的完全二叉樹的深度log n 。

在二叉排序樹中,某結點的右孩子結點的值一定大於該結點的左孩子結點的值;在堆中卻不一定,堆只是限定了某結點的值大於(或小於)其左右孩子結點的值,但沒有限定左右孩子結點之間的大小關係。

在二叉排序樹中,最小值結點是最左下結點,其左指標為空;最大值結點是最右下結點,其右指標為空。在大根堆中,最小值結點位於某個葉子結點,而最大值結點是大根堆的堆頂(即根結點)。

二叉排序樹是為了實現動態查詢而設計的資料結構,它是面向查詢操作的,在二叉排序樹中查詢一個結點的平均時間複雜度是o(log n);

堆是為了實現排序而設計的一種資料結構,它不是面向查詢操作的,因而在堆中查詢一個結點需要進行遍歷,其平均時間複雜度是o(n)。

2樓:

堆不一定是完全二叉樹 但是一般採用完全二叉樹,主要是利於儲存和運算

堆個二叉樹的區別

3樓:

在二叉排序樹中查詢一個結點的平均時間複雜度是o(log n),它不是面向查詢操作的,版因而在堆中查詢一個結點需權要進行遍歷,它是面向查詢操作的  二叉排序樹是為了實現動態查詢而設計的資料結構;

堆是為了實現排序而設計的一種資料結構,其平均時間複雜度是o(n)

什麼是二叉樹,舉二叉樹的例子,什麼是二叉樹,舉一個二叉樹的例子

二叉樹樹是一種重要的非線性資料結構,直觀地看,它是資料元素 在樹中稱為結點 按分支關係組織起來的結構,很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在,如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用,如在編譯源程式如下時,可用樹表示源源程式如下的語法結構。又如在資...

二叉樹的深度和高度有什麼區別求助二叉樹的高度和深度有什麼區別

一 概念不同 深度是從根節點數到它的葉節點,高度是從葉節點數到它的根節點。二叉樹的深度是指所有結點中最深的結點所在的層數。對於整棵樹來說,最深的葉結點的深度就是樹的深度 樹根的高度就是樹的高度。這樣樹的高度和深度是相等的。對於樹中相同深度的每個結點來說,它們的高度不一定相同,這取決於每個結點下面的葉...

二叉樹是重要的資料結構,點的不同的二叉樹有幾個

2個點有2種 根有左兒子或者根有右兒子 3個點有5種 左邊2個結點或者右邊2個結點或者左右各一結點,2 2 1 5 4個點有14種 左邊3個結點或者右邊3個結點或者左1右2或者左2右1 5 5 2 2 14 5個點有42種 左4或右4或左3右1或左1右3或左2右2,14 14 5 5 2 2 42 ...