二分搜索树节点的插入学习笔记

什么是二分搜索树？

二分搜索树（Binary Search Tree，BST）是一种数据结构，它是一个有序的树形结构。每个节点最多只有左右两个子节点，且左子节点小于父节点，右子节点大于父节点。

二分搜索树的插入操作

二分搜索树的插入操作比较简单，在二分搜索树中插入一个节点，需要执行以下步骤：

1. 如果树为空，则将插入的节点作为根节点。
2. 如果待插入节点的值小于当前节点的值，则将待插入节点插入当前节点的左子树中。
3. 如果待插入节点的值大于当前节点的值，则将待插入节点插入当前节点的右子树中。

二分搜索树节点插入示例

假设我们有一个空的二分搜索树，要向其中插入以下节点：8, 10, 3, 6, 7, 14, 1, 13。

首先插入节点 8，它成为了根节点：

Copy Code
       8

接下来插入节点 10，由于它大于根节点 8，所以它应该作为根节点的右子节点：

Copy Code
       8
        \
        10

插入节点 3，由于它小于根节点 8，所以它应该作为根节点的左子节点：

Copy Code
       8
      /
     3
      \
       10

插入节点 6，由于它大于节点 3，小于节点 8，所以它应该作为节点 3 的右子节点：

Copy Code
       8
      /
     3
      \
       6
        \
         10

插入节点 7，由于它大于节点 6，小于节点 8，所以它应该作为节点 6 的右子节点：

Copy Code
       8
      /
     3
      \
       6
        \
         7
          \
           10

插入节点 14，由于它大于节点 10，所以它应该作为节点 10 的右子节点：

Copy Code
       8
      / \
     3   10
      \    \
       6    14
        \
         7

插入节点 1，由于它小于节点 3，所以它应该作为节点 3 的左子节点：

Copy Code
        8
      /   \
     3     10
    / \      \
   1   6     14
      / \
     7   8

插入节点 13，由于它大于节点 10，小于节点 14，所以它应该作为节点 14 的左子节点：

Copy Code
        8
      /   \
     3     10
    / \      \
   1   6     14
      / \    /
     7   8  13