- #include<stdexcept>
- #ifndef ToozyBinaryTreeHead
- #define ToozyBinaryTreeHead
- template <class T>
- class ToozyBinaryTree{
- public:
- static const int LEFT = 1;
- static const int RIGHT = 2;
- struct ToozyBinaryTreeNode{
- ToozyBinaryTreeNode *left;
- ToozyBinaryTreeNode *right;
- ToozyBinaryTreeNode *nextNode;
- T value;
- ToozyBinaryTreeNode(const T *v){
- value = *v;
- left = nullptr;
- right = nullptr;
- nextNode = nullptr;
- }
- };
- typedef bool (*findFunc)(const ToozyBinaryTreeNode*,const T*);
- findFunc findFunction;
- ToozyBinaryTree(ToozyBinaryTreeNode *root);
- ToozyBinaryTree(T *v);
- ~ToozyBinaryTree();
- const ToozyBinaryTreeNode *find(const T *value) const;
- const ToozyBinaryTreeNode *add(const ToozyBinaryTreeNode *parent,const T *value,int type);
- //const ToozyBinaryTreeNode *left(const ToozyBinaryTreeNode *parent);
- //const ToozyBinaryTreeNode *right(const ToozyBinaryTreeNode *parent);
- //int depth();//深度
- const ToozyBinaryTreeNode *getRoot();
- //void del(ToozyBinaryTreeNode *node);
- //int nodeNum();
- //int leafNum();
- protected:
- ToozyBinaryTreeNode* _root;
- ToozyBinaryTreeNode* _lastNode;
- };
- template<class T>
- ToozyBinaryTree<T>::ToozyBinaryTree(typename ToozyBinaryTree<T>::ToozyBinaryTreeNode *root){
- _root = root;
- if (_root) {
- _lastNode = _root;
- }
- };
- template<class T>
- ToozyBinaryTree<T>::ToozyBinaryTree(T *v){
- _root = new ToozyBinaryTree<T>::ToozyBinaryTreeNode(v);
- if (_root) {
- _lastNode = _root;
- }
- };
- template<class T>
- ToozyBinaryTree<T>::~ToozyBinaryTree(){
- ToozyBinaryTree<T>::ToozyBinaryTreeNode *node,*nextNode;
- node = _root;
- do {
- nextNode = node->nextNode;
- delete node;
- } while (node = nextNode);
- };
- template<class T>
- const typename ToozyBinaryTree<T>::ToozyBinaryTreeNode *ToozyBinaryTree<T>::find(const T *value) const{
- ToozyBinaryTree<T>::ToozyBinaryTreeNode *node;
- node = _root;
- do {
- if (node->value == *value) {
- return node;
- }
- } while (node = node->nextNode);
- return nullptr;
- };
- template<class T>
- const typename ToozyBinaryTree<T>::ToozyBinaryTreeNode *ToozyBinaryTree<T>::add(const typename ToozyBinaryTree<T>::ToozyBinaryTreeNode *parent,const T *value,int type){
- if (!parent) {
- throw new std::runtime_error("parent node can not empty");
- }
- ToozyBinaryTree<T>::ToozyBinaryTreeNode *node = new ToozyBinaryTree<T>::ToozyBinaryTreeNode(value);
- ToozyBinaryTree<T>::ToozyBinaryTreeNode *parentNode = const_cast<ToozyBinaryTree<T>::ToozyBinaryTreeNode *>(parent);
- switch (type) {
- case ToozyBinaryTree<T>::LEFT:
- if (parentNode->left) {
- throw std::runtime_error("left node already exists");
- }
- parentNode->left = node;
- break;
- case ToozyBinaryTree<T>::RIGHT:
- if (parentNode->right) {
- throw std::runtime_error("right node already exists");
- }
- parentNode->right = node;
- break;
- default:
- throw std::runtime_error("unknow node type");
- }
- _lastNode->nextNode = node;
- _lastNode = node;
- return node;
- };
- template<class T>
- const typename ToozyBinaryTree<T>::ToozyBinaryTreeNode *ToozyBinaryTree<T>::getRoot(){
- return _root;
- };
- #endif
- //该片段来自于http://www.codesnippet.cn/detail/160520149609.html
来源: http://www.codesnippet.cn/detail/160520149609.html