#ifndef BINARYTREE_H
#define BINARYTREE_H
//---------------------------------------------------------------------------
//
// BinaryTree.h
//---------------------------------------------------------------------------
#include <vector>
#include <list>
#include <type_traits>
#include <queue>
#include <map>//it use return node array location
template <typename T>
struct BSTNode{
BSTNode(T data = T()) :_data(data), _left(nullptr), _right(nullptr),_parent(nullptr) {}
T _data;
BSTNode<T>* _left;
BSTNode<T>* _right;
BSTNode<T>* _parent;
};
template<typename T>
class BSTree {
using value_type = T;
using reference_value_type = T&;
using const_value_type = const T&;
using node_type = BSTNode<T>;
using node_type_ptr = BSTNode<T>*;
using const_node_type_ptr = const BSTNode<T>*;
node_type_ptr m_root = nullptr;
public:
~BSTree() { remove(getRoot()); }
node_type_ptr& getRoot() { return m_root; }
virtual void create(const std::vector<value_type>& _vec) {
for (auto it:_vec) {
insert(it, getRoot());
}
}
void insert(const_value_type _t, node_type_ptr _parent) {
node_type_ptr now_node = new node_type;
now_node->_data = _t;
insert(now_node, _parent);
}
void insert(node_type_ptr& _node, node_type_ptr _parent) {
//root
if (getRoot() == nullptr) {
getRoot() = _node;
return;
}
//not root
if (_node->_data < _parent->_data) {//left
if (_parent->_left)insert(_node, _parent->_left);
else {
_parent->_left = _node;
_node->_parent = _parent;
}
}
else {
if (_parent->_right)insert(_node, _parent->_right);
else {
_parent->_right = _node;
_node->_parent = _parent;
}
}
}
void remove(node_type_ptr _node) {
if (_node == nullptr)return;
remove(_node->_left);
remove(_node->_right);
if (getRoot() == _node) {}
else if (isLeft(_node))_node->_parent->_left = nullptr;
else if (isLeft(_node)==false)_node->_parent->_right=nullptr;
LOGXD("delete node:", _node->_data);
delete _node;
}
auto midOrder(node_type_ptr _start) {
std::list<T> data{};
if (_start == nullptr)return data;
auto d1= midOrder(_start->_left);
data.insert(data.end(), d1.begin(),d1.end());
data.emplace_back(_start->_data);
auto d2 = midOrder(_start->_right);
data.insert(data.end(), d2.begin(), d2.end());
return data;
}
void find(const_value_type _t,node_type_ptr _node,node_type_ptr &_result) {
if (_node == nullptr)return;
if (_t == _node->_data) {
_result = _node;
}
else if (_t < _node->_data) {
find(_t, _node->_left, _result);
}
else {
find(_t, _node->_right, _result);
}
}
bool isLeft(const_node_type_ptr _node) {
//must sure node have parent
if(_node->_parent->_left==_node)return true;
else return false;
}
auto arrayInfo(){
std::queue<node_type_ptr> que{};
std::map<node_type_ptr, value_type> infos;
if (getRoot() == nullptr)return infos;
que.push(getRoot());
long node_loc = 0;
while (!que.empty()) {
auto front_node = que.front();
if (front_node->_left) que.push(front_node->_left);
if (front_node->_right) que.push(front_node->_right);
if (front_node->_parent == nullptr){//root
node_loc = 1;
}
else {
if (isLeft(front_node))node_loc = infos[front_node->_parent] * 2;
else node_loc = infos[front_node->_parent] * 2+1;
}
infos[front_node] = node_loc;
que.pop();
}
return infos;
}
};
#endif // BINARYTREE_H
void PaintTree::test(){
//
const int arr_len = 8;
vector<int> arr;
srand(time(0));
for(int i=0;i<arr_len;i++){
arr.emplace_back(rand()%200+(i));
}
BSTree<int> bst;
//create
LOGXA("1.start create...,get middle order:");
bst.create(arr);
auto mid_data = bst.midOrder(bst.getRoot());
for (const auto& it : mid_data) {
LOGXD(it);
}
//get array info
LOGXA("2.get tree arrary info,and paint it");
int array_max_len = 0;
auto array_info = bst.arrayInfo();
for (const auto& it : array_info) {
LOGXT(it.second, it.first->_data);
if (array_max_len < it.second)array_max_len = it.second;
}
array_max_len+=1;
std::vector<std::string> vec_str{};
vec_str.assign(array_max_len, to_string(0));
for (const auto& it : array_info) {
vec_str[it.second] = to_string(it.first->_data);
}
auto image= drawTreeArray(vec_str);
getDisplayLabel()->flushDisplay(image);
//find test
LOGXA("3.test find and remove");
BSTNode<int>* find_node = nullptr;
bst.find(arr[3], bst.getRoot(), find_node);
LOGXD(VAR_DATA(find_node));
find_node = nullptr;
bst.find(123, bst.getRoot(), find_node);
LOGXD(VAR_DATA(find_node));
//auto image= drawTreeArray(arr);
//getDisplayLabel()->flushDisplay(image);
}
/*
[+] log construction, can use it E:\Desktop\t\PaintTree/_log/log.html
[0]06:20:55[info][11920] [PaintTree::test] 1.start create...,get middle order: (PaintTree.cpp:39)
[1]06:20:55[debg][11920] [PaintTree::test] 43 (PaintTree.cpp:43)
[2]06:20:55[debg][11920] [PaintTree::test] 57 (PaintTree.cpp:43)
[3]06:20:55[debg][11920] [PaintTree::test] 84 (PaintTree.cpp:43)
[4]06:20:55[debg][11920] [PaintTree::test] 90 (PaintTree.cpp:43)
[5]06:20:55[debg][11920] [PaintTree::test] 99 (PaintTree.cpp:43)
[6]06:20:55[debg][11920] [PaintTree::test] 102 (PaintTree.cpp:43)
[7]06:20:55[debg][11920] [PaintTree::test] 166 (PaintTree.cpp:43)
[8]06:20:55[debg][11920] [PaintTree::test] 181 (PaintTree.cpp:43)
[9]06:20:55[info][11920] [PaintTree::test] 2.get tree arrary info,and paint it (PaintTree.cpp:47)
[10]06:20:55[test][11920] [PaintTree::test] 1 181 (PaintTree.cpp:51)
[11]06:20:55[test][11920] [PaintTree::test] 23 166 (PaintTree.cpp:51)
[12]06:20:55[test][11920] [PaintTree::test] 5 99 (PaintTree.cpp:51)
[13]06:20:55[test][11920] [PaintTree::test] 16 43 (PaintTree.cpp:51)
[14]06:20:55[test][11920] [PaintTree::test] 2 90 (PaintTree.cpp:51)
[15]06:20:55[test][11920] [PaintTree::test] 4 84 (PaintTree.cpp:51)
[16]06:20:55[test][11920] [PaintTree::test] 11 102 (PaintTree.cpp:51)
[17]06:20:55[test][11920] [PaintTree::test] 8 57 (PaintTree.cpp:51)
[18]06:20:55[info][11920] [PaintTree::drawTreeArray] depath: 5 image_width: 1000 image_heihet: 700 (PaintTree.cpp:111)
[19]06:20:55[info][11920] [PaintTree::test] 3.test find and remove (PaintTree.cpp:64)
[20]06:20:55[debg][11920] [PaintTree::test] find_node: 00F0C108 (PaintTree.cpp:67)
[21]06:20:55[debg][11920] [PaintTree::test] find_node: 00000000 (PaintTree.cpp:70)
[22]06:20:55[debg][11920] [BSTree<int>::remove] delete node: 43 (BinaryTree.h:76)
[23]06:20:55[debg][11920] [BSTree<int>::remove] delete node: 57 (BinaryTree.h:76)
[24]06:20:55[debg][11920] [BSTree<int>::remove] delete node: 84 (BinaryTree.h:76)
[25]06:20:55[debg][11920] [BSTree<int>::remove] delete node: 166 (BinaryTree.h:76)
[26]06:20:55[debg][11920] [BSTree<int>::remove] delete node: 102 (BinaryTree.h:76)
[27]06:20:55[debg][11920] [BSTree<int>::remove] delete node: 99 (BinaryTree.h:76)
[28]06:20:55[debg][11920] [BSTree<int>::remove] delete node: 90 (BinaryTree.h:76)
[29]06:20:55[debg][11920] [BSTree<int>::remove] delete node: 181 (BinaryTree.h:76)
*/