在計算機科學(xué)中，二叉樹(Binary Tree)是包含n個節(jié)點的有限集合，該集合或者為空集（此時，二叉樹稱為空樹），或者由一個根節(jié)點和兩棵互不相交的、分別稱為根節(jié)點的左子樹和右子樹的二叉樹組成。
前文
本文主要講述了對二叉排序樹的創(chuàng)建及其它操作，二叉排序樹具有以下幾個特點：
1、若任意節(jié)點的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；
2、若任意節(jié)點的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；
3、任意節(jié)點的左、右子樹也分別為二叉查找樹；
4、沒有鍵值相等的節(jié)點。
接下來我們通過用OC代碼實現(xiàn)的方式完成對二叉排序樹的一些基礎(chǔ)操作，其中主要就是考察我們的遞歸思想。
首先我們以二叉樹的節(jié)點為一個類創(chuàng)建一個類，這個類擁有兩個屬性，分別是左節(jié)點和右節(jié)點。如下所示：
@interface DyBinaryTreeNode : NSObject
@property (nonatomic, strong) DyBinaryTreeNode *leftNode;
@property (nonatomic, strong) DyBinaryTreeNode *rightNode;
接著，我們便可以依次定義并實現(xiàn)其操作方法了。
0x01 創(chuàng)建二叉排序樹
1、創(chuàng)建二叉樹
/
* @param values 數(shù)組
* @return 二叉樹根節(jié)點
*/
+ (DyBinaryTreeNode *)createTreeWithValues:(NSArray *)values {
DyBinaryTreeNode *root = nil;
for (NSInteger i=0; i<values.count; i++) {
NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue];
root = [DyBinaryTreeNode addTreeNode:root value:value];
}
return root;
}
我們通過以下方法調(diào)用：
NSArray *arr = [NSArray arrayWithObjects:@(7),@(6),@(3),@(2),@(1),@(9),@(10),@(12),@(14),@(4),@(15),nil];
DyBinaryTreeNode *tree = [DyBinaryTreeNode new];
tree = [DyBinaryTreeNode createTreeWithValues:arr];
會生成如下圖所示的二叉排序樹：
2、獲取某個位置的節(jié)點（層序）
大致思路
1、將根節(jié)點加到隊列中，當(dāng)隊列有元素時循環(huán)。
2、循環(huán)一次將隊列的第一個元素出隊列，index-1
3、當(dāng)index=0時返回此時的根節(jié)點。
4、遍歷隊列第一個元素(根節(jié)點)的左節(jié)點和右節(jié)點，加到隊列中。
/* @param index 按層次遍歷樹時的位置(從0開始算)
* @param rootNode 樹根節(jié)點
* @return 節(jié)點
*/
+ (DyBinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(DyBinaryTreeNode *)rootNode {
//按層次遍歷
if (!rootNode || index < 0) {
return nil;
}
//數(shù)組當(dāng)成隊列
NSMutableArray *queueArray = [NSMutableArray array];
//壓入根節(jié)點
[queueArray addObject:rootNode];
while (queueArray.count > 0) {
DyBinaryTreeNode *node = [queueArray firstObject];
if (index == 0) {//返回根節(jié)點。
return node;
}
//彈出最前面的節(jié)點，仿照隊列先進先出原則
[queueArray removeObjectAtIndex:0];
//移除節(jié)點，index減少
index--;
if (node.leftNode) {
[queueArray addObject:node.leftNode]; //壓入左節(jié)點
}
if (node.rightNode) {
[queueArray addObject:node.rightNode]; //壓入右節(jié)點
}
}
//層次遍歷完，仍然沒有找到位置，返回nil
return nil;
}
調(diào)用當(dāng)index==8時，打印的值為1。
DyBinaryTreeNode *tree1 = [DyBinaryTreeNode treeNodeAtIndex:8 inTree:tree];
NSLog(@"節(jié)點值為==%ld\n",tree1.value);
0x02 二叉樹遍歷
分為先序遍歷、中序遍歷、后序遍歷、層序遍歷。
先、中、后主要是指遍歷根的順序，如果先遍歷根便是先序，其它類似。左節(jié)點和右節(jié)點的遍歷順序固定(先左后右)。
層序遍歷：從上至下，從左至右依次遍歷。
可參考wiki的樹的遍歷
1、先序遍歷
先訪問根，再遍歷左子樹，再遍歷右子樹。典型的遞歸思想。
通過block，依次將遍歷到的node值回調(diào)回去。
/ *
根-左-右
@param rootNode 根節(jié)點
* @param handler 訪問節(jié)點處理函數(shù)
*/
+ (void)preOrderTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^)(DyBinaryTreeNode *treeNode))handler {
if (rootNode) {
if (handler) {
handler(rootNode);//根
}
[DyBinaryTreeNode preOrderTraverseTree:rootNode.leftNode handler:handler];//左
[DyBinaryTreeNode preOrderTraverseTree:rootNode.rightNode handler:handler];//右
}
}
2、中序遍歷
先遍歷左子樹，再訪問根，再遍歷右子樹
/**
* 左 根 右
* @param rootNode 根節(jié)點
* @param handler 訪問節(jié)點處理函數(shù)
*/
+ (void)inOrderTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^) (DyBinaryTreeNode *treeNode))handler {
if (rootNode) {
[DyBinaryTreeNode inOrderTraverseTree:rootNode.leftNode handler:handler];//左
if (handler) {
handler(rootNode);//中
}
[DyBinaryTreeNode inOrderTraverseTree:rootNode.rightNode handler:handler];//右
}
}
3、后序遍歷
先遍歷左子樹，再遍歷右子樹，再訪問根
/**
* @param rootNode 根節(jié)點
* @param handler 訪問節(jié)點處理函數(shù)
*/
+ (void)postOrderTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^)(DyBinaryTreeNode *treeNode))handler {
if (rootNode) {
[DyBinaryTreeNode postOrderTraverseTree:rootNode.leftNode handler:handler];
[DyBinaryTreeNode postOrderTraverseTree:rootNode.rightNode handler:handler];
if (handler) {
handler(rootNode);
}
}
}
以上三種遍歷方式依次打印為：
先序遍歷結(jié)果：7,6,3,2,1,4,9,10,12,14,15
中序遍歷結(jié)果：1,2,3,4,6,7,9,10,12,14,15
后序遍歷結(jié)果：1,2,4,3,6,15,14,12,10,9,7
3、層序遍歷
同上根據(jù)index獲取節(jié)點的值的思想一樣。
通過數(shù)組模擬隊列，進行遍歷操作。
+ (void)levelTraverseTree:(DyBinaryTreeNode *)rootNode handler:(void(^)(DyBinaryTreeNode *treeNode))handler {
if (!rootNode) {
return;
}
NSMutableArray *queueArray = [NSMutableArray array]; //數(shù)組當(dāng)成隊列
[queueArray addObject:rootNode]; //壓入根節(jié)點
while (queueArray.count > 0) {
DyBinaryTreeNode *node = [queueArray firstObject];
if (handler) {
handler(node);
}
[queueArray removeObjectAtIndex:0]; //彈出最前面的節(jié)點，仿照隊列先進先 出原則
if (node.leftNode) {
[queueArray addObject:node.leftNode]; //壓入左節(jié)點
}
if (node.rightNode) {
[queueArray addObject:node.rightNode]; //壓入右節(jié)點
}
}
}
0x03 獲取二叉樹的屬性
1、獲取二叉樹的深度
二叉樹的深度
從根節(jié)點到葉子節(jié)點依次經(jīng)過的節(jié)點（含根、葉節(jié)點）形成樹的一條路徑，最長路徑的長度包含的節(jié)點數(shù)為樹的深度。
可以理解為二叉樹有多少層。
遞歸思想：二叉樹的深度 = MAX(左子樹深度，右子樹深度)+1
1:根節(jié)點。
/*
* @param rootNode 二叉樹根節(jié)點
*
* @return 二叉樹的深度
*/
+ (NSInteger)depthOfTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
if (!rootNode.leftNode && !rootNode.rightNode) {
return 1;
}
//左子樹深度
NSInteger leftDepth = [DyBinaryTreeNode depthOfTree:rootNode.leftNode];
//右子樹深度
NSInteger rightDepth = [DyBinaryTreeNode depthOfTree:rootNode.rightNode];
return MAX(leftDepth, rightDepth) + 1;
}
2、獲取二叉樹的寬度
隊列的最大長度，結(jié)點數(shù)最多的層的結(jié)點數(shù)。
思想：同層序遍歷，保存隊列中最多元素時的元素個數(shù)。
/*
* @param rootNode 二叉樹根節(jié)點
*
* @return 二叉樹寬度
*/
+ (NSInteger)widthOfTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
NSMutableArray *queueArray = [NSMutableArray array]; //數(shù)組當(dāng)成隊列
[queueArray addObject:rootNode]; //壓入根節(jié)點
NSInteger maxWidth = 1; //最大的寬度，初始化為1（因為已經(jīng)有根節(jié)點）
NSInteger curWidth = 0; //當(dāng)前層的寬度
while (queueArray.count > 0) {
curWidth = queueArray.count;
//依次彈出當(dāng)前層的節(jié)點
for (NSInteger i=0; i<curWidth; i++) {
DyBinaryTreeNode *node = [queueArray firstObject];
[queueArray removeObjectAtIndex:0]; //彈出最前面的節(jié)點，仿照隊列先進先出原則
//壓入子節(jié)點
if (node.leftNode) {
[queueArray addObject:node.leftNode];
}
if (node.rightNode) {
[queueArray addObject:node.rightNode];
}
}
//寬度 = 當(dāng)前層節(jié)點數(shù)
maxWidth = MAX(maxWidth, queueArray.count);
}
return maxWidth;
}
3、獲取二叉樹的節(jié)點數(shù)
遞歸思想：節(jié)點數(shù)=左子樹節(jié)點數(shù)+右子樹節(jié)點數(shù)+1（根節(jié)點）
+ (NSInteger)numberOfNodesInTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
//節(jié)點數(shù)=左子樹節(jié)點數(shù)+右子樹節(jié)點數(shù)+1（根節(jié)點）
return [DyBinaryTreeNode numberOfNodesInTree:rootNode.leftNode] + [DyBinaryTreeNode numberOfNodesInTree:rootNode.rightNode] + 1;
}
4、獲取二叉樹某一層的節(jié)點數(shù)
遞歸思想：level層節(jié)點數(shù) = 左子樹level-1層節(jié)點數(shù)+右子樹level-1層節(jié)點數(shù)
+ (NSInteger)numberOfNodesOnLevel:(NSInteger)level inTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode || level < 1) { //根節(jié)點不存在或者level<0
return 0;
}
if (level == 1) { //level=1，返回1（根節(jié)點）
return 1;
}
//遞歸：level層節(jié)點數(shù) = 左子樹level-1層節(jié)點數(shù)+右子樹level-1層節(jié)點數(shù)
return [DyBinaryTreeNode numberOfNodesOnLevel:level-1 inTree:rootNode.leftNode] + [DyBinaryTreeNode numberOfNodesOnLevel:level-1 inTree:rootNode.rightNode];
}
5、獲取葉子節(jié)點數(shù)
葉子節(jié)點：左子樹和右子樹都是空的節(jié)點。
遞歸思想：葉子數(shù) = 左子樹葉子數(shù) + 右子樹葉子數(shù)
+ (NSInteger)numberOfLeafsInTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
//左子樹和右子樹都是空，說明是葉子節(jié)點
if (!rootNode.leftNode && !rootNode.rightNode) {
return 1;
}
//遞歸：葉子數(shù) = 左子樹葉子數(shù) + 右子樹葉子數(shù)
return [DyBinaryTreeNode numberOfLeafsInTree:rootNode.leftNode] + [DyBinaryTreeNode numberOfLeafsInTree:rootNode.rightNode];
}
6、獲取二叉樹的最大直徑
二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的，定義“距離”為兩個節(jié)點之間的邊數(shù)。
遞歸思想：
分為三種情況
1、最遠距離經(jīng)過根節(jié)點：距離 = 左子樹深度 + 右子樹深度
2、最遠距離在根節(jié)點左子樹上，即計算左子樹最遠距離
3、最遠距離在根節(jié)點右子樹上，即計算右子樹最遠距離
+ (NSInteger)maxDistanceOfTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return 0;
}
//方案一：（遞歸次數(shù)較多，效率較低）
NSInteger distance = [DyBinaryTreeNode depthOfTree:rootNode.leftNode] + [DyBinaryTreeNode depthOfTree:rootNode.rightNode];
NSInteger disLeft = [DyBinaryTreeNode maxDistanceOfTree:rootNode.leftNode];
NSInteger disRight = [DyBinaryTreeNode maxDistanceOfTree:rootNode.rightNode];
return MAX(MAX(disLeft, disRight), distance);
}
0x04 翻轉(zhuǎn)二叉樹
又叫：二叉樹的鏡像。交換節(jié)點的左節(jié)點和右節(jié)點。
1、遞歸翻轉(zhuǎn)
遞歸思想：先交換當(dāng)前節(jié)點的左右節(jié)點，再遞歸調(diào)用去翻轉(zhuǎn)以左右節(jié)點為根節(jié)點的二叉樹。
+ (DyBinaryTreeNode *)invertBinaryTree:(DyBinaryTreeNode *)rootNode {
if (!rootNode) {
return nil;
}
if (!rootNode.leftNode && !rootNode.rightNode) {
return rootNode;
}
//交換當(dāng)前節(jié)點的左右節(jié)點。
DyBinaryTreeNode *tempNode = rootNode.leftNode;
rootNode.leftNode = rootNode.rightNode;
rootNode.rightNode = tempNode;
//遞歸交換左右子節(jié)點
[DyBinaryTreeNode invertBinaryTree:rootNode.leftNode];
[DyBinaryTreeNode invertBinaryTree:rootNode.rightNode];
return rootNode;
}
2、非遞歸翻轉(zhuǎn)
思想：類似于層序遍歷，將即將入隊列的節(jié)點交換其左右節(jié)點。
/**
* 非遞歸方式翻轉(zhuǎn)
*/
+ (DyBinaryTreeNode *)invertBinaryTreeNot:(DyBinaryTreeNode *)rootNode {
if (!rootNode) { return nil; }
if (!rootNode.leftNode && !rootNode.rightNode) { return rootNode; }
NSMutableArray *queueArray = [NSMutableArray array]; //數(shù)組當(dāng)成隊列
[queueArray addObject:rootNode]; //壓入根節(jié)點
while (queueArray.count > 0) {
DyBinaryTreeNode *node = [queueArray firstObject];
[queueArray removeObjectAtIndex:0]; //彈出最前面的節(jié)點，仿照隊列先進先出原則
DyBinaryTreeNode *pLeft = node.leftNode;
node.leftNode = node.rightNode;
node.rightNode = pLeft;
if (node.leftNode) {
[queueArray addObject:node.leftNode];
}
if (node.rightNode) {
[queueArray addObject:node.rightNode];
}
}
return rootNode;
}
備注
關(guān)于二叉樹的基本算法先介紹到此處，后續(xù)會補充更多關(guān)于二叉樹操作的一些算法。
