一、二叉搜索树-Binary Search Tree

它是二叉树中的一种，是使用最广泛的一种，英文缩写为BST
又称之为：二叉查找树、二叉排序树

二、特点

1.任意一个节点的值都大于其左子树所有节点的值
2.任意一个节点的值都小于其右子树所有节点的值
3.它的左右子树也是一棵二叉搜索树

二叉搜索树存储的元素必须具备可比较性
如：int 、double等
自定义类型需指定比较方式
不允许为null

三、二叉树的遍历

1.前序遍历：先访问根结点
2.中序遍历：中间访问根结点
3.后序遍历：最后访问根结点
4.层序遍历：

前序遍历 Preorder Traversal

首先访问根结点，再访问左子树，然后再访问右子树。子树将以同样的规则访问。

前序遍历顺序.png

通过递归的方式实现

// 前序遍历
-(void)preorderTraversal{
    [self preorderTraversal:self.root];
}

-(void)preorderTraversal:(Node *)node{
    
    // 1.node 为空的时候，退出
    if (node == nil) return;
    // 2.前序遍历，首先访问根结点
    NSLog(@"%@",node.element);
    // 3.再访问左结点
    [self preorderTraversal:node.left];// 递归，进入步骤1，遍历子结点
    // 4.在访问右结点
    [self preorderTraversal:node.right];// 同样进入步骤1，遍历子结点
    
}

中序遍历

首先遍历左子树，然后访问根结点，最后遍历右子树

中序遍历.png

中序遍历
如果先访问左子树，在访问根结点，最后访问右子树的顺序，进行遍历，那么遍历的结果是升序。
如果先访问右子树，再访问根结点，最后访问左子树的顺序，进行遍历，那么遍历的结果过升序。

-(void)inorderTraversal{
    [self inorderTraversal:self.root];
}
-(void)inorderTraversal:(Node *)node{
    if (node == nil) return;
    [self inorderTraversal:node.left];
    NSLog(@"%@",node.element);
    [self inorderTraversal:node.right];
}

后序遍历

首先访问左子树，然后访问右子树，最后访问根结点

后序遍历.png

-(void)postorderTraversal:(Node *)node{
    if (node == nil) return;
    [self postorderTraversal:node.left];
    [self postorderTraversal:node.right];
    NSLog(@"%@",node.element);
}

层序遍历

从上到下，从左到右依次访问每一个结点

层序遍历.png

1.利用队列
首先访问根结点，将根结点入队
然后依次判断是否具有左右子结点，如果具有，将子结点入队
将根结点出队
循环以上步骤，直到队列为空
2.利用数组
首先访问根结点，将根结点插入数组中
然后依次判断是否具有左右子结点，如果具有，插入子结点
然后移除根结点
循环以上步骤，直到数组为空


/// 层序遍历
-(void)levelOrderTraversal{
    
    if(self.root == nil) return;
    
    /// 1.先将根结点入队
    NSMutableArray *mArray = [NSMutableArray array];
    [mArray addObject:self.root];
    
    while (mArray.count != 0) {
        Node *node = mArray.firstObject;
        [mArray removeObjectAtIndex:0];
        // 2.访问结点
        NSLog(@"%@",node.element);
        // 3.查看是否具有左右子结点
        if (node.left != nil) {
            [mArray addObject:node.left];
        }
        if (node.right != nil) {
            [mArray addObject:node.right];
        }
    }
}

练习-翻转二叉树

image.png

输入: [4,2,7,1,3,6,9]
输出 : [4,7,2,9,6,3,1]
前序遍历翻转二叉树

-(Node *)inverTree:(Node*)root{
    if (root == nil) {
        return nil;
    }
    Node *tempNode = root.left;
    root.left = root.right;
    root.right = tempNode;
    
    [self inverTree:root.left];
    [self inverTree:root.right];
    
    return  root;
}

后序遍历翻转二叉树

-(Node *)inverTree2:(Node *)root{
    if (root == nil) {
        return nil;
    }
    [self inverTree2:root.left];
    [self inverTree2:root.right];
    Node *tempNode = root.left;
    root.left = root.right;
    root.right = tempNode;

    return root;
}

中序遍历翻转二叉树

-(Node *)inverTree3:(Node *)root{
    if (root == nil) {
        return nil;
    }
    
    [self inverTree3:root.left];
    Node *tempNode = root.left;
    root.left = root.right;
    root.right = tempNode;
    [self inverTree3:root.left];
    return  root;
}

层序遍历翻转二叉树

-(Node *)inverTree4:(Node *)root{
    if (root == nil) {
        return nil;
    }
    
    NSMutableArray *queue = [NSMutableArray array];
    [queue addObject:root];
    while (queue.count != 0) {
        
        Node *node = queue.firstObject;
        Node *tempNode = node.left;
        node.left = node.right;
        node.right = tempNode;
        
        [queue removeObjectAtIndex:0];
        
        if (node.left != nil) {
            [queue addObject:node.left];
        }
        if (node.right != nil) {
            [queue addObject:node.right];
        }
    }
    return root;
    
}