二分搜索树节点的插入

一. 定义二分搜索树

首先定义一颗二分搜索树，C++代码如下：

#include <iostream>
#include <queue>
#include <cassert>
using namespace std;

//套用模板函数
template <typename Key, typename Value>
class BST {
private:
    //构造节点Node
  struct Node {
        Key key;
  Value value;
  Node *left;     //左孩子指针
  Node *right;    //右孩子指针

  Node(Key key, Value value) {
         this->key = key;
         this->value = value;
  //初始值为空
  this->left = this->right = NULL;
  }
        Node(Node *node){
            this->key = node->key;
            this->value = node->value;
            this->left = node->left;
            this->right = node->right;
  }
    };

  //根节点
  Node *root;
  //节点数量
  int count;

public:
  //构造函数
    BST() {
        //初始值为空
  root = NULL;
  count = 0;
  }

//析构函数
    ~BST() {
        distroy(root);
  }

二. 插入节点

接下来我们开始对二分搜索树中进行插入节点，如图：
我们向树中插入键值为60的节点

1. 首先60会和整个数的根节点比较，显然60 > 41 所以将60，继续和41节点的右孩子进行比较：
   
2. 此时 60 > 58 ，所以将60 继续和58节点的右孩子节点进行比较，但58节点的右孩子为空，这时 60 节点就插入为58节点的右孩子：
   

下面我们再向二分搜索树中插入键值为28的节点：

1. 节点28和二分搜索树的根节点41比较，28 < 41 ,将28继续和41节点的左孩子节点比较：
   
2. 此时28 > 22, 再将28和22节点的左孩子比较：
   
3. 28 < 33,继续将节点28和33节点的右孩子比较，但此时33的左孩子为空，28节点就插入为节点33的左孩子：
   

如果出现插入的节点和二分搜索树中的节点重合的情况，依然是同理，只需要将原来节点覆盖即可

三. 代码实现

新节点的插入操作的逻辑明白了，下面我们开始带着这种逻辑进入代码的实现(使用递归版本，c++实现）：
我们在public中定义函数：

//插入操作
void insert(Key key, Value value) {
    //向根节点中插入key， value
  root = insert(root, key, value);
}

接下来我们在private中写：

//插入操作
//向以node为根节点的二分搜索树中，插入节点（key，value),使用递归算法
//返回插入新节点后的二分搜索树的根
Node *insert(Node *node, Key key, Value value) {
    if (node == NULL) {
        count++;
        return new Node(key, value);
  }

    if (key == node->key) {
        node->value = value;
  } 
    else if (key > node->key) {
        node->right = insert(node->right, key, value);
  } 
    else //key < node->key
  node->left = insert(node->left, key, value);
}

本作品采用《CC 协议》，转载必须注明作者和本文链接