学习Binary search tree

笔记

1. 貌似我是不需要传入一个结点的，因为那个结点直接就引用了这个函数。
2. 每一次调用该对象的node，应该是不需要用this->来指向的，因为默认是对象的node
3. 对于transplate 声明为bst，但是我传入的是两个地址....应该是有问题吧
4. 我感觉对于问题3,我没有好好的理清楚里面每个结点，究竟是一个对象还是....
5. 对于类里面的一个函数，默认是调用里面的元素
6. 对于每一个使用了模板的类型，在声明使用的时候，都要加上

脑子有洞！！！什么都变成了类里面的函数？？？！！！

继续填坑
1. 面向对象，说的是面向一个类中同一样的不同对象使用相同的方法去实现一个目的。[好像这样理解并没有什么问题。
2. 从这个角度出发的话，对于一个二叉查找树，

初步构想的功能：

貌似这个link在分清结点类和二叉树类这方面比较清晰。
因为主要是分好两个类各自的职能，结点类负责什么，二叉树类负责什么。
可能这就是所谓的代码设计的重要性啊

• 明白树类适合做什么，明白结点类又适合做什么

失败文件：见link

成功：BSTreeDone.cpp

#include <iostream>
using namespace std;
template <typename T>
class Node{
public:
  Node();
  void DeleteNodesRecursion();
  T key;
  Node *left;
  Node *right;
  Node *parent;
  Node<T>* search(T num);
  Node<T>* minimun();
  Node<T>* maximun();
  void print();
private:
};
template <typename T>
class BSTree {
public:
  BSTree():root(nullptr){};
  ~BSTree();
  void insert(T num);
  void deleteNode(T num);
  void inOrder() ;
private:
  Node<T> *root;
  void transplant(Node<T> *x,Node<T> *y);
};
template <typename T>
Node<T>::Node() {
  key = 0;
  left = nullptr;
  right = nullptr;
}
template <typename T>
void Node<T>::DeleteNodesRecursion() {
  if (this) {
    Node<T> *l = this->left;
    Node<T> *r = this->right;
    delete this;
    l->DeleteNodesRecursion();
    r->DeleteNodesRecursion();
  }
}
template <typename T>
Node<T>* Node<T>::search(T num) {
  if (this == NULL || this->key == num ) {
    return this;
  }
  if (this->key > num) {
    return left->search(num);
  }
  else {
    return right->search(num);
  }
}
template <typename T>
Node<T>* Node<T>::minimun() {
  Node<T> *temp;
  temp = this;
  while (temp->left != NULL) {
    temp = (temp->left);
  }
  return temp;
}
template <typename T>
Node<T>* Node<T>::maximun() {
  while (this->right) {
    this = this->right;
  }
  return this;
}
template <typename T>
void Node<T>::print() {
  if(left != NULL)left->print();
  cout<<key;
  if(right != NULL)right->print();
}
template <typename T>
BSTree<T>::~BSTree() {
  root->DeleteNodesRecursion();
}
template <typename T>
void BSTree<T>::insert(T num) {
  Node<T> *z = new Node<T>;
  z->key = num;
  Node<T> *y = new Node<T>;
  y = nullptr;
  Node<T> *x = root;
  while (x != NULL) {
    y = x;
    if (x->key > z->key) {
      x= x->left;
    }
    else x = x->right;
  }
  z->parent = y;
  if (y == NULL) {
    root = z;
  }
  else if (y->key > z->key) {
    y->left = z;
  }
  else y->right = z;
}
template <typename T>
void BSTree<T>::deleteNode(T num) {
  Node<T> *n = root->search(num);
  if (n->left == NULL) {
    transplant(n,n->right);
  }
  else if (n->right ==NULL ) {
    transplant(n,n->left);
  }
  else {
    Node<T> *min;
    min = n->right->minimun();
    if (min->parent != n) {
      transplant(min,min->right);
      min->right = n->right;
      min->right->parent = min;
    }
    transplant(n,min);
    min->left = n->left;
    min->left->parent = min;
  }
}
template <typename T>
void BSTree<T>::inOrder() {
  root->print();
}
template <typename T>
void BSTree<T>::transplant(Node<T> *x ,Node<T> *y) {
  if (x->parent == NULL) {
    x = y;
  }
  else if (x->parent->left == x) {
    x->parent->left = y;
  }
  else x->parent->right = y;
  if (y != NULL) {
    y->parent = x->parent;
  }
}
int main() {
  BSTree<int> tree;
  tree.insert(2);
  tree.insert(4);
  tree.insert(1);
  tree.insert(3);
  tree.inOrder();
  tree.deleteNode(4);
  tree.insert(5);
  tree.inOrder();
  return 0;
}