用OC和Swift一起说说二叉树
前言：
一：在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。
三：一棵深度为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];
/**
上面的数组创建的二叉树应该是这样的 * 代表没有值
2
1 3
* 7
5 9
4 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
}
}
// 调用
// 打印 ====== 5
let deep = node.deepWithThree(rootNode: node)
print("======",deep)计算二✘树的宽度OC:
/*
二叉树宽度的定义：各层节点数的最大值！
*/
+(NSInteger)WidthOfTree:(ZXTThreeObject * )RootNode{
// 根节点不存在，就返回 0
if (!RootNode) {
return 0;
}
NSMutableArray * queeArray = [NSMutableArray array];
NSInteger currentWidth = 0;
NSInteger maxWidth = 1; // 前面 0 的不存在就 肯定有，至少是 1
[queeArray addObject:RootNode]; // 添加根节点
while (queeArray.count > 0) {
// 这就是当前的节点的数目，第一层就只有根节点 宽度是1
// 下一层，按照下面逻辑添加了左右节点就变成了2
currentWidth=queeArray.count;
// 遍历该层，删除原始数组中遍历过的节点，添加它下一层的节点。再循环遍历
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];
}
}
// 一层一层的遍历的时候去最大值，返回
maxWidth = MAX(maxWidth, queeArray.count);
}
return maxWidth;
}计算二✘树的宽度Swift:
func widthWithThree(rootNode: ZXTreeObject?) -> Int {
if ((rootNode) == nil){
return 0
}else{
var widthDataArray = Array<ZXTreeObject>()
widthDataArray.append(rootNode!)
var maxWidth = 1
var currentWidth = 0;
while (widthDataArray.count > 0) {
currentWidth = widthDataArray.count
for _ 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 = Array<Int>()
let node = ZXTreeObject().CreatTreesWithValues(Values: sortArray)
_ = node.preorderTraversal(rootNode:node, handle: {(treeNode) in
dataArray.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.count>0) {
// 取出数组中的第一个元素
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 = Array<Int>()
_ = node.preorderTraversal(rootNode:node, handle: {(treeNode) in
array.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)!)
}
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-03-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
