首页 > 代码库 > 用OC和Swift一起说说二叉树

用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 = http://www.mamicode.com/[obj intValue];>

你可以验证一下它的正确性,你在创建左右节点的时候他们打印出来,下面的数组提供大家参考:

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 = http://www.mamicode.com/value"----- 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 = http://www.mamicode.com/[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)!)
                }
            }
        }
    }

用OC和Swift一起说说二叉树