二叉搜索树

• content
  {:toc}

  1.介绍

2.为什么使用树形结构

为什么使用树形结构。因为高效

1. 二分搜索树
2. 平衡二叉树：avl；红黑树
3. 堆；并查集
4. 线段树；trie （字典树， 前端树）

3.二分搜索树

• 二叉树

  • 和链表一样，动态数据结构

  • class Node {
        E e;
        Node left; //左孩子
        Node right; //右孩子
    }
    <!--0-->
    
        另一种写法:
    
        <!--1-->
    
        **思考: 链表递归实现**
    
    - 二叉树查询
    
      <!--2-->
    
    - 数据结构遍历
    
      遍历:把所有节点都访问一遍
    
      访问的原因和业务有关
    
      在线下结构下,遍历及其容易
    
      树形结构遍历
    
    
    

前序遍历: 先访问节点,再访问左右子树;最自然的遍历方式;最常用的遍历方式
中序遍历: 打印出来,就是一个排序好的顺序,自左到右
后序遍历:

在哪里打印

非递归的实现,用了个 栈 去实现, 

​    深度优先遍历 : 用栈
​    广度优先遍历: 用队列

广度优先遍历:使用在查询身上,使用在获取解的身上

​    更快找到问题的解

​    常用于算法设计中-最短路径

深度优先遍历:一下子就进入到了,深度很深的地方,可能解在比较浅的地方

草稿：

1. 二分搜索树是二叉树怎么 赋值呢,怎么产生二叉树的值