一、樹的定義

樹是由n（n>=1）個有限節(jié)點組成一個具有層次關(guān)系的集合，它有如下特點：

1、每個節(jié)點有零個或多個子節(jié)點；

2、沒有父節(jié)點的節(jié)點稱為根節(jié)點；

3、每一個非根節(jié)點有且只有一個父節(jié)點；

4、除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹。

一棵樹至少包含一個樹節(jié)點，不存在不包含樹節(jié)點的樹。

樹中節(jié)點的最大層次稱為樹的深度（或高度）。

二、二叉樹的定義

二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。

二叉樹與樹不同之處：

1、樹的節(jié)點個數(shù)至少為1，而二叉樹的節(jié)點個數(shù)可以為0；

2、樹中節(jié)點的最大度數(shù)沒有限制，而二叉樹節(jié)點的最大度數(shù)為2；

3、樹的節(jié)點無左、右之分，而二叉樹的結(jié)點有左、右之分。

二叉樹的性質(zhì)：

1、在二叉樹的第i層最多有2^(i-1)個節(jié)點（i≥1）；

2、深度為h的二叉樹至多有2^h - 1個節(jié)點；

3、包括n（n>1）個元素的二叉樹的邊樹為n-1；

4、對于任何一顆二叉樹，若其葉子節(jié)點數(shù)記為n0，其度為2的節(jié)點數(shù)記為n2，則有n0 = n2+1。

5、若一顆滿二叉樹有n個節(jié)點，則其深度h應(yīng)為h = log2(n)+1，對數(shù)取下限。

6、一顆有n個節(jié)點的完全二叉樹，從左至右，從上至下，從1開始編號，對于編號為i的節(jié)點，有：

（1）若i=1，則i是根節(jié)點；若i≠1，則i/2是i的父親；

（2）若2i≤n，則i的左孩子是2i；若2i＞n，則i沒有孩子；

（3）若2i+2≤n，則i的右孩子是2i+1；若2i+1>n，則i沒有右孩子。

二叉樹的遍歷方式：前根（根左右）、中根（左根右）、后根（左右根）遍歷。

三、完全二叉樹的定義

對于一顆二叉樹，假設(shè)其深度為d（d>1）。除了第d層外，其它各層的節(jié)點數(shù)目均已達最大值，且第d層所有節(jié)點從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹。

在一棵二叉樹中，除最后一層外，其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干節(jié)點，則此二叉樹為完全二叉樹。

四、滿二叉樹的定義

一棵深度為k，且有2^k-1個節(jié)點的二叉樹，稱為滿二叉樹。

對于上述的完全二叉樹，如果去掉其第d層的所有節(jié)點，那么剩下的部分就構(gòu)成一個滿二叉樹（此時該滿二叉樹的深度為d-1）。

五、平衡二叉樹的定義

平衡二叉樹的定義如下：

1、它的左子樹和右子樹的高度之差的絕對值不超過1；

2、它的左子樹和右子樹都是平衡二叉樹。

六、二叉搜索樹的定義

二叉搜索樹的定義如下：

1、任意節(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；

2、任意節(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；

3、任意節(jié)點的左、右子樹也分別為二叉查找樹；

4、沒有鍵值相等的節(jié)點。

七、霍夫曼樹的定義

霍夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。霍夫曼樹的所有元素都在葉子節(jié)點上。

所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度（若根結(jié)點為0層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù)）。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的树、二叉树简介的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。