文章目錄
- 前言
- 樹的概念
- 樹的表示
- 樹結構在實際中的運用
- 二叉樹的概念
- 特殊的二叉樹
- 滿二叉樹
- 完全二叉樹
- 二叉樹性質
- 二叉樹的存盤結構
- 順序存盤
- 鏈式存盤
- 熟悉樹結構的習題練習
前言
陸陸續續的,我們已經學完了順序表,鏈表,堆疊和佇列等線性的資料結構,而今天博主要介紹的就是樹形的資料結構,和線性資料結構一樣,我們先介紹什么是樹形結構以及樹的特點
樹的概念
樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因
為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的
如下圖所示:
下面是介紹樹的一些常用術語概念,博主先上一張圖,方便大家區分各個術語
-
根結點:沒有雙親節點的結點,比如結點A.
-
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如B是A的孩子節點
-
雙親結點若一個節點含有子節點，則這個節點稱為其子節點的父節點,如A是B的父節點
-
節點的度:一個節點含有的子樹的個數稱為該節點的度； 如A的度為6
-
-
葉節點或終端節點度為0的節點稱為葉節點, 如B、C、H、I等節點為葉節點
-
非終端節點或分支節點度不為0的節點； 如D、E、F、G等節點為分支節點
-
兄弟節點具有相同雙親節點的節點互稱為兄弟節點； 如I,J是兄弟結點,K,L,M是兄弟結點,H,I不是兄弟結點
-
樹的度一棵樹中，最大的節點的度稱為樹的度； 如樹的度為6(因為A的度是所有結點中度最大的,結果為6)
-
節點的層次從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
-
樹的高度或深度樹中節點的最大層次； 如上面的樹的高度為4(即具有四層)
-
節點的祖先從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先
-
子孫以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫
樹的表示
前面簡單介紹了樹的概念,但是樹畢竟是邏輯結構,我們想要實作它,該怎么做呢?最常用的是借助鏈表,用
孩子兄弟表示法進行演繹樹結構.如下圖:
結點的代碼構建如下:
typedef int DataType;
typedef struct node
{
struct node* child; //指向左孩子結點
struct node* brother; //挨個指向兄弟結點
DataType data; //存盤當前結點資料
}node;
樹結構在實際中的運用
樹結構在實際生活中運用最多的就是檔案結構,如下示意圖:
二叉樹的概念
符合樹的概念,但特點是樹的度最大只能為2,也就是說每個結點的子節點最多只能有兩個.
二叉樹特點:
- 每個結點最多有兩棵子樹，即二叉樹不存在度大于2的結點，
- 二叉樹的子樹有左右之分，其子樹的次序不能顛倒，
特殊的二叉樹
滿二叉樹
**概念:**每一層的結點都達到最大值,且
第n層的結點數量符合公式2^(n-1),層數是從1開始數
完全二叉樹
概念: 對于層數(n>=2)的樹,其n-1層符合滿二叉樹,第n層結點數量必須從左向右都符合
222...1特性,即有且只有1個單結點,位置處于末尾,該單結點一定是左孩子結點.
二叉樹性質
-
若規定根節點的層數為1，則一棵非空二叉樹的第n層上最多有2^(n-1) 個結點.
-
若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是2^h- 1(該公式由等比數列求和得到).
-
若規定根節點的層數為1，具有n個結點的滿二叉樹的深度h=Log2(n+1)
-
任意一顆二叉樹,假設度為0的結點數量為n0,度為2的結點數量為n1,則滿足 n0= n1+1;
二叉樹的存盤結構
順序存盤
即用陣列進行存盤,在邏輯結構上是二叉樹,在物理結構上是一個陣列,用陣列的下標進行表示每個結點,從0開始,如下圖:
順序存盤的特點:
- 只適用二叉樹,因為二叉樹要求即使空結點也存盤,所以空間不會浪費,但是其他樹結構就會造成嚴重空間浪費
- 順序存盤二叉樹一般適用于堆排序
鏈式存盤
鏈式存盤有兩種:
- 二叉鏈:擁有三個域,分別是左右指標域和資料域,左右指標域分別指向左孩子和右孩子
- 三叉鏈:擁有四個域,分別是左右指標域以及雙親域和資料域,左右指標域同上,雙親域指向雙親節點.
示意圖如下:
二叉鏈結點構建代碼:
typedef int DataType;
typedef struct node
{
struct node* leftchild;
struct node* rightchild;
Datatype data;
};
三叉鏈結點構建代碼:
typedef int DataType;
typedef struct node
{
struct node* leftchild;
struct node* rightchild;
Datatype data;
};
熟悉樹結構的習題練習
1. 某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（ ）
A 不存在這樣的二叉樹
B 200
C 198
D 199
2.下列資料結構中，不適合采用順序存盤結構的是（ ）
A 非完全二叉樹
B 堆
C 佇列
D 堆疊
3.在具有 2n 個結點的完全二叉樹中，葉子結點個數為（ ）
A n
B n+1
C n-1
D n/2
4.一棵完全二叉樹的節點數位為531個，那么這棵樹的高度為（ ）
A 11
B 10
C 8
D 12
5.一個具有767個節點的完全二叉樹，其葉子節點個數為（）
A 383
B 384
C 385
D 386
答案:
- B,原因二叉樹中 葉子結點數量 = 度為2結點數量 + 1
- C,因為順序結構的優點是 尾刪尾插方便,但是佇列用的更多的是 頭插頭刪
- A,一顆滿二叉樹的結點數量是2n-1,現在所有結點是2n,相當于在滿二叉樹后增加了一個結點.所以為n
- B,2^9的結果是512,是一個滿二叉樹,531比512多19個結點,所以高度是10.
- B,前9層是滿二叉樹結點有512,剩余255葉節點,但是這255個結點有254個結點有雙親,即有127個度為2結點,然后前8層的結點都是度為2結點,2^8-1等于255,所以度為2的結點為255+127=382,那么剩下的結點為767-382=385(包含葉節點和一個度為1結點),所以答案是384
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296882.html
標籤：其他