二叉搜索树心得

什么是二叉树?

  1. 二叉树像链表一样,属于动态数据结构
  2. 二叉树的特点:
    1. 二叉树具有唯一的根节点
    2. 二叉树的每一个节点最多只有两个孩子
  3. 二叉树具有天然的递归结构
    1. 每一个节点的左、右子树也是一个二叉树
  4. 二叉树不一定是满的

二叉树的节点

//节点
type Node struct{
    value  int      //节点值
    Node   *left        //左孩子
    Node   *right   //右孩子
}

//二叉树
type BST struct{
    Node root   //根节点
    int  size   //二叉树的节点数(大小)
}

为什么要发明这种树结构?

  1. 树结构本身是一种天然的组织结构。
  2. 树结构具有高效性。

二分搜索树的应用举例

  • 平衡二叉树
  • AVL
  • 红黑树
  • 堆、并查集
  • 线段树
  • Trie(字典树、前缀树)(多叉树)(对字符串的操作)
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注