目錄
一、前言
二、樹的概念和定義
三、二叉樹
1.基本概念
2.基本形態
3.性質
4.滿二叉樹
5.完全二叉樹
四、存盤結構
1.順序存盤
2.二叉鏈表
3.三叉鏈表
五、總結比較
一、前言
- 學習目標：理解樹和二叉樹的基本概念與性質、存盤結構
- 重點：二叉樹的五個性質、存盤結構
二、樹的概念和定義
- 定義：n(n>=0)個結點的有限集合，n=0，空樹
- 結點：表示樹中的元素
- 根結點：第一個元素
- 葉結點：度為0，即沒有子樹
- 雙親結點：結點的直接前驅
- 孩子結點：結點的直接后繼
- 兄弟結點：同一雙親結點的孩子
- 結點的度：結點的子樹個數
- 結點的層次：根節點層次為1，依次向下加一
- 樹的度：樹中所有結點度的最大值
- 樹的高度：樹中所有結點層次的最大值
- 森林:m(m>=0)棵互不相交樹的集合
例題：
求出下圖的葉子結點、樹的度、高度、結點B、C、D的度、H的兄弟和雙親、E的孩子
- 葉子結點：K、L、F、G、M、I、J
- 樹的度和高度：3（最大結點的度數是D）、4
- 結點B、C、D的度：2、1、3
- H的兄弟和雙親、E的孩子：I、J D K、L
三、二叉樹
1.基本概念
- 定義：滿足每個結點度不大于2，孩子結點次序確定的樹
- 左孩子：位于左側
- 右孩子：位于右側
2.基本形態
- n個結點有
/（n+1）不同形態的二叉樹
3.性質
- 在二叉樹的第i層上最多有
個結點(i>=1)
- 深度為k的二叉樹最多有
-1個結點(k>=1)
- 對于任意一棵二叉樹，度為0的結點數等于度為2的結點數+1
結點為i雙親結點為i/2向下取整，左孩子2*i，右孩子2*i+1
4.滿二叉樹
特點：
- 每一層的結點數都是最大結點數
5.完全二叉樹
- 結點按照編號從左到右依次構建二叉樹，不存在無左孩子、卻有右孩子的情況
- 滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹
例題：
四、存盤結構
1.順序存盤
- 實作：按照結點的層次編號，依次放入陣列中，如上圖編號的123456789
- 特點：結點間關系蘊含在其存盤位置中、浪費空間，適于存滿二叉樹和完全二叉樹
2.二叉鏈表
- lchild:指向左孩子結點，沒有置為空
- rchild:指向右孩子結點，沒有置為空
- 特點：在n個結點的二叉鏈表中，有n+1個指標域
結構體：
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode,*BiTree;
例：
3.三叉鏈表
- 定義：三叉鏈表就是有三個指標域，lchild指向左孩子，rchild指向右孩子和二叉鏈表一樣，多出一個parent指向它的雙親結點
結構體：
typedef struct TriTNode
{ TElemType data;
struct TriTNode *lchild, *rchild, *parent;
} TriTNode,*TriTree;
例：
五、總結比較
| 線性結構 | 樹 |
| 第一個資料元素(無前驅) | 根結點(無前驅) |
| 最后一個資料元素(無后繼) | 多個葉子結點(無后繼) |
| 其它資料元素(一個前驅、一個后繼) | 樹中其它結點(一個前驅、多個后繼) |
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/400564.html
標籤：其他
上一篇：作業系統期末總復習——絕地求生版
下一篇：【C語言小游戲】計算器