有n個結點的二叉樹的深度至少是log(2)nl

2021-09-01 07:15:49 字數 3007 閱讀 6349

1樓:匿名使用者

不寫嚴格的符號證明了,自己手打,應該很好理解的。

首先,同樣n個結點,滿二叉樹肯定深度最小,這是顯然的因為滿二叉樹都是排滿一層以後再排下一層。

所以,這個“至少”的情況就是滿二叉樹的情況。

這樣就不難理解了,滿二叉樹第n層的結點數= 2的n-1次方。

也就是 第一層 1 , 下面 2, 4, 8, 16……深度為d的滿二叉樹,結點數就是 2的d次方-1講了這麼多,答案其實就顯然了。簡潔的概括,n個結點的二叉樹,深度最小的是滿二叉樹(或者說除最後一層外排滿的二叉樹)。

對於滿二叉樹,n個結點,假如n恰好等於 2的d次方-1(恰好排滿)[log(2)n]就等於d-1,深度等於d。

n如果=(2的d次方-1)+m (m>=1)深度等於d+1,此時[log(2)n]=d。

我寫的很痛苦…………害怕講不清楚。

其實二叉樹你只要動手畫畫,很多東西一看就出來了,比如如題的結論。否則

2樓:匿名使用者

二叉樹的第i層最多有2i-1個節點

若一個二叉樹的深度為 k,則次二叉樹最多有2k - 1個節點,

即n≤2k-1 k≥log2n+1

證明具有n個結點的二叉樹,其深度至少為[log2n]+1,求詳細證明?

3樓:綠鬱留場暑

證明:設所求完全二叉樹的深度為k,根據完全二叉樹的定義和性質2可知,k-1層滿二叉樹的結點個數為n時,有  2k-1-1即  2k-1≤n<2k;

對不等式取對數,有  k-1≤log2n由於k是整數,所以具有n個結點的二叉樹,其深度至少為[log2n]+1。

4樓:匿名使用者

深度為k的二叉樹的節點總數最多為1+2+4+..+2^(k-1)=2^k-1

則設n個節點的二叉樹深度為m,2^m-1>=nm>=log2(n+1)>log(2n),由於m是整數m>=[log2n]+1,

求解具有n個結點的完全二叉樹的深度,寫出計算過程

5樓:

具有n個結點的完全二叉樹的深度為「log2n」+1計算過程如下:

採用數學歸納法證明。

當n=1=2^1-1時,命題成立。

假設當n<=2^k-1時具有n個結點的完全二叉樹的深度為「log2n」+1,

則當n=2^k(以及2^k+1,...,2^(k+1)-1)時,由歸納假設知:

前2^k-1個結點構成深度為「log2n」+1的樹;

再由完全二叉樹的定義知:

剩餘的1(或2,...,2^k)個結點均填在第「log2n」+2層上(作為“葉子”),深度剛好增加了1,

故n<=2^(k+1)-1時,命題成立。

6樓:荔枝in時尚

具有n個結點的完全二叉樹的深度為「log2n」+1 !!!

二叉樹的計算方法:

若一棵二叉樹為空,則其深度為0,否則其深度等於左子樹和右子樹的最大深度加1,即有如下遞迴模型:

depth(b)=0 /*如果b=null*/

depth(b)=max(depth(b->left,b->right)+1 /*其它*/

因此求二叉樹深度的遞迴函式如下:

int depth(btree *b) }

二叉樹的基本性質

★樹的基本定義

1、樹是n(n>=0)個結點的有限集

2、樹的結點包含一個資料元素及若干指向其子樹的分支

3、結點擁有的子樹數稱為結點的度

4、度為0的結點稱為葉子或終端結點

5、樹的度是樹內各結點的度的最大值

6、結點的層次從根開始定義起,根為第一層,根的孩子為第二層

7、樹中結點的最大層次稱為樹的深度或高度

8、如果將樹中結點的各子樹看成從左至右是有次序的(即不能互換),則稱該樹為有序樹,否則稱為無序樹。在有序樹中,最左邊的子樹的根稱為第一個孩子,最右邊的稱為最後一個孩子。

★二叉樹的定義

二叉樹是一種樹型結構,它的特點是每個結點至多隻有二棵子樹(即二叉樹中不存在度大於2的結點),並且,二叉樹的子樹有左右之分,其次序不能任意顛倒。

★二叉樹的性質

性質一 在二叉樹的第i層上至多有2i-1個結點

性質二 深度為k的二叉樹至多有2k-1個結點(k>=1)

性質三 對任何一棵二叉樹t,如果其終端結點數為n0,度為2的結點數為n2,則n0=n2+1

性質四 具有n個結點的完全二叉樹的深度為「log2n」+1

性質五 如果對一棵有n個結點的完全二叉樹(其深度為「log2n」+1)的結點按層序編號(從第1層到第「log2n」+1層,每層從左到右),則對任一結點i(1≤i≤n),有

①如果i=1,則結點i是二叉樹的根,無雙親;如果i>1,則其雙親parent(i)是結點「i/2」

②如果2i>n,則結點n無左孩子(結點i為葉子結點);否則其左孩子lchild(i)是結點2i

③如果2i+1>n,則結點i無右孩子,否則其右孩子rchild(i)是結點2i+1

★先序遍歷二叉樹的操作定義

若二叉樹為空,則空操作,否則

(1)訪問根結點

(2)先序遍歷左子樹

(3)先序遍歷右子樹

★中序遍歷二叉樹的操作定義

若二叉樹為空,則空操作,否則

(1)中序遍歷左子樹

(2)訪問根結點

(3)中序遍歷右子樹

★後序遍歷二叉樹的操作定義

若二叉樹為空,則空操作,否則

(1)後序遍歷左子樹

(2)後序遍歷右子樹

(3)訪問根結點

7樓:匿名使用者

k層完全二叉樹,就是前(k-1)層為滿二叉樹,第k層均為葉結點,可以不滿。所以結點與深度的關係為:

2 ^ ( k - 1 ) - 1 < n <= 2 ^ k - 1。 所以k = [ ( n + 1 ) 以 2 為底取對數,然後向上取整 ]。

8樓:it達人

結論:⌊log2k⌋+1

設一棵完全二叉樹有結點,則該完全二叉樹的深度為,有葉子結點

256。二叉樹 binary tree 是指樹中節點的度不大於2的有序樹,它是一種最簡單且最重要的樹。二叉樹的遞迴定義為 二叉樹是一棵空樹,或者是一棵由一個根節點和兩棵互不相交的,分別稱作根的左子樹和右子樹組成的非空樹 左子樹和右子樹又同樣都是二叉樹 二叉樹 binary tree 是樹形結構的一個...

一棵二叉樹中,度為2的結點數為N,則葉子結點數是多少

總結點數 所有結點的度數加1,即2 n2 n1 n0 0 1,n0就是葉子結點數,又等於n2 n1 n0 由些可解出葉子結點數是n 1 n 1 2 自己畫幾個特例就懂了 若一棵二叉樹有11個葉子結點,則該二叉樹中度為2的結點個數是 二叉樹有如下性質 n0 n2 1,n0表示葉子結點,n2表示度為2的...

在深度為7的滿二叉樹中,葉子結點的個數為多少?(詳解)

滿二叉樹是指除最後一層外,每層上內的所有結點都有兩個子容結點 即在滿二叉樹中,每一層上的結點數都達到最大值,則在滿二叉樹的第k層上有2k 1個結點,月 深度為m的滿二叉樹有2m 1個結點。深度為7的滿二叉樹,其葉子結點數為27 1 26 64。如果根的層次為1,則深度為7的滿二叉樹,葉子都在第7層,...