iOS_算法之二叉樹

什么是二叉樹急侥?

在計算機(jī)科學(xué)中执赡,二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”和“右子樹”歇父,左子樹和右子樹同時也是二叉樹蒂培。二叉樹的子樹有左右之分,并且次序不能任意顛倒榜苫。二叉樹是遞歸定義的护戳,所以一般二叉樹的相關(guān)題目也都可以使用遞歸的思想來解決,當(dāng)然也有一些可以使用非遞歸的思想解決单刁,我下面列出的一些算法有些采用了遞歸灸异,有些是非遞歸的。

什么是二叉排序樹羔飞?

二叉排序樹又叫二叉查找樹或者二叉搜索樹肺樟,它首先是一個二叉樹,而且必須滿足下面的條件:

1)若左子樹不空逻淌,則左子樹上所有結(jié)點的值均小于它的根節(jié)點的值么伯;

2)若右子樹不空,則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值

3)左卡儒、右子樹也分別為二叉排序樹

概念就介紹這么多田柔,都是來自網(wǎng)上,下面主要看算法和具體實現(xiàn)代碼骨望。

二叉樹節(jié)點定義:采用單項鏈表的形式硬爆,只從根節(jié)點指向孩子節(jié)點,不保存父節(jié)點擎鸠。

*? 二叉樹節(jié)點

*/@interfaceBinaryTreeNode : NSObject/**

*? 值

*/@property(nonatomic, assign) NSInteger value;/**

*? 左節(jié)點

*/@property(nonatomic, strong) BinaryTreeNode *leftNode;/**

*? 右節(jié)點

*/@property(nonatomic, strong) BinaryTreeNode *rightNode;

@end

創(chuàng)建二叉排序樹

二叉樹中左右節(jié)點值本身沒有大小之分缀磕,所以如果要創(chuàng)建二叉樹,就需要考慮如何處理某個節(jié)點是左節(jié)點還是右節(jié)點,如何終止某個子樹而切換到另一個子樹袜蚕。 因此我選擇了二叉排序樹糟把,二叉排序樹中對于左右節(jié)點有明確的要求,程序可以自動根據(jù)鍵值大小自動選擇是左節(jié)點還是右節(jié)點牲剃。

/** *? 創(chuàng)建二叉排序樹 *? 二叉排序樹:左節(jié)點值全部小于根節(jié)點值遣疯,右節(jié)點值全部大于根節(jié)點值 * *@paramvalues 數(shù)組 * *@return二叉樹根節(jié)點 */

+ (BinaryTreeNode *)createTreeWithValues:(NSArray *)values {

BinaryTreeNode *root = nil;

for(NSInteger i=0; i<values.count;i++) {

NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue];

root = [BinaryTree addTreeNode:root value:value];

}

return root;

}

/** *? 向二叉排序樹節(jié)點添加一個節(jié)點 *

?*@paramtreeNode 根節(jié)點

?*@paramvalue值 *

?*@return根節(jié)點 */

+ (BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value {//根節(jié)點不存在,創(chuàng)建節(jié)點

if(!treeNode) {

treeNode = [BinaryTreeNodenew];

treeNode.value = value;

NSLog(@"node:%@", @(value));

}elseif(value <= treeNode.value) {

NSLog(@"to left");//值小于根節(jié)點凿傅,則插入到左子樹

treeNode.leftNode = [BinaryTree addTreeNode:treeNode.leftNode value:value];

}else{

NSLog(@"to right");//值大于根節(jié)點缠犀,則插入到右子樹

treeNode.rightNode = [BinaryTree addTreeNode:treeNode.rightNode value:value];

}

returntreeNode;

}

二叉樹中某個位置的節(jié)點

類似索引操作,按層次遍歷聪舒,位置從0開始算夭坪。

/** *? 二叉樹中某個位置的節(jié)點(按層次遍歷) *?

*@paramindex按層次遍歷樹時的位置(從0開始算)?

*@paramrootNode 樹根節(jié)點 *

?*@return節(jié)點 */

+ (BinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(BinaryTreeNode *)rootNode {//按層次遍歷if(!rootNode || index <0) {

returnnil;

}

NSMutableArray *queueArray = [NSMutableArray array];

//數(shù)組當(dāng)成隊列[queueArray addObject:rootNode];

//壓入根節(jié)點

while(queueArray.count >0) {

BinaryTreeNode *node = [queueArray firstObject];

if(index ==0) {

return node;

}

[queueArray removeObjectAtIndex:0];

//彈出最前面的節(jié)點,仿照隊列先進(jìn)先出原則index--;

//移除節(jié)點过椎,index減少

if(node.leftNode) {

[queueArray addObject:node.leftNode];//壓入左節(jié)點

}if(node.rightNode) {

[queueArray addObject:node.rightNode];//壓入右節(jié)點

}

}//層次遍歷完,仍然沒有找到位置戏仓,返回nil

return nil;

}

先序遍歷

先訪問根疚宇,再遍歷左子樹,再遍歷右子樹赏殃。典型的遞歸思想敷待。

/** *? 先序遍歷 *? 先訪問根,再遍歷左子樹仁热,再遍歷右子樹 *?

*@paramrootNode 根節(jié)點?

*@paramhandler? 訪問節(jié)點處理函數(shù) */

+ (void)preOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {

if(rootNode) {

if(handler) {

handler(rootNode);

}

[self preOrderTraverseTree:rootNode.leftNode handler:handler];

[self preOrderTraverseTree:rootNode.rightNode handler:handler];

}

}

NSMutableArray*orderArray= [NSMutableArray array];

[BinaryTree preOrderTraverseTree:root handler:^(BinaryTreeNode*treeNode) {??

? [orderArray addObject:@(treeNode.value)];

}];

NSLog(@"先序遍歷結(jié)果:%@", [orderArray componentsJoinedByString:@","]);

中序遍歷

先遍歷左子樹榜揖,再訪問根,再遍歷右子樹抗蠢。

對于二叉排序樹來說举哟,中序遍歷得到的序列是一個從小到大排序好的序列。

/** *? 中序遍歷 *? 先遍歷左子樹迅矛,再訪問根,再遍歷右子樹 *?

*@paramrootNode 根節(jié)點?

*@paramhandler? 訪問節(jié)點處理函數(shù) */

+ (void)inOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {

if(rootNode) {

[self inOrderTraverseTree:rootNode.leftNode handler:handler];

if(handler) {handler(rootNode);

}

[self inOrderTraverseTree:rootNode.rightNode handler:handler];

}

}

后序遍歷

先遍歷左子樹,再遍歷右子樹咬腕,再訪問根

/** *? 后序遍歷 *? 先遍歷左子樹徒探,再遍歷右子樹,再訪問根 *

?*@paramrootNode 根節(jié)點?

*@paramhandler? 訪問節(jié)點處理函數(shù) */

+ (void)postOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {

if(rootNode) {

[self postOrderTraverseTree:rootNode.leftNode handler:handler];

[self postOrderTraverseTree:rootNode.rightNode handler:handler];

if(handler) {

handler(rootNode);

}

}}

層次遍歷

按照從上到下销斟、從左到右的次序進(jìn)行遍歷庐椒。先遍歷完一層,再遍歷下一層蚂踊,因此又叫廣度優(yōu)先遍歷约谈。需要用到隊列,在OC里可以用可變數(shù)組來實現(xiàn)。

/** *? 層次遍歷(廣度優(yōu)先) *

?*@paramrootNode 二叉樹根節(jié)點?

*@paramhandler? 訪問節(jié)點處理函數(shù) */

+ (void)levelTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {

if(!rootNode) {

return;}

NSMutableArray *queueArray = [NSMutableArray array];//數(shù)組當(dāng)成隊列

[queueArray addObject:rootNode];//壓入根節(jié)點

while(queueArray.count >0) {

BinaryTreeNode *node = [queueArray firstObject];

if(handler) {

handler(node);}

[queueArray removeObjectAtIndex:0];//彈出最前面的節(jié)點窗宇,仿照隊列先進(jìn)先出原則

if(node.leftNode) {

[queueArray addObject:node.leftNode];//壓入左節(jié)點

}

if(node.rightNode) {

[queueArray addObject:node.rightNode];//壓入右節(jié)點

}

}}

二叉樹的深度

二叉樹的深度定義為:從根節(jié)點到葉子結(jié)點依次經(jīng)過的結(jié)點形成樹的一條路徑,最長路徑的長度為樹的深度

1)如果根節(jié)點為空措伐,則深度為0;

2)如果左右節(jié)點都是空军俊,則深度為1侥加;

3)遞歸思想:二叉樹的深度=max(左子樹的深度,右子樹的深度)+ 1

/** *? 二叉樹的深度 *

?*@paramrootNode 二叉樹根節(jié)點 *?

*@return二叉樹的深度 */

+ (NSInteger)depthOfTree:(BinaryTreeNode *)rootNode {

if(!rootNode) {

return0;}

if(!rootNode.leftNode && !rootNode.rightNode) {

return1;}//左子樹深度

NSInteger leftDepth = [self depthOfTree:rootNode.leftNode];

//右子樹深度

NSInteger rightDepth = [self depthOfTree:rootNode.rightNode];

returnMAX(leftDepth, rightDepth) +1;}

二叉樹的寬度

二叉樹的寬度定義為各層節(jié)點數(shù)的最大值粪躬。

/** *? 二叉樹的寬度 *?

*@paramrootNode 二叉樹根節(jié)點 *?

*@return二叉樹寬度 */

+ (NSInteger)widthOfTree:(BinaryTreeNode *)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++){

BinaryTreeNode *node = [queueArray firstObject];

[queueArray removeObjectAtIndex:0];

//彈出最前面的節(jié)點,仿照隊列先進(jìn)先出原則

//壓入子節(jié)點

if(node.leftNode) {

[queueArray addObject:node.leftNode];

}

if(node.rightNode) {

[queueArray addObject:node.rightNode];

}

}

//寬度 = 當(dāng)前層節(jié)點數(shù)

maxWidth = MAX(maxWidth, queueArray.count);

}returnmaxWidth;

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末镰官,一起剝皮案震驚了整個濱河市提前,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌泳唠,老刑警劉巖狈网,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異笨腥,居然都是意外死亡拓哺,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進(jìn)店門脖母,熙熙樓的掌柜王于貴愁眉苦臉地迎上來士鸥,“玉大人,你說我怎么就攤上這事谆级】窘福” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵肥照,是天一觀的道長脚仔。 經(jīng)常有香客問我,道長舆绎,這世上最難降的妖魔是什么玻侥? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮亿蒸,結(jié)果婚禮上凑兰,老公的妹妹穿的比我還像新娘。我一直安慰自己边锁,他們只是感情好姑食,可當(dāng)我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著茅坛,像睡著了一般音半。 火紅的嫁衣襯著肌膚如雪则拷。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天曹鸠,我揣著相機(jī)與錄音煌茬,去河邊找鬼。 笑死彻桃,一個胖子當(dāng)著我的面吹牛坛善,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播邻眷,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼眠屎,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了肆饶?” 一聲冷哼從身側(cè)響起改衩,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎驯镊,沒想到半個月后葫督,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡板惑,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年候衍,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片洒放。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖滨砍,靈堂內(nèi)的尸體忽然破棺而出往湿,到底是詐尸還是另有隱情,我是刑警寧澤惋戏,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布领追,位于F島的核電站,受9級特大地震影響响逢,放射性物質(zhì)發(fā)生泄漏绒窑。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一舔亭、第九天 我趴在偏房一處隱蔽的房頂上張望些膨。 院中可真熱鬧,春花似錦钦铺、人聲如沸订雾。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽洼哎。三九已至,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間噩峦,已是汗流浹背锭沟。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留识补,地道東北人族淮。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像李请,于是被迫代替她去往敵國和親瞧筛。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 參考兩篇其他bolg總結(jié)的二叉樹:https://github.com/xy7313/lintcode/blob/...
    暗黑破壞球嘿哈閱讀 2,380評論 0 1
  • 姓名: 李小娜 [嵌牛導(dǎo)讀] :這篇文章主要介紹了Java二叉排序樹导盅,包括二叉排序樹的定義较幌、二叉排序樹的性質(zhì)、二叉...
    n184閱讀 631評論 0 0
  • 樹的概述 樹是一種非常常用的數(shù)據(jù)結(jié)構(gòu)白翻,樹與前面介紹的線性表乍炉,棧,隊列等線性結(jié)構(gòu)不同滤馍,樹是一種非線性結(jié)構(gòu) 1.樹的定...
    Jack921閱讀 4,462評論 1 31
  • 一. 二叉樹的定義 二叉樹(Binary Tree)是 n ( n >= 0) 個節(jié)點的有限集岛琼,這個集合可以為空,...
    NahuelK閱讀 2,044評論 0 1
  • 編譯環(huán)境:python v3.5.0, mac osx 10.11.4 前述內(nèi)容: 線性表 隊列 堆棧 線性結(jié)構(gòu)...
    擲骰子的求閱讀 2,447評論 1 7