本次实现为平衡二叉树做基础，如有问题，欢迎指出！
编译环境：GCC 7.3、vs 2005
#ifndef __BTREE_H__
#define __BTREE_H__#if __cplusplus >= 201103L
#include <type_traits> // std::forward、std::move
#include <initializer_list>
#endif#if __cplusplus >= 201103L
#define null nullptr
#else
#define null NULL
#endif template<typename __Type>
static void swap(__Type &a, __Type &b)
{__Type tmp = a;a = b;b = tmp;
}// 二叉树结点
template<typename _Tp>
struct BTreeNode
{typedef BTreeNode self;typedef _Tp value_type;typedef _Tp * pointer;typedef _Tp & reference;typedef unsigned long size_type;// 前置保证不为空BTreeNode(pointer v, self *left = null, self *right = null, self *parent = null, size_type s = 0, size_type d = 1): _M_value(v), _M_left(left), _M_right(right), _M_parent(parent), _M_child_size(s), _M_depth(d) { }// 前置保证不为空BTreeNode(self *node, self *parent = null): _M_value(null), _M_left(null), _M_right(null), _M_parent(parent), _M_child_size(0), _M_depth(1) {_M_child_size = node->child_size();_M_depth = node->depth();_M_value = new value_type(node->value());if(null != node->left_child()){ _M_left = new BTreeNode(node->left_child(), this); }if(null != node->right_child()){ _M_right = new BTreeNode(node->right_child(), this); }}~BTreeNode(){ delete _M_value;if(null != _M_left){ delete _M_left; }if(null != _M_right){ delete _M_right; } }void add_child_number(size_type size){_M_child_size += size;if(null != _M_parent){ _M_parent->add_child_number(size); }}void update_size(){_M_child_size = 0;_M_depth = 1;if(null != _M_left){ _M_depth = _M_left->_M_depth + 1; _M_child_size += _M_left->child_size() + 1;}if(null != _M_right){_M_child_size += _M_right->child_size() + 1;size_type tmp = _M_right->_M_depth + 1;_M_depth = tmp > _M_depth ? tmp : _M_depth;}if(null != _M_parent){ _M_parent->update_size(); }}void append_node(self *node){if(null != node){ node->_M_parent = this; }update_size();return node;}self* set_left(self *left){ _M_child_size -= null == _M_left ? 0 : (_M_left->child_size() + 1);_M_left = left;append_node(left);return left;}self* set_right(self *right){ _M_child_size -= null == _M_right ? 0 : (_M_right->child_size() + 1);_M_right = right;append_node(right); return right;}size_type child_size() const { return _M_child_size; }size_type depth() const { return _M_depth; }pointer value() { return _M_value; }self* left_child(){ return _M_left; }self* right_child(){ return _M_right; }self* parent() { return _M_parent; }void swap(BTreeNode *node){ ::swap<pointer>(node->_M_value, _M_value);::swap<self*>(node->_M_left, _M_left);::swap<self*>(node->_M_right, _M_right);::swap<self*>(node->_M_parent, _M_parent);::swap<size_type>(node->_M_child_size, _M_child_size);::swap<size_type>(node->_M_depth, _M_depth);}pointer _M_value;self *_M_left;self *_M_right;self *_M_parent;size_type _M_child_size;size_type _M_depth;// 深度，包括自己
};// 普通二叉树
template<typename _Tp, typename _Node = BTreeNode<_Tp>>
class BinaryTree
{
public:typedef _Tp value_type;typedef _Tp & reference;typedef const _Tp & const_reference;typedef unsigned long size_type;typedef _Node node_type;#if __cplusplus >= 201103Ltypedef _Tp && rvalue_reference;
#endifpublic:BinaryTree(): _M_root(null) { }BinaryTree(const BinaryTree &bt): _M_root(null) { operator=(bt); }#if __cplusplus >= 201103LBinaryTree(BinaryTree &&bt): _M_root(null) { swap(bt._M_root, _M_root); }
#endif~BinaryTree() { clear(); }void swap(BinaryTree &bt){ ::swap<node_type*>(bt._M_root, _M_root); }size_type size() const { return null == _M_root ? 0 : (_M_root->child_size() + 1); }size_type depth() const { return null == _M_root ? 0 : _M_root->depth(); }BinaryTree& operator=(const BinaryTree &bt){clear();if(null != bt._M_root){ _M_root = new node_type(bt._M_root); }}void clear(){if(null != _M_root){ delete _M_root; }}node_type* root(){ return _M_root; }/* 需要移除的结点* 返回值：* 1. 如果node的左子树深度 大于 右子树深度，则返回node的左子树最右边的结点* 2. 如果node的左子树深度 不大于 右子树深度，则返回node的右子树最左边的结点*/node_type* erase(node_type *node);public:node_type* right_rotate(node_type *node);// 以node为中心，进行右转操作node_type* left_rotate(node_type *node);// 以node为中心，进行左转操作static node_type* left_child_under(node_type *node);// 最左边的结点static node_type* right_child_under(node_type *node);// 最右边的结点static node_type* left_leaves(node_type *node);// 最左边的叶子结点static node_type* right_leaves(node_type *node);// 最右边的叶子结点static node_type* former_next(node_type *node);// 获取前序遍历的下一个结点static node_type* middle_next(node_type *node);// 获取中序遍历的下一个结点static node_type* after_next(node_type *node);// 获取后续遍历的下一个结点static node_type* former_previous(node_type *node);// 获取前序遍历的上一个结点static node_type* middle_previous(node_type *node);// 获取中序遍历的上一个结点static node_type* after_previous(node_type *node);// 获取后续遍历的上一个结点private:node_type *_M_root;
};//---------------------***************---------------------//
//---------------------***************---------------------//
//---------------------***************---------------------//template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::right_rotate(node_type *node)
{node_type *left_node = node->left_child();if(null == left_node) { return null; }node_type *original_parent = node->parent();node_type *left_node_right_child = left_node->right_child();if(null != original_parent){if(original_parent->right_child() == node){ original_parent->_M_right = left_node; }else{ original_parent->_M_left = left_node; }}node->_M_parent = null;left_node->_M_parent = null;size_type left_node_right_child_size = left_node_right_child == null ? 0 : (left_node_right_child->child_size() + 1);node->add_child_number(- (left_node->child_size() + 1));node->add_child_number(left_node_right_child_size);left_node->add_child_number(-left_node_right_child_size);left_node->add_child_number(node->child_size() + 1);node->_M_parent = left_node;node->_M_left = left_node_right_child;left_node->_M_right = node;left_node->_M_parent = original_parent;if(left_node_right_child != null){ left_node_right_child->_M_parent = node; }if(node == root()){ _M_root = left_node; }node->update_size();return left_node;
}template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::left_rotate(node_type *node)
{node_type *right_node = node->right_child();if(right_node == null){ return null; }node_type *original_parent = node->parent();node_type *right_node_left_child = right_node->left_child();if(null != original_parent){if(original_parent->right_child() == node){ original_parent->_M_right = right_node; }else{ original_parent->_M_left = right_node; }}node->_M_parent = null;right_node->_M_parent = null;size_type left_node_right_child_size = right_node_left_child == null ? 0 : (right_node_left_child->child_size() + 1);node->add_child_number(- (right_node->child_size() + 1));node->add_child_number(left_node_right_child_size);right_node->add_child_number(-left_node_right_child_size);right_node->add_child_number(node->child_size() + 1);node->_M_parent = right_node;node->_M_right = right_node_left_child;right_node->_M_left = node;right_node->_M_parent = original_parent;if(right_node_left_child != null){ right_node_left_child->_M_parent = node; }if(node == root()){ _M_root = right_node; }node->update_size();return right_node;
}//-----------------------------------------------------------//
//----------------------静态方法类外实现----------------------//
//-----------------------------------------------------------//template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::left_child_under(node_type *node)
{while(node != null && null != node->left_child()){ node = node->left_child(); }return node;
}template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::right_child_under(node_type *node)
{while(node != null && null != node->right_child()){ node = node->right_child(); }return node;
}template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::left_leaves(node_type *node)
{node = left_child_under(node);while(null != node->right_child()){ node = left_child_under(node->right_child()); }return node;
}template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::right_leaves(node_type *node)
{node = right_child_under(node);while(null != node->left_child()){ node = right_child_under(node->left_child()); }return node;
}template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::former_next(node_type *node)
{if(null != node->left_child()){ return node->left_child(); }if(null != node->right_child()){ return node->right_child(); }node_type *temp = node;node = node->parent();while(node != null && (node->right_child() == temp || null == node->right_child())){temp = node;node = node->parent();}return node->right_child();
}template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::middle_next(node_type *node)
{if(null != node->right_child()){ return left_child_under(node->right_child()); }if(node != node->parent()->right_child()){ return node->parent(); }node_type *temp = node;node = node->parent();while(null != node && node->right_child() == temp){temp = node;node = node->parent();}return node;
}template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::after_next(node_type *node)
{if(node == node->parent()->left_child()){if(null == node->parent()->right_child()){ return node->parent(); }return left_leaves(node->parent()->right_child());}if(node == node->parent()->right_child()){ return node->parent(); }return null;
}template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::former_previous(node_type *node)
{if(node == node->parent()->left_child()){ return node->parent(); }if(node == node->parent()->right_child()){node = node->parent();if(null != node->left_child()){ return right_leaves(node->left_child()); }return node;}return null;
}template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::middle_previous(node_type *node)
{if(null != node->left_child()){ return right_child_under(node->left_child()); }if(node == node->parent()->right_child()){ return node->parent(); }while(null != node && node == node->parent()->left_child()){ node = node->parent(); }return node->parent();
}template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::after_previous(node_type *node)
{if(null != node->right_child()){ return node->right_child(); }if(node->parent()->right_child() == node){node = node->parent();while(node != null && null != node->left_child()){ node = node->parent(); }return node->left_child();}if(null != node->left_child()){ return node->left_child(); }while(null != node && node->parent()->left_child() == node){ node = node->parent(); }node = node->parent();while(node != null && null == node->left_child()){ node = node->parent(); }return node->left_child();
}//---------------------***************---------------------//
//---------------------***************---------------------//
//---------------------***************---------------------//
template<typename _Tp, typename _Node>
typename BinaryTree<_Tp, _Node>::node_type*BinaryTree<_Tp, _Node>::erase(node_type *node)
{if(null == node) { return null; }node_type *left = node->left_child();node_type *right = node->right_child();if(right->depth() > left->depth()){if(null == left){node_type *node_parent = node->parent();if(null == node_parent){ return _M_root = right; }if(node_parent->left_child() == node){ return node_parent->set_left(right); }return node_parent->set_right(right);}// 获取最左边的结点node_type *reserve = left_child_under(right);node_type *reserve_parent = reserve->parent();node_type *temp = reserve->right_child();reserve_parent->set_left(temp);if(null == temp){ temp = reserve_parent; }// 与删除的结点交换位置node->swap(reserve);reserve->_M_right = null;delete reserve;return temp;}else{if(null == right){node_type *node_parent = node->parent();if(null == node_parent){ return _M_root = left; }if(node_parent->left_child() == node){ return node_parent->set_left(left); }return node_parent->set_right(left);}// 获取最右边的结点node_type *reserve = left->right_child_under();node_type *reserve_parent = reserve->parent();node_type *temp = reserve->left_child();reserve_parent->set_right(temp);if(temp == null){ temp = reserve_parent; }// 与删除的结点交换位置node->swap(reserve);reserve->_M_left = null;delete reserve;return temp;}
}#endif // __BTREE_H__