二叉樹
滿二叉樹
國內(nèi)教程定義：一個二叉樹端逼，如果每一個層的結(jié)點數(shù)都達(dá)到最大值颜矿，則這個二叉樹就是滿二叉樹。也就是說找岖，如果一個二叉樹的層數(shù)為K陨倡，第i層上的結(jié)點數(shù)為：2(i-1)，且結(jié)點總數(shù)是(2k) -1 许布，則它就是滿二叉樹兴革。
國外(國際)定義：如果一棵二叉樹的結(jié)點要么是葉子結(jié)點，要么它有兩個孩子結(jié)點蜜唾，這樣的樹就是滿二叉樹杂曲。
完全二叉樹
判斷完全二叉樹
完全二叉樹：葉節(jié)點只能出現(xiàn)在最下層和次下層，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置的二叉樹（我的理解是完全二叉樹：就是滿二叉樹去掉最下層最右邊的一些節(jié)點）
完全二叉樹定義
完全二叉樹(Complete Binary Tree)
若設(shè)二叉樹的深度為h袁余，除第 h 層外擎勘，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊泌霍，這就是完全二叉樹货抄。
完全二叉樹是由【滿二叉樹】而引出來的述召。對于深度為K的，有n個結(jié)點的二叉樹蟹地，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹积暖。
一棵二叉樹至多只有最下面的一層上的結(jié)點的度數(shù)可以小于2，并且最下層上的結(jié)點都集中在該層最左邊的若干位置上怪与，則此二叉樹成為完全二叉樹夺刑。
二叉排序樹
二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree）分别，亦稱二叉搜索樹遍愿。
定義：
二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：
（1）若左子樹不空耘斩，則左子樹上所有結(jié)點的值均小于或等于它的根結(jié)點的值沼填；
（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值括授；
（3）左坞笙、右子樹也分別為二叉排序樹；
查找：
若根結(jié)點的關(guān)鍵字值等于查找的關(guān)鍵字荚虚，成功薛夜。
否則，若小于根結(jié)點的關(guān)鍵字值版述，遞歸查左子樹梯澜。
若大于根結(jié)點的關(guān)鍵字值，遞歸查右子樹渴析。
若子樹為空晚伙，查找不成功。
完全二叉樹的存儲
1.鏈表
鏈表中每一個節(jié)點俭茧，包含兩個指針leftchild撬腾，rightchild，分別指向左右子樹
2.數(shù)組
利用平衡二叉樹平衡的特性恢恼，使用數(shù)組來存儲完全二叉樹民傻，a[n]的左右子節(jié)點分別為a[2n+1]，a[2n+2]
- [1,2,3,4,5] ?a[0] 场斑，左:a[1] 右:a[2]
- a[1]漓踢，左:a[3] 右:a[4]
數(shù)組的下標(biāo)是從0開始的，二叉樹是從1開始的漏隐。
二叉排序樹插入
- 將待插入節(jié)點添加到數(shù)組的最后喧半，即平衡二叉樹的最后一個葉子節(jié)點。
- 從最后一個子樹的根節(jié)點a(n/2)開始青责，調(diào)整所有子樹挺据，使其保持大頂堆特性（a[n] >= a[2n+1], a[n] >= a[2n+2]）
（這是從下往上調(diào)整取具，堆排序是從上往下調(diào)整）
堆排序
定義
實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：
一個數(shù)組a[N]共N個元素, 設(shè)2k+1 < N（K為所有的根節(jié)點）,如果a[k] >= a[2k + 1] 且a[k] >= a[2k+2]，則該堆為大頂堆扁耐。
實現(xiàn)思路
- 將a[0 - n-1]建立為一個大頂堆暇检，此時a[0]為數(shù)組里的最大值（共有n個元素）
- 將首尾元素a[0]與a[n-1]交換，這樣a[n-1]為堆a[0 – n-1]的最大值婉称，同時a[0-(n-2)]為無序樹
- 調(diào)整a[0 – (n-2)]為大頂堆块仆，再次交換首尾元素
- ...重復(fù)步驟3直到最后一個元素，得到一個升序數(shù)組a[0 - n-1]
建堆
- 一個有n個節(jié)點的完全二叉樹王暗，有n/2個父節(jié)點悔据。
從最后一個父節(jié)點a[n/2-1]開始，將每一個以該父節(jié)點為頂點的樹調(diào)整為大頂堆（從下往上依次調(diào)整）俗壹。
調(diào)整過程科汗，因為被調(diào)整樹除了根節(jié)點（即a[0]）外，其余父節(jié)點均大于子節(jié)點（因為建堆的時候绷雏，就是建的一個大頂堆）肛捍，所以可以采取向下調(diào)整一次即可（不用從下往上調(diào)整，因為第二次調(diào)整的時候之众，第二層就存在最大值了）。
排序
- 將當(dāng)前大頂堆依许，最大元素根節(jié)點與最后一個元素交換
- 交換后棺禾，最大的元素在數(shù)組的最后，同時調(diào)整前面的n-1個元素為大根堆
- 重復(fù)步驟2峭跳，直到最后一個元素膘婶，此時，數(shù)組為升序數(shù)組蛀醉。
下面是一個數(shù)組的排序的實現(xiàn)過程：
需要注意的是：
第一步：圖中樹1悬襟，是在交換了7和5過后，所以要調(diào)整子樹拯刁，但是子樹是節(jié)點5脊岳，所以不需要調(diào)整。
第二步：圖中樹2垛玻，是在交換了7和3過后割捅，所以也要調(diào)整子樹，這時子樹的父節(jié)點是3帚桩，左右子節(jié)點分別是6和5亿驾，所以必須要調(diào)整成樹3過后，才算建堆完成账嚎。所以說每當(dāng)子節(jié)點和父節(jié)點產(chǎn)生了交換過后莫瞬，都必須要調(diào)整其下面的子樹儡蔓。
總結(jié)：
建堆的時候，從最后一個父節(jié)點向上調(diào)整到根節(jié)點疼邀，但是調(diào)整是往下調(diào)整的喂江，而且每當(dāng)子節(jié)點和父節(jié)點需要交換的時候，交換過后檩小，還要從這個父節(jié)點往下調(diào)整這顆子樹开呐，如圖中的樹1到樹3的過程。
排序時調(diào)整的時候规求，從根節(jié)點向下調(diào)整到最后一個需要調(diào)整的根節(jié)點筐付。這里的調(diào)整和建堆時候的調(diào)整一樣，也是往下調(diào)整阻肿。
下面是相關(guān)堆排序的代碼瓦戚，其實只要直到了原理，寫代碼就很簡單了
/*
//向下調(diào)整
a:需要調(diào)整的數(shù)組
head:開始調(diào)整的位置
length:數(shù)組長度
*/
+ (void)ajustHeapWith:(int *)a head:(int)head length:(uint)length
{
int leftChild = 2 * head + 1;
int switchChild = leftChild; //交換的子節(jié)點
if (leftChild >= length) { //當(dāng)只剩一個元素的時候丛塌，滿足這個條件较解，也就是遞歸的出口了
return;
}
int rightChild = leftChild + 1;
if (rightChild < length) {
//如果右子節(jié)點存在，且大于左子節(jié)點
if (a[rightChild] > a[leftChild]) {
switchChild = rightChild; //就讓交換的子節(jié)點等于右子節(jié)點
}
}
//判斷是否要交換
if (a[switchChild] > a[head]) {
//交換
[self swap:&a[switchChild] with:&a[head]];
//調(diào)整一下被交換過的子樹
[self ajustHeapWith:a head:switchChild length:length];
}
}
//建堆
+ (void)buidHeapWith:(int *)a length:(uint)length
{
for (int i = length/2 -1; i >= 0; i--) {
[self ajustHeapWith:a head:i length:length]; //從下往上調(diào)整赴邻，但是調(diào)整是向下調(diào)整的
}
}
+ (void)sortCArray:(int *)a length:(uint)length
{
//1.建堆
[self buidHeapWith:a length:length];
//2.排序
for (int i = length - 1; i > 0; i--) {
// 1.交換a[0]與a[i]
[self swap:&a[0] with:&a[i]];
// 2.調(diào)整堆（移除了最后一個元素印衔，即最大值，所以長度減1.然后從a[0]往下開始調(diào)整）
[self ajustHeapWith:a head:0 length:i];
}
}
+ (void)testHeapSort
{
int maxCount = 1000;
int *a = [self unsortedCArrayWithLenght:maxCount];
[self logArray:a length:maxCount];
[self sortCArray:a length:maxCount];
[self checkAsendingSortArray:a length:maxCount];
[self logArray:a length:maxCount];
free(a);
}
+ (BOOL)checkAsendingSortArray:(int [])a length:(int)length
{
for (int i = 0; i < length - 1; i++) {
if (a[i] > a[i+1]) {
NSLog(@"位置:%d,%d; 位置:%d,%d",i,a[i],i+1,a[i+1]);
NSLog(@"非升序數(shù)組＠蚜病奸焙！");
return false;
}
}
NSLog(@"該數(shù)組是升序數(shù)組！彤敛！");
return true;
}
+ (void)logArray:(int[])a length:(int)length
{
for (int i = 0; i < length; i++) {
NSLog(@"%d",a[i]);
}
}
+ (int *)unsortedCArrayWithLenght:(NSUInteger)length
{
int *a = (int *) malloc(sizeof(int) * length);
for (int i = 0; i < length; i++) {
a[i] = rand()%length;
}
return a;
}
+ (void)swap:(int *)a with:(int *)b
{
int temp = *a;
*a = *b;
*b = temp;
}
二叉樹遍歷
所謂遍歷(Traversal)是指沿著某條搜索路線与帆，依次對樹中每個結(jié)點均做一次且僅做一次訪問。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問 題墨榄。 遍歷是二叉樹上最重要的運算之一玄糟，是二叉樹上進(jìn)行其它運算之基礎(chǔ)。
中序遍歷
LNR：中序遍歷(Inorder Traversal)
——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間）袄秩。
即中根遍歷阵翎，左中右前序遍歷/先序遍歷
NLR：前序遍歷(Preorder Traversal 亦稱（先序遍歷））
——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前。
根在最前面之剧，根左右后序遍歷
LRN：后序遍歷(Postorder Traversal)
——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后贮喧。
根在最后面，左右根
如上圖中遍歷結(jié)果為：
- 中序遍歷 （對于每一個父節(jié)點和左右子節(jié)點來說都是 “左父右”）
GDH B E A K C IJ F - 前序遍歷/先序遍歷 （先是根節(jié)點和左邊的依次所有左子節(jié)點猪狈，然后從下往上依次所有的右子節(jié)點箱沦，最后再是根節(jié)點右邊的子節(jié)點，依次往下雇庙，如果有子的左節(jié)點谓形，就依次往下下去灶伊，直到?jīng)]有了，再從右子節(jié)點開始）
ABDGHECKFIJ （左子節(jié)點優(yōu)先） - 后序遍歷（寫的時候從右往左開始寫寒跳，先是根節(jié)點聘萨，然后是右邊的子節(jié)點，如果右邊的子節(jié)點還有下一層右邊的子節(jié)點童太，就依次往下米辐，直到?jīng)]有了右邊的子節(jié)點，再依次往上找左邊的子節(jié)點书释，然后才是根節(jié)點的左邊的子節(jié)點翘贮，如果有右子節(jié)點就右子節(jié)點優(yōu)先）
GHDEBKJIFCA （右子節(jié)點優(yōu)先）
實例題：
- 求后序遍歷是多少
前序遍歷：GDAFEMHZ
中序遍歷：ADEFGHMZ
結(jié)合上面兩個遍歷，前序遍歷確定根節(jié)點爆惧，中序遍歷確定左右子節(jié)點狸页，從而畫出二叉樹圖，再寫出后序遍歷扯再。
如上圖芍耘，后序遍歷為：AEFDHZMG
