二叉搜索树(Binary Search Tree, BST)是特殊的二叉树,它满足如下性质:

  • 左小右大:对于BST的每一个节点,它左子树节点的值都小于根节点的值,右子树节点的值都大于根节点的值。
  • 递归定义:对于BST的每一个节点,它的左子树和右子树也都是BST。
  • 中序升序:BST的中序遍历结果是升序的。

直接基于BST的数据结构有AVL树、红黑树等,拥有自平衡性质;还有B+树,线段树等结构都是基于BST的思想来设计的。因此学好BST也很重要。

阅读全文 »

二叉树不仅仅是数组/链表这类基本数据结构和图这类高级数据结构中间的过滤,更代表着递归的思维模式,能够帮助我们更好地掌握计算机思维,得心应手地借助计算机解决问题。

阅读全文 »
0%