深圳网站建设(龙华信科),赣州网站建设方案,建设部网站申请表无法打印,网站怎么做免费推广前言#xff1a; 一#xff1a;在计算机科学中#xff0c;二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”#xff08;left subtree#xff09;和“右子树”#xff08;right subtree#xff09;。二叉树常被用于实现二叉查找树和二叉堆。二#xf…前言 一在计算机科学中二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”left subtree和“右子树”right subtree。二叉树常被用于实现二叉查找树和二叉堆。 二二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)二叉树的子树有左右之分次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点深度为k的二叉树至多有2^k-1个结点对任何一棵二叉树T如果其终端结点数为n_0度为2的结点数为n_2则n_0n_21。 三一棵深度为k且有2^k-1个节点称之为满二叉树深度为k有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中序号为1至n的节点对应时称之为完全二叉树。 四二叉树遍历 先序遍历、中序遍历、后序遍历、层次遍历 、下面答案很精辟 二✘树的OC创建源码 /**创建二叉树param Values 传入数组return return value description*/
(ZXTThreeObject * )CreatTreesWithValues:(NSArray * )Values{__block ZXTThreeObject * rootNode nil;/** 这里顺便提一下这个循环遍历,可能不部分都用的是for循环或者for..in..来循环的 **//** 大家了解一下 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 这个参数其实是一个局部变量不管里面嵌套调用多少次AddTreeNode这个方法这里每一次返回的一直都是它的最原始的根节点这点对创建过程的 理解很重要但如果返回值你写成全局变量就不一样了它返回的就是最后赋给它的值。这里简单说一下局部变量是存储在栈中的全局变量是存储在静态存储区的每存储一个局部变量编译器就会开辟一块栈区域来保存方法第一次传递的node这个变量编译器就开辟了栈区域保存了它的值后面要是有嵌套调用了这个方法编译器就又开辟新的栈区域保存它们的返回值但不会影响第一次保存的值你要调用多次的话第一个保存的值也就是最后一个返回的了这就解释了为什么每次最后的返回值都是 最原始的根节点了
**/
(ZXTThreeObject * )AddTreeNode:(ZXTThreeObject *)node andValue:(int) value{if (!node) {node [[ZXTThreeObject alloc]init];node.Value value;}else if (value node.Value){/**值小于节点的值插入到左节点**/node.leftTreeNode [self AddTreeNode:node.leftTreeNode andValue:value];}else{/**值大于节点的值插入到右节点**/node.rightTreeNode [self AddTreeNode:node.rightTreeNode andValue:value];}return node;
}你可以验证一下它的正确性你在创建左右节点的时候他们打印出来下面的数组提供大家参考 NSArray * array [2,3,7,5,9,4,6,1,8];
/** 上面的数组创建的二叉树应该是这样的 * 代表没有值21 3* 75 94 6 8 ***/
[ZXTThreeObject CreatTreesWithValues:array];二✘树的Swift创建源码 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中函数签名中的下划线的意思是告诉编译器我们在调用函数时第一个参数不需要外带标签这样我们可以按照 Swift 2 中的方式去调用函数,还有这个下划线和参数名之间要有空格必须要有**/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(节点:,node!.nodevalue ?? 0)return node!}
}调用的时候这样 // 定义一个数组
let sortArray:[Int] [2,3,7,5,9,4,6,1,8] _ ZXTreeObject().CreatTreesWithValues(Values: sortArray) 这个结果的话大家可以把上面的打印注释打开自己看看结果是没问题的这里在给大家看看这样一个警告 就这个返回值没有使用的警告这警告有两种办法消除 /*
一就像上面的加 _ 在调用的函数前面
二在函数声明的前面加上 discardableResult 如:
discardableResult func AddTreeNode(node: inout ZXTreeObject?, _ value:Int) - ZXTreeObject {
}*/计算二✘树的深度OC /**树的深度三种情况 一根节点要是不存在就返回0二左节点和右节点都不存在到这里的前提是根节点存在返回1三都存在再递归获取深度返回最大值param node 节点return return value description*/
// 2017-03-03 14:06:15.248 算法OC版本[22755:262170] 数的深度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;}
}计算二✘树的深度Swift // Swift 求二叉树的深度func 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}}
// 调用
// 打印 5let deep node.deepWithThree(rootNode: node)print(,deep)计算二✘树的宽度OC: /*二叉树宽度的定义各层节点数的最大值*/
(NSInteger)WidthOfTree:(ZXTThreeObject * )RootNode{// 根节点不存在就返回 0if (!RootNode) {return 0;}NSMutableArray * queeArray [NSMutableArray array];NSInteger currentWidth 0;NSInteger maxWidth 1; // 前面 0 的不存在就 肯定有至少是 1[queeArray addObject:RootNode]; // 添加根节点while (queeArray.count 0) {// 这就是当前的节点的数目第一层就只有根节点 宽度是1// 下一层按照下面逻辑添加了左右节点就变成了2currentWidthqueeArray.count;// 遍历该层删除原始数组中遍历过的节点添加它下一层的节点。再循环遍历for (NSInteger i0; icurrentWidth; i) {ZXTThreeObject * treenode [queeArray firstObject];[queeArray removeObjectAtIndex:0];if (treenode.leftTreeNode) {[queeArray addObject:treenode.leftTreeNode];}if (treenode.rightTreeNode) {[queeArray addObject:treenode.rightTreeNode];}}// 一层一层的遍历的时候去最大值返回maxWidth MAX(maxWidth, queeArray.count);}return maxWidth;
}计算二✘树的宽度Swift: func widthWithThree(rootNode: ZXTreeObject?) - Int {if ((rootNode) nil){return 0 }else{var widthDataArray ArrayZXTreeObject()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: // 调用代码
NSMutableArray * dataArray [NSMutableArray array];[ZXTThreeObject preorderTraversal:rootNode andHandle:^(ZXTThreeObject *threeNode) {NSString * value [NSString stringWithFormat:%ld,threeNode.Value];[dataArray addObject:value];}];
NSLog(%,dataArray);// 方法实现代码
/**这里所谓的先序中序或者后序说的都是根节点的顺序这个可以看着上面的那张度娘的图片去好好体会一下。handle就是一个回调node就是根节点这样就很容易理解记住了。其他的后序和中序就不写代码了交换顺序就行了。**/
(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: // 定义一个随机数组
let sortArray:[Int] [2,3,7,5,9,4,6,1,8]
var dataArray ArrayInt()
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: /*层次遍历层次遍历就是一层一层的遍历下面的方法用到了队列的想法。*/
(void)CengCiBLTreeNode:(ZXTThreeObject * ) RootNode handle:(void(^)(ZXTThreeObject * treenode))handle{if (RootNode) {NSMutableArray * queeArray[NSMutableArray array];// 添加了根节点进去[queeArray addObject:RootNode];while (queeArray.count0) {// 取出数组中的第一个元素ZXTThreeObject * rootnode [queeArray firstObject];if (handle) {// 添加这个元素的值到数组中去handle(rootnode);}// 添加完这个元素的值就把这个元素删除了[queeArray removeObjectAtIndex:0];// 这个节点要有左节点的话就添加左节点到数组中去有右节点的话就添加右节点到数组中去。// 建议一步一步研究这个添加顺序就可以清晰的看到这个是一层一层的遍历到的。if (rootnode.leftTreeNode) {[queeArray addObject:rootnode.leftTreeNode];}if (rootnode.rightTreeNode) {[queeArray addObject:rootnode.rightTreeNode];}}}
}二✘树的层次遍历Swift: /******* 调用/
var array ArrayInt()
_ 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 ArrayZXTreeObject()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)!)}}}} 转载于:https://www.cnblogs.com/zhangxiaoxu/p/6484532.html
