前言：

? ?一：在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。 ? ?二：二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)；對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n_0，度為2的結(jié)點(diǎn)數(shù)為n_2，則n_0=n_2+1。 ? ?三：一棵深度為k，且有2^k-1個(gè)節(jié)點(diǎn)稱之為滿二叉樹；深度為k，有n個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹中，序號(hào)為1至n的節(jié)點(diǎn)對(duì)應(yīng)時(shí)，稱之為完全二叉樹。 ? ?四：二叉樹遍歷： 先序遍歷、中序遍歷、后序遍歷、層次遍歷 、下面答案很精辟；

?

二?樹的OC創(chuàng)建源碼：

/**創(chuàng)建二叉樹@param Values 傳入數(shù)組@return return value description*/ +(ZXTThreeObject * )CreatTreesWithValues:(NSArray * )Values{__block ZXTThreeObject * rootNode = nil;/** 這里順便提一下這個(gè)循環(huán)遍歷,可能不部分都用的是for循環(huán)或者for..in..來(lái)循環(huán)的 **//** 大家了解一下 NSEnumerator 遍歷和Block遍歷還有GCD中的dispatch_apply **//** 鏈接在這里 **/[Values enumerateObjectsUsingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {int value = [obj intValue];rootNode = [self AddTreeNode:rootNode andValue:value];}];return rootNode; }/**遞歸的思想這里返回的 node 這個(gè)參數(shù)其實(shí)是一個(gè)局部變量，不管里面嵌套調(diào)用多少次AddTreeNode這個(gè)方法，這里每一次返回的一直都是它的最原始的根節(jié)點(diǎn)！！這點(diǎn)對(duì)創(chuàng)建過(guò)程的 理解很重要，但如果返回值你寫成全局變量就不一樣了，它返回的就是最后賦給它的值。這里簡(jiǎn)單說(shuō)一下，局部變量是存儲(chǔ)在棧中的，全局變量是存儲(chǔ)在靜態(tài)存儲(chǔ)區(qū)的！每存儲(chǔ)一個(gè)局部變量，編譯器就會(huì)開辟一塊棧區(qū)域來(lái)保存方法第一次傳遞的node這個(gè)變量，編譯器就開辟了棧區(qū)域保存了它的值，后面要是有嵌套調(diào)用了這個(gè)方法編譯器就又開辟新的棧區(qū)域保存它們的返回值，但不會(huì)影響第一次保存的值，你要調(diào)用多次的話，第一個(gè)保存的值也就是最后一個(gè)返回的了這就解釋了為什么每次最后的返回值都是 最原始的根節(jié)點(diǎn)了！ **/ +(ZXTThreeObject * )AddTreeNode:(ZXTThreeObject *)node andValue:(int) value{if (!node) {node = [[ZXTThreeObject alloc]init];node.Value = value;}else if (value <= node.Value){/**值小于節(jié)點(diǎn)的值，插入到左節(jié)點(diǎn)**/node.leftTreeNode = [self AddTreeNode:node.leftTreeNode andValue:value];}else{/**值大于節(jié)點(diǎn)的值，插入到右節(jié)點(diǎn)**/node.rightTreeNode = [self AddTreeNode:node.rightTreeNode andValue:value];}return node; }

你可以驗(yàn)證一下它的正確性，你在創(chuàng)建左右節(jié)點(diǎn)的時(shí)候他們打印出來(lái)，下面的數(shù)組提供大家參考：

NSArray * array = @[@2,@3,@7,@5,@9,@4,@6,@1,@8]; /** 上面的數(shù)組創(chuàng)建的二叉樹應(yīng)該是這樣的 * 代表沒有值21 3* 75 94 6 8 ***/ [ZXTThreeObject CreatTreesWithValues:array];

二?樹的Swift創(chuàng)建源碼：

class ZXTreeObject: NSObject {var leftNode :ZXTreeObject?var rightNode:ZXTreeObject?var nodevalue:Int?func CreatTreesWithValues(Values:[Int]) -> ZXTreeObject {var rootNode:ZXTreeObject?for value in Values {rootNode = self.AddTreeNode(node: &rootNode,value)}return rootNode!}/**注意在Swift3中：函數(shù)簽名中的下劃線的意思是告訴編譯器，我們?cè)谡{(diào)用函數(shù)時(shí)第一個(gè)參數(shù)不需要外帶標(biāo)簽這樣，我們可以按照 Swift 2 中的方式去調(diào)用函數(shù),還有這個(gè)下劃線和參數(shù)名之間要有空格！必須要有！**/func AddTreeNode(node: inout ZXTreeObject?, _ value:Int) -> ZXTreeObject {if (node == nil) {node = ZXTreeObject()node?.nodevalue = value}else if (value < (node?.nodevalue)!) {//print("----- to left ")_ = AddTreeNode(node: &node!.leftNode, value)}else{//print("----- to right ")_ = AddTreeNode(node: &node!.rightNode, value)}// print("節(jié)點(diǎn):",node!.nodevalue ?? 0)return node!} }

調(diào)用的時(shí)候這樣：

// 定義一個(gè)數(shù)組 let sortArray:[Int] = [2,3,7,5,9,4,6,1,8] _ = ZXTreeObject().CreatTreesWithValues(Values: sortArray)

這個(gè)結(jié)果的話大家可以把上面的打印注釋打開自己看看結(jié)果，是沒問(wèn)題的，這里在給大家看看這樣一個(gè)警告：

就這個(gè)返回值沒有使用的警告，這警告有兩種辦法消除：

/* 一：就像上面的加 _ = 在調(diào)用的函數(shù)前面 二：在函數(shù)聲明的前面加上 @discardableResult 如: @discardableResult func AddTreeNode(node: inout ZXTreeObject?, _ value:Int) -> ZXTreeObject { }*/

計(jì)算二?樹的深度OC：

/**樹的深度三種情況： 一：根節(jié)點(diǎn)要是不存在就返回0二：左節(jié)點(diǎn)和右節(jié)點(diǎn)都不存在，到這里的前提是根節(jié)點(diǎn)存在，返回1三：都存在，再遞歸獲取深度，返回最大值！@param node 節(jié)點(diǎn)@return return value description*/ // 2017-03-03 14:06:15.248 算法OC版本[22755:262170] 數(shù)的深度==5 +(NSInteger)deepWithThree:(ZXTThreeObject *)node{if (!node) {return 0; }else if (!node.leftTreeNode && !node.rightTreeNode){return 1;}else{NSInteger leftDeep = [self deepWithThree:node.leftTreeNode];NSInteger rightDeep = [self deepWithThree:node.rightTreeNode];return MAX(leftDeep, rightDeep) + 1;} }

計(jì)算二?樹的深度Swift：

// Swift 求二叉樹的深度f(wàn)unc deepWithThree(rootNode: ZXTreeObject?) -> Int {if ((rootNode) == nil){return 0 }else if((rootNode?.leftNode) == nil && (rootNode?.rightNode) == nil){return 1}else{let deepLeft = self.deepWithThree(rootNode: rootNode?.leftNode)let rightLeft = self.deepWithThree(rootNode: rootNode?.rightNode)return max(deepLeft, rightLeft) + 1}} // 調(diào)用 // 打印 ====== 5let deep = node.deepWithThree(rootNode: node)print("======",deep)

計(jì)算二?樹的寬度OC:?

/*二叉樹寬度的定義：各層節(jié)點(diǎn)數(shù)的最大值！*/ +(NSInteger)WidthOfTree:(ZXTThreeObject * )RootNode{// 根節(jié)點(diǎn)不存在，就返回 0if (!RootNode) {return 0;}NSMutableArray * queeArray = [NSMutableArray array];NSInteger currentWidth = 0;NSInteger maxWidth = 1; // 前面 0 的不存在就 肯定有，至少是 1[queeArray addObject:RootNode]; // 添加根節(jié)點(diǎn)while (queeArray.count > 0) {// 這就是當(dāng)前的節(jié)點(diǎn)的數(shù)目，第一層就只有根節(jié)點(diǎn) 寬度是1// 下一層，按照下面邏輯添加了左右節(jié)點(diǎn)就變成了2currentWidth=queeArray.count;// 遍歷該層，刪除原始數(shù)組中遍歷過(guò)的節(jié)點(diǎn)，添加它下一層的節(jié)點(diǎn)。再循環(huán)遍歷for (NSInteger i=0; i<currentWidth; i++) {ZXTThreeObject * treenode = [queeArray firstObject];[queeArray removeObjectAtIndex:0];if (treenode.leftTreeNode) {[queeArray addObject:treenode.leftTreeNode];}if (treenode.rightTreeNode) {[queeArray addObject:treenode.rightTreeNode];}}// 一層一層的遍歷的時(shí)候去最大值，返回maxWidth = MAX(maxWidth, queeArray.count);}return maxWidth; }

?計(jì)算二?樹的寬度Swift:?

func widthWithThree(rootNode: ZXTreeObject?) -> Int {if ((rootNode) == nil){return 0 }else{var widthDataArray = Array<ZXTreeObject>()widthDataArray.append(rootNode!)var maxWidth = 1var currentWidth = 0;while (widthDataArray.count > 0) {currentWidth = widthDataArray.countfor _ in 0 ..< currentWidth{let node = widthDataArray.first widthDataArray.remove(at: 0)if ((node?.leftNode) != nil) {widthDataArray.append((node?.leftNode)!)} if ((node?.rightNode) != nil){widthDataArray.append((node?.rightNode)!)}}maxWidth = max(currentWidth, widthDataArray.count)}return maxWidth } }

二?樹的先 , 中，后遍歷OC:?

// 調(diào)用代碼 NSMutableArray * dataArray = [NSMutableArray array];[ZXTThreeObject preorderTraversal:rootNode andHandle:^(ZXTThreeObject *threeNode) {NSString * value = [NSString stringWithFormat:@"%ld",threeNode.Value];[dataArray addObject:value];}]; NSLog(@"=======%@",dataArray);// 方法實(shí)現(xiàn)代碼 /**這里所謂的先序，中序，或者后序說(shuō)的都是根節(jié)點(diǎn)的順序，這個(gè)可以看著上面的那張度娘的圖片去好好體會(huì)一下。handle就是一個(gè)回調(diào)，node就是根節(jié)點(diǎn)，這樣就很容易理解記住了。其他的后序和中序就不寫代碼了，交換順序就行了。**/ +(void)preorderTraversal:(ZXTThreeObject *)node andHandle:(void(^)(ZXTThreeObject * threeNode))handle{if (node) {// 根if (handle) {handle(node);}//左[self preorderTraversal:node.leftTreeNode andHandle:handle];//右[self preorderTraversal:node.rightTreeNode andHandle:handle];} }

二?樹的先 , 中，后遍歷Swift:

// 定義一個(gè)隨機(jī)數(shù)組 let sortArray:[Int] = [2,3,7,5,9,4,6,1,8] var dataArray = Array<Int>() let node = ZXTreeObject().CreatTreesWithValues(Values: sortArray) _ = node.preorderTraversal(rootNode:node, handle: {(treeNode) indataArray.append((treeNode?.nodevalue)!) }) print(dataArray)/** 先序遍歷 中序和后序就不寫了，而上面OC的道理是一樣的 **/ // 這是定義的閉包，注意它的位置和我們OC定義Block類似 typealias Handle = (_ root:ZXTreeObject?) -> Void; func preorderTraversal(rootNode: ZXTreeObject?, handle:@escaping Handle) -> Void {if ((rootNode) != nil) {handle(rootNode); self.preorderTraversal(rootNode: rootNode?.leftNode, handle: handle)self.preorderTraversal(rootNode: rootNode?.rightNode, handle: handle)} }

二?樹的層次遍歷OC:

/*層次遍歷層次遍歷，就是一層一層的遍歷，下面的方法用到了隊(duì)列的想法。*/ +(void)CengCiBLTreeNode:(ZXTThreeObject * ) RootNode handle:(void(^)(ZXTThreeObject * treenode))handle{if (RootNode) {NSMutableArray * queeArray=[NSMutableArray array];// 添加了根節(jié)點(diǎn)進(jìn)去[queeArray addObject:RootNode];while (queeArray.count>0) {// 取出數(shù)組中的第一個(gè)元素ZXTThreeObject * rootnode = [queeArray firstObject];if (handle) {// 添加這個(gè)元素的值到數(shù)組中去handle(rootnode);}// 添加完這個(gè)元素的值就把這個(gè)元素刪除了[queeArray removeObjectAtIndex:0];// 這個(gè)節(jié)點(diǎn)要有左節(jié)點(diǎn)的話，就添加左節(jié)點(diǎn)到數(shù)組中去，有右節(jié)點(diǎn)的話就添加右節(jié)點(diǎn)到數(shù)組中去。// 建議一步一步研究這個(gè)添加順序，就可以清晰的看到這個(gè)是一層一層的遍歷到的。if (rootnode.leftTreeNode) {[queeArray addObject:rootnode.leftTreeNode];}if (rootnode.rightTreeNode) {[queeArray addObject:rootnode.rightTreeNode];}}} }

二?樹的層次遍歷Swift:

/******* 調(diào)用/ var array = Array<Int>() _ = node.preorderTraversal(rootNode:node, handle: {(treeNode) inarray.append((treeNode?.nodevalue)!) }) //array ====== [2, 1, 3, 7, 5, 4, 6, 9, 8] print("array ======",array)/******* 層次遍歷/ func CengCiBLTreeNode(rootNode: ZXTreeObject?, handle:@escaping Handle) -> Void {if ((rootNode) != nil) {var dataArray = Array<ZXTreeObject>()dataArray.append(rootNode!)while dataArray.count > 0 {handle(rootNode);dataArray.remove(at: 0)if ((rootNode?.leftNode) != nil) {dataArray.append((rootNode?.leftNode)!)}if ((rootNode?.rightNode) != nil) {dataArray.append((rootNode?.rightNode)!)}}}}

轉(zhuǎn)載于:https://www.cnblogs.com/zhangxiaoxu/p/6484532.html

總結(jié)

以上是生活随笔為你收集整理的用OC和Swift一起说说二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。