一. ?? 前言
根據(jù)王道考研數(shù)據(jù)結(jié)構(gòu)總結(jié)出的知識點(diǎn)，以下是文章整體大綱：
二. ?? 各種樹的知識點(diǎn)
1. 樹
1.1 概念
樹是n個(gè)結(jié)點(diǎn)的有限集合，n = 0時(shí)稱為空樹，這是一種特殊情況。任意一棵非空樹中應(yīng)滿足：
- 有且僅有一個(gè)特定的稱為根的節(jié)點(diǎn)
- 當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m個(gè)互不相交的有限集合T1、T2、T3……Tm；每個(gè)集合又稱為根結(jié)點(diǎn)的子樹。
1.2 屬性
-
結(jié)點(diǎn)的深度：從上往下數(shù)；
-
結(jié)點(diǎn)的高度：從下往上數(shù)；
-
樹的高度：總共多少層
-
結(jié)點(diǎn)的度：有幾個(gè)孩子
-
樹的度：樹中結(jié)點(diǎn)的度的最大值
1.3 ?？夹再|(zhì)
- 結(jié)點(diǎn)數(shù) = 總度數(shù)+1
- 度為m的樹和m叉樹
度為m的樹是一定存在一個(gè)結(jié)點(diǎn)，它的度為m，且樹非空；m叉樹是指任意結(jié)點(diǎn)的度≤m，可以為空；
- 度為m的樹第i層至多有m的i-1次方個(gè)結(jié)點(diǎn)（i>=1）
- 高度為h的m叉樹至少有h個(gè)結(jié)點(diǎn)；高度為h，度為m的樹至少有h+m-1個(gè)結(jié)點(diǎn)。
1.4 樹轉(zhuǎn)換成二叉樹
樹轉(zhuǎn)換成二叉樹的畫法:
- 在兄弟結(jié)點(diǎn)之間加一條線；
- 對每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子的連線，抹去與其他孩子的連線；
- 以樹根為軸心，順時(shí)針旋轉(zhuǎn) 45°
1.5 森林轉(zhuǎn)換為二叉樹
森林轉(zhuǎn)換成二叉樹的畫法:
- 將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹
- 每棵樹的根也可視為兄弟結(jié)點(diǎn)，在每棵樹之間加一根連線
- 以第一棵樹的根為軸心順時(shí)針旋轉(zhuǎn) 45°
1.6 二叉樹轉(zhuǎn)換為森林
就是將森林轉(zhuǎn)換為二叉樹的逆做法
1.7 樹的遍歷
樹的遍歷: 用某種方式訪問樹中的每個(gè)結(jié)點(diǎn)，且僅訪問一次
先序遍歷：先根后子樹
后根遍歷：先子樹后根
先根遍歷序列為：ABEFCDG 對應(yīng)二叉樹中的先序遍歷
后根遍歷序列為：EFBCGDA 對應(yīng)二叉樹中的中序遍歷
1.8 森林的遍歷
先序遍歷：先根后子樹
中序遍歷：先子樹后根
先序遍歷序列為：ABCDEFGHI 對應(yīng)二叉樹的先序遍歷
中序遍歷序列為：BCDAFEHIG 對應(yīng)二叉樹的中序遍歷
2. 二叉樹
二叉樹是n個(gè)結(jié)點(diǎn)的有限集合；
2.1滿二叉樹
一棵高度為h，且含有2的h次方-1個(gè)結(jié)點(diǎn)的二叉樹；
特點(diǎn)：
- 只有最后一層有葉子結(jié)點(diǎn)；
- 不存在度為1的結(jié)點(diǎn)；
- 按層序從1開始編號，結(jié)點(diǎn)為i的左孩子結(jié)點(diǎn)為2i；右孩子為2i+1；結(jié)點(diǎn)i的父結(jié)點(diǎn)為i/2;
2.2 完全二叉樹
當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)都與高度為h的滿二叉樹中編號為1~n的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱為完全二叉樹；
特點(diǎn)：
- 只有最后兩層可能有葉子結(jié)點(diǎn)；
- 最多只有一個(gè)度為1的結(jié)點(diǎn)；
- i ≤ n/2為分支結(jié)點(diǎn)，i ＞ n/2為葉子結(jié)點(diǎn)；
- 如果一個(gè)完全二叉樹某結(jié)點(diǎn)只有一個(gè)孩子，則這個(gè)一定是左孩子；
2.3二叉排序樹
- 左子樹的所有結(jié)點(diǎn)均小于根結(jié)點(diǎn)；
- 右子樹的所有結(jié)點(diǎn)均大于根結(jié)點(diǎn)；
- 左子樹和右子樹又各是一棵二叉排序樹
2.4 平衡二叉樹
樹上任一結(jié)點(diǎn)的左子樹和右子樹的深度之差不超過1；
2.5 二叉樹?？夹再|(zhì)
- 設(shè)非空二叉樹中度為0、度為1、度為2的結(jié)點(diǎn)個(gè)數(shù)分別為n0、n1、n2，則n0 = n2 +1（葉子結(jié)點(diǎn)永遠(yuǎn)比二分支結(jié)點(diǎn)多一個(gè)）；
2.6 二叉樹存儲結(jié)構(gòu)
1. 順序存儲
使用數(shù)組實(shí)現(xiàn)順序存儲。一定要把二叉樹的結(jié)點(diǎn)編號與完全二叉樹對應(yīng)起來。
- i 的左孩子 — 2i+1
- i 的右孩子 — 2i+2
- i 的父節(jié)點(diǎn) — 『(i-1）/2』
2. 鏈?zhǔn)酱鎯?/h5>
struct ElemType{
int value;
}
typedef struct BiTNode{
ElemType data; //數(shù)據(jù)域
struct BiTNode *lchild; //左孩子指針
struct BiTNode *rchild; //右孩子指針
}BiTNode,*BiTree;
struct ElemType{
int value;
}
typedef struct BiTNode{
ElemType data; //數(shù)據(jù)域
struct BiTNode *lchild; //左孩子指針
struct BiTNode *rchild; //右孩子指針
}BiTNode,*BiTree;
假設(shè)二叉樹有n個(gè)結(jié)點(diǎn)，那么一定會有2n個(gè)指針，共有n+1個(gè)空鏈域；
二叉樹操作：
// 定義一棵空樹
BiTree root = null;
// 插入根節(jié)點(diǎn)
root = (BiTree) malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;
//插入新結(jié)點(diǎn)
BiTNode * p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p; //作為根節(jié)點(diǎn)的左孩子
2.7二叉樹的遍歷
1. 先序遍歷
先序遍歷(preOrder)的操作過程如下：
-
若二叉樹為空，則什么也不做
-
若二義樹非空:
- 訪問根結(jié)點(diǎn)
- 先序遍歷左子樹
- 先序遍歷右子樹
void preOrder(BiTree root){ if(root != null){ visit(root); //訪問根節(jié)點(diǎn)操作 preOrder(root->lchild); preOrder(root->rchild); } }void preOrder(BiTree root){ if(root != null){ visit(root); //訪問根節(jié)點(diǎn)操作 preOrder(root->lchild); preOrder(root->rchild); } }
如下： 每個(gè)結(jié)點(diǎn)都會被訪問三次。
2. 中序遍歷
中序遍歷(inOrder)的操作過程如下：
- 若二叉樹為空，則什么也不做
- 若二義樹非空:
- 中序遍歷左子樹
- 訪問根結(jié)點(diǎn)
- 中序遍歷右子樹
void inOrder(BiTree root){
if(root != null){
inOrder(root->lchild);
visit(root); //訪問根節(jié)點(diǎn)操作
inOrder(root->rchild);
}
}
3. 后序遍歷
后序遍歷(postOrder)的操作過程如下：
- 若二叉樹為空，則什么也不做
- 若二義樹非空:
- 后序遍歷左子樹
- 后序遍歷右子樹
- 訪問根節(jié)點(diǎn)
void postOrder(BiTree root){
if(root != null){
postOrder(root->lchild);
postOrder(root->rchild);
visit(root); //訪問根節(jié)點(diǎn)操作
}
}
應(yīng)用：求樹的深度
4. 層序遍歷
算法思想：
- 初始化一個(gè)輔助隊(duì)列
- 根結(jié)點(diǎn)入隊(duì)
- 若隊(duì)列非空，則隊(duì)頭結(jié)點(diǎn)p出隊(duì)，訪問p，并將其左右孩子插入隊(duì)尾(如果有的話)
- 重復(fù)步驟3，直到隊(duì)列為空。
// 層序遍歷
void levelOrder(BiTree root){
LinkQueue queue;
InitQueue(queue); //初始化隊(duì)列
BiTree p;
enQueue(root); //根節(jié)點(diǎn)入隊(duì)
while(!isEmpty(queue)){ //隊(duì)列不為空則循環(huán)
deQueue(queue,p); //隊(duì)頭結(jié)點(diǎn)出隊(duì)
visit(p);
if(p->lchild != NULL) enQueue(queue,p->lchild);
if(p->rchild != NULL) enQueue(queue,p->rchild);
}
}
隊(duì)列定義如下：
3. 線索二叉樹
4. 哈夫曼樹與哈夫曼編碼
權(quán): 樹中結(jié)點(diǎn)常被賦予一個(gè)代表某種意義的數(shù)值；
結(jié)點(diǎn)帶權(quán)路徑長度: 從樹的根到任意結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)上權(quán)值的乘積；
哈夫曼樹: 帶權(quán)路徑長度最小的二叉樹
4.1 哈夫曼樹的構(gòu)造
構(gòu)造哈夫曼樹的步驟：
- 將所有結(jié)點(diǎn)分別作為僅含一個(gè)結(jié)點(diǎn)的二叉樹；
- 構(gòu)造一個(gè)新結(jié)點(diǎn)，從中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新結(jié)點(diǎn)的左、右子樹，并且將新結(jié)點(diǎn)的權(quán)值置為左、右子樹上根結(jié)點(diǎn)的權(quán)值之和；（意思即 每次找出兩個(gè)權(quán)值最小的組成一棵二叉樹）
- 從中刪除剛才選出的兩棵樹，同時(shí)將新得到的樹加入森林中；
- 重復(fù)步驟(2) 和 (3)，直至剩下一棵樹為止
- 求哈夫曼編碼就是在哈夫曼樹的基礎(chǔ)上將左子樹的路徑變成0，右子樹的路徑變成1，如下：
a的哈夫曼編碼為：011
b的哈夫曼編碼為：10
c的哈夫曼編碼為：00
d的哈夫曼編碼為：010
e的哈夫曼編碼為：11
- ecabcbbe
- WPL = 5×2 + 2×3 + 4×3 + 7×2 + 9×2
5. 并查集
5.1 初始版本
public class unionFind{
// 初始化并查集
public void init(int[] nums){
Arrays.fill(nums,-1);
}
// 查操作：找x所屬集合，返回x所屬根節(jié)點(diǎn)
int find(int[] nums,int x){
while(s[x] >= 0){
x = s[x];
}
return x;
}
// 并操作：將兩個(gè)集合合并為一體
public void union(int[] nums,int rootX,int rootY){
if(rootX == rootY) return;
nums[rootY] = rootX;
}
}
5.2 優(yōu)化版本
public class unionFind{
// 初始化并查集
public void init(int[] nums){
Arrays.fill(nums,-1);
}
/**
* 并操作：使用根節(jié)點(diǎn)記錄樹的節(jié)點(diǎn)數(shù)目，讓小樹合并到大樹上
* 該方法構(gòu)造的樹高不超過log2n]+1
* @param s
* @param x
* @param y
*/
public void union(int[] nums,int x,int y){
int root1 = find(nums,x);
int root2 = find(nums,y);
if (root1 == root2) return;
if(s[root2]>s[root1]){ //root2節(jié)點(diǎn)更少（負(fù)數(shù)）
s[root1] += s[root2]; //將小樹的根節(jié)點(diǎn)數(shù)目加到大樹根節(jié)點(diǎn)上
s[root2] = root1; //小樹合并到大樹
}else{
s[root2] += s[root1];
s[root1] = root2;
}
}
/**
* 查操作：壓縮路徑
* @param s
* @param x
* @return
*/
int find1(int[] s,int x){
int root = x;
while(s[root] >= 0) root = s[root]; //循環(huán)找到根節(jié)點(diǎn)
while (x != root){ //壓縮路徑
int t = s[x]; //t指向x的父節(jié)點(diǎn)
s[x] = root; //x直接掛到根節(jié)點(diǎn)下
x = t;
}
return root;
}
}
本質(zhì)上表示集合的一種邏輯關(guān)系。
文章來源：http://www.zghlxwxcb.cn/news/detail-605892.html
三. ?? 總結(jié)
根據(jù)王道視頻課總結(jié)的數(shù)據(jù)結(jié)構(gòu)知識點(diǎn)，對于期末考、考研、面試的寶子有幫助哦?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-605892.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】| 王道考研——樹的前世今生的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
