二叉树的排序原理

涉及到算法就有点烧脑了，今天分享一下二叉树排序的理解！
二叉树排序的基本原理：
使用第一个元素作为根节点，如果之后的元素比第一个小，则放到左子树，否则放到右子树，之后按中序遍历。
时间复杂度：nlog2(n)
空间复杂度：中序遍历时，需要构建栈，为logn.
二叉搜索树的性质：
（1）每个结点都有一个作为搜索依据的关键码（key）也就是数据域，所有节点的关键码互不一样。
（2）左子树（如果存在）上的所有结点的关键码都小于根结点的关键码。
（3）右子树（如果存在）上的所有结点的关键码都大于根结点的关键码。
（4）左右子树也是二叉搜索树。
（5）缺点在于 如果key值趋向于升序或者降序，那么复杂度就会升为o(n)级别
好了原理大概介绍了一下，废话不多说撸代码

template<class K ,class V>
struct NodeTree{
    NodeTree(K key,V value){
        this->key=key;
        this->value=value;
        this->left=NULL;
        this->right=NULL;
    }
    K key=NULL;
    V value=NULL;
    NodeTree<K,V>*left=NULL;
    NodeTree<K,V>*right=NULL;
};

template<class K ,class V>
class BST {
    NodeTree<K,V>* root;
    int count;


public:
    BST();
    ~BST();

public:
    static NodeTree<K,V>* addNode(NodeTree<K,V>* node,K key,V value);
    void put(K key,V value);
    int getSize();
    void remove(K key);
    NodeTree<K,V>* removeNode(NodeTree<K,V>* pNode,K key);
    bool contain(K key);
    bool containNode(NodeTree<K,V>* node,K key);
    void centerOrder();
    V getValueByKey(NodeTree<K, V> *node,K key);
    V getValueByKey(K key);
    void treeOrder(NodeTree<K,V>* node);
    NodeTree<K,V>* deleteLeftMax(NodeTree<K,V>* node);
    NodeTree<K,V>* getLeftMax(NodeTree<K,V>* node);
};

template<class K, class V>
BST<K, V>::BST() {
    int count=0;
    root= NULL;
}

template<class K, class V>
NodeTree<K, V> *BST<K, V>::addNode(NodeTree<K, V> *node, K key, V value) {
    if (node==NULL){
        return new NodeTree<K, V> (key,value);
    }
    if(node->key>key){
            node->left = addNode(node->left, key, value);
    } else if (node->key<key){
        node->right=addNode(node->right,key,value);
    } else{
        node->value=value;
    }
    return node;
}

template<class K, class V>
void BST<K, V>::put(K key, V value) {
 root=addNode(root,key,value);
 count++;
}

template<class K, class V>
int BST<K, V>::getSize() {
    return count;
}

template<class K, class V>
void BST<K, V>::remove(K key) {
  root=removeNode(root,key);
}

template<class K, class V>
bool BST<K, V>::contain(K key) {
    return containNode(root,key);
}

//进行中序排序 就是升序排序（二叉树中序排序就是升序排序）
template<class K, class V>
void BST<K, V>::treeOrder(NodeTree<K, V> *node) {
    if (node==NULL){
        return;
    }
    treeOrder(node->left);
    __android_log_print(ANDROID_LOG_ERROR,"TAG","%d--%d",node->key,node->value);

    treeOrder(node->right);
}

template<class K, class V>
void BST<K, V>::centerOrder() {
    treeOrder(root);
}

template<class K, class V>
V BST<K, V>::getValueByKey(NodeTree<K, V> *node,K key) {
 if(node==NULL){
     throw "not find value";
 }
  if(node->key==key){
      return node->value;
  }else if(node->key<key){
      return getValueByKey(node->right, key);
  } else{
      return getValueByKey(node->left,key);
  }
}

template<class K, class V>
V BST<K, V>::getValueByKey(K key)  {
    return getValueByKey(root,key);
}

template<class K, class V>
bool BST<K, V>::containNode(NodeTree<K, V> *node, K key) {
    if (node==NULL){
        return nullptr;

    }
    if (node->key==key){
        return node->value;
    } else if(key>node->key){
        return containNode(node->right,key);
    } else{
        return containNode(node->left,key);
    }

}

template<class K, class V>
NodeTree<K, V> *BST<K, V>::deleteLeftMax(NodeTree<K, V> *pTree) {
    if (pTree->right== nullptr){
        NodeTree<K, V> *left=pTree->left;
        delete  pTree;
        count--;
        return left;
    }

    pTree->right= deleteLeftMax(pTree->right);
    return pTree;
}

//一直往右节点找
template<class K, class V>
NodeTree<K, V> *BST<K, V>::getLeftMax(NodeTree<K, V> *pTree) {
    if (pTree== nullptr){
        return nullptr;
    }
    if (pTree->right== nullptr){
        return  pTree;
    }
    return getLeftMax(pTree->right);
}

template<class K, class V>
NodeTree<K, V> *BST<K, V>::removeNode(NodeTree<K,V>* pNode,K key) {
   if(pNode== nullptr){
       return nullptr;
   }
   if (pNode->key>key){
       pNode->left=removeNode(pNode->left,key);
   } else if (pNode->key<key){
       pNode->right=removeNode(pNode->right,key);
   } else{
       count--;
       if(pNode->left== nullptr && pNode->right== nullptr){
           delete(pNode);
           return nullptr;
       } else if (pNode->left== nullptr){
           NodeTree<K,V>* right =pNode->right;
           delete(pNode);
           return right;
       } else if(pNode->right== nullptr){
           NodeTree<K,V>* left =pNode->left;
           delete(pNode);
           return left;
       } else{
           //前区后及 找到左边最大值
           NodeTree<K,V>* max= getLeftMax(pNode->left);
           max->left=deleteLeftMax(pNode->left);
           max->right=pNode->right;
           count++;
           delete(pNode);
           return max;
       }
   }

    return pNode;
}

里面比较复杂的就是删除方法了，删除数据得考虑到二叉树结构位置的调整得分情况递归调整有点烧脑。