數(shù)據(jù)結(jié)構(gòu)與算法筆記
備忘錄
二叉樹的非遞歸后序遍歷還沒有搞懂
二叉查找樹的刪除操作竟坛。
概述
數(shù)據(jù)結(jié)構(gòu)(Data Structure)
數(shù)據(jù)結(jié)構(gòu)可以表示為如下：
DataStructure = (D,L,S,O)
D(data):數(shù)據(jù)元素的有限集合，是存儲和操作的對象。
L(Logic Structure):邏輯結(jié)構(gòu)奖亚，是數(shù)據(jù)元素之間客觀存在的關(guān)系的有限集合。
S(Storage Structure):存儲結(jié)構(gòu)衰絮，是數(shù)據(jù)元素在計算機中的存儲表示练俐，也叫做物理結(jié)構(gòu)沸久。
O(Operation):在數(shù)據(jù)元素D上的一組操作的集合季眷。
邏輯結(jié)構(gòu)
基本的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)（元素不重復(fù)）、線性結(jié)構(gòu)（一對一）卷胯、樹形結(jié)構(gòu)（一對多）子刮、圖形結(jié)構(gòu)（多對多）。
存儲結(jié)構(gòu)
基本存儲結(jié)構(gòu)包括：順序存儲結(jié)構(gòu)（邏輯相鄰的元素物理也相鄰）窑睁，鏈式存儲結(jié)構(gòu)（邏輯相鄰的元素物理不一定相鄰）挺峡，散列存儲結(jié)構(gòu)（通過關(guān)鍵字直接計算出元素存儲位置）。
數(shù)據(jù)類型
數(shù)據(jù)類型是數(shù)據(jù)元素的類型卵慰，包括原子類型（基本數(shù)據(jù)類型如int沙郭，char等）和抽象數(shù)據(jù)類型（結(jié)構(gòu)體佛呻，類等）裳朋。
算法(Agorithms)
算法是求解特定問題的步驟的有限序列，可以表示為如下三元組：
Agorithms=(S,R,D)
S(Steps):是步驟的有限集合吓著。
D(Data):是求解問題所涉及的數(shù)據(jù)元素集合鲤嫡。
R(Relation):是步驟之間的關(guān)系集合，由一些流程控制結(jié)構(gòu)組成绑莺，順序結(jié)構(gòu)暖眼、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)纺裁、子過程和遞歸（調(diào)用已有算法）诫肠。
算法的特征
算法有五個特征：有輸入、有輸出欺缘、有窮性栋豫、確定性、可行性
數(shù)據(jù)結(jié)構(gòu)
線性表
線性表是具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的有限序列谚殊，表示一種邏輯結(jié)構(gòu)丧鸯。線性表除表頭和表尾元素外，每個元素都有唯一直接前驅(qū)和唯一直接后繼嫩絮。線性表的基本操作包括：
① 初始化
② 銷毀
③ 清空
④ 判空
⑤ 求長度
⑥ 按址查找
⑦ 按值查找
⑧ 插入操作
⑨ 刪除操作
⑩ 求前驅(qū)
? 求后繼
順序表
用順序存儲結(jié)構(gòu)存儲的線性表成為順序表丛肢，其元素可以隨機存取，所以也叫隨機存儲結(jié)構(gòu)剿干。各個操作的時間復(fù)雜度如下表：
|
操作
|
時間復(fù)雜度
|
備注
|
|
按址查找
|
O(1)
| |
|
按值查找
|
O(n)
| |
|
插入
|
O(n)
| |
|
刪除
|
O(n)
| |
|
其他
|
O(1)
| |
優(yōu)點：實現(xiàn)簡單蜂怎，可隨機存取
缺點：插入，刪除操作效率低置尔，預(yù)分配空間可能存在浪費杠步。
鏈表
鏈表是以鏈式存儲結(jié)構(gòu)存儲數(shù)據(jù)元素的線性表，插入和刪除元素不需要移動元素，時間復(fù)雜度為O(1)篮愉。
根據(jù)每個節(jié)點中指針數(shù)目的多少腐芍，分為單鏈表，雙向鏈表试躏，多重鏈表猪勇。
單鏈表每個節(jié)點有兩個域：數(shù)據(jù)域和一個后繼指針域。不常用颠蕴。
靜態(tài)鏈表：用數(shù)組表示的鏈表泣刹，每個數(shù)組項由data和next域，next存下一個節(jié)點的數(shù)組索引（下標）犀被，用于如java等沒有指針的語言實現(xiàn)鏈表椅您。
棧
棧和隊列是受限的線性表，棧限制了“先入后出（FILO）”寡键，隊列限制了“先入先出(FIFO)”掀泳。
隊列
數(shù)組
樹
二叉樹的基本概念
二叉樹：二叉樹是具有相同類型的數(shù)元素的集合，包含一個根和兩個子樹（左子樹和右子樹）西轩，且兩個子樹也是二叉樹员舵。
節(jié)點的度：節(jié)點擁有的子樹個數(shù)成為節(jié)點的度，二叉樹中藕畔，節(jié)點的度最大為2马僻。
孩子、雙親注服、子孫韭邓、祖先、兄弟溶弟、堂兄弟女淑。。可很。
層次：即第幾層诗力。
二叉樹的度：二叉樹中最大的節(jié)點的度。
二叉樹的深度：二叉樹中節(jié)點的最大層次數(shù)我抠。
滿二叉樹：所有分支節(jié)點都存在左右子樹苇本，且所有葉子都在同一層次。
完全二叉樹：自上往下菜拓，自左往右從1開始編號瓣窄，所有節(jié)點的編號與滿二叉樹一致的二叉樹，是一顆完全二叉樹（最下層葉子集中在左邊）纳鼎。
二叉樹的性質(zhì)
① 一棵非空二叉樹第i層俺夕，最多有2^（i-1）個節(jié)點
各種樹
滿二叉樹
所有分支節(jié)點都存在左右子樹裳凸，且所有葉子都在同一層次。
完全二叉樹
自上往下劝贸，自左往右從1開始編號姨谷，所有節(jié)點的編號與滿二叉樹一致的二叉樹，是一顆完全二叉樹（最下層葉子集中在左邊）映九。
二叉查找樹
又稱為二叉排序樹梦湘、二叉搜索樹，具有如下性質(zhì)的樹為二叉查找樹：
① 要么是一棵空樹件甥，否則
② 若任意子節(jié)點左子樹非空捌议，則左子樹上所有節(jié)點的值均小于根節(jié)點的值
③ 若任意子節(jié)點的右子樹非空，則右子樹所有節(jié)點的值均大于根節(jié)點的值
④ 任意子節(jié)點的左右子樹也分別為二叉查找樹
⑤ 沒有值相等的節(jié)點
由上述可得出引有，平衡二叉樹的中序遍歷為升序序列瓣颅。
二叉查找樹的查詢復(fù)雜度，和二分查找一樣譬正，插入和查找的時間復(fù)雜度均為 O(logn) 宫补，但是在最壞的情況下仍然會有 O(n) 的時間復(fù)雜度。原因在于插入和刪除元素的時候导帝，樹沒有保持平衡守谓，如下兩種二叉查找樹，其查找性能不可同日而語您单。
[圖片上傳失敗...(image-7e99e5-1594457410235)]
二叉查找樹的操作主要有插入、刪除荞雏、查找
插入：可以總結(jié)為虐秦，找葉子節(jié)點à插入
void myBinTree::Insert(int data){
Node *tmp = new Node;
tmp->data = data;
tmp->lChild = tmp->rChild = nullptr;
if (!m_root) {
m_root = tmp;
return;
}
Node *p = m_root;
//找葉子節(jié)點
while (1) {
if (data < p->data){
if (p->lChild) {
p = p->lChild;
}
else {
break;
}
}
else{
if (p->rChild) {
p = p->rChild;
}
else {
break;
}
}
}
//插入
if (data < p->data) {
p->lChild = tmp;
}
else{
p->rChild = tmp;
}
}
查找：
Node* myBinTree::Search(int key) {
Node *p = m_root;
while (p) {
if (key == p->data) {
return p;
}
else if (key < p->data) {
p = p->lChild;
}
else if (key > p->data) {
p = p->rChild;
}
}
return nullptr;
}
刪除：
平衡樹
平衡樹是任意節(jié)點的左右子樹高度差小于等于1的樹。常見的平衡樹有B樹（多路平衡搜索樹——不是二叉樹）凤优、AVL樹（二叉平衡搜索樹）悦陋。
平衡二叉樹
又稱為AVL數(shù)，具有如下
