`#pragma warning(disable : 4996)

include

include

include

include

template
struct BinNode {
int _depth; // 节点深度
int _height; // 节点高度
T _data; // 存储的数据
BinNode* _parent; // 父节点
BinNode* _lChild; // 左子节点
BinNode* _rChild; // 右子节点

template <typename VST> static  void visitAlongLeftBranch(BinNode* x, VST&, std::stack<BinNode*>& s);

public:
BinNode();
BinNode(const T& data);
int size() const; // 获取当前节点及其所有后代节点的总数
BinNode* succ() const; // 获取中序遍历下的后继节点
template void travLevel(VST&); // 层次遍历
template void travPre(VST&); // 先序遍历（迭代）
template static void travPre_I2(BinNode* x,VST&); // 先序遍历（迭代）
template void travIn(VST&); // 中序遍历（迭代）
template void travPost(VST&); // 后序遍历（迭代）
};

template
BinNode::BinNode() : _depth(0), _height(0), _data(T()), _parent(nullptr), _lChild(nullptr), _rChild(nullptr) {}

template
BinNode::BinNode(const T& data) : _depth(0), _height(0), _data(data), _parent(nullptr), _lChild(nullptr), _rChild(nullptr) {}

template
int BinNode::size() const {
return (_lChild ? _lChild->size() : 0) + (_rChild ? _rChild->size() : 0) + 1;
}

template
BinNode* BinNode::succ() const {
BinNode* p = const_cast<BinNode*>(this);
if (_rChild) {
p = _rChild;
while (p->_lChild) p = p->_lChild;
}
else {
while (p->_parent && p == p->_parent->_rChild) p = p->_parent;
p = p->_parent;
}
return p;
}

template
template
void BinNode::travLevel(VST& visit) {
std::queue<BinNode> q;
q.push(this);
while (!q.empty()) {
BinNode x = q.front(); q.pop();
visit(x->_data);
if (x->_lChild) q.push(x->_lChild);
if (x->_rChild) q.push(x->_rChild);
}
}

template
template
void BinNode::visitAlongLeftBranch(BinNode* x, VST& visit, std::stack<BinNode *> &s)
{
while (!x) {
visit(x);
x = x->_lChild;
s.push(_rChild);
}

}

template
template
void BinNode::travPre(VST& visit) {
std::stack<BinNode> s; // 创建栈
s.push(this); // 将根节点压入栈中
while (!s.empty()) {
BinNode x = s.top(); // 取栈顶元素
s.pop(); // 弹出栈顶元素
visit(x->_data); // 访问该节点
if (x->_rChild) s.push(x->_rChild); // 先压右子节点，后压左子节点
if (x->_lChild) s.push(x->_lChild);
}
}

template
template
static void BinNode::travPre_I2(BinNode* x,VST& visit)
{
std::stack<BinNode *> s;
while (true) {
visitAlongLeftBranch(this, visit, s);
if (s.empty()) break;
x = s.top();
}
}

template
template
void BinNode::travIn(VST& visit) {
std::stack<BinNode> s; // 创建栈
BinNode current = this; // 从当前节点开始
while (current != nullptr || !s.empty()) {
while (current != nullptr) { // 遍历左子树
s.push(current); // 将当前节点压入栈中
current = current->_lChild; // 移动到左子节点
}
if (!s.empty()) {
current = s.top(); // 访问栈顶元素
s.pop(); // 弹出栈顶元素
visit(current->_data); // 访问该节点
current = current->_rChild; // 转向右子节点
}
}
}

template
template
void BinNode::travPost(VST& visit) {
std::stack<BinNode> s1, s2; // 创建两个栈
s1.push(this); // 将根节点压入第一个栈
while (!s1.empty()) {
BinNode x = s1.top();
s1.pop();
s2.push(x); // 将节点压入第二个栈
if (x->_lChild) s1.push(x->_lChild); // 先压左子节点
if (x->_rChild) s1.push(x->_rChild); // 再压右子节点
}
while (!s2.empty()) { // 访问第二个栈中的节点
visit(s2.top()->_data);
s2.pop();
}
}

template
class BinTree {
protected:
int _size; // 节点数
BinNode* _root; // 根节点

virtual int updateHeight(BinNode<T>* x);            // 更新节点高度
void updateHeightAbove(BinNode<T>* x);      // 更新当前节点及其所有祖先的高度
void release(BinNode<T>* x);                // 递归释放节点内存

virtual int updateDepth(BinNode<T>* x);            // 更新节点深度
void updateDepthBelow(BinNode<T>* x);      // 更新当前节点及其所有子节点的深度

public:
BinTree() : _size(0), _root(nullptr) {}
~BinTree(); // 析构函数
int size() const { return _size; }
bool empty() const { return !_root; }
BinNode* root() const { return _root; }

BinNode<T>* insertAsRoot(const T& elem);    // 插入根节点
BinNode<T>* insertAsLC(BinNode<T>* parent, const T& elem);  // 插入左子节点
BinNode<T>* insertAsRC(BinNode<T>* parent, const T& elem);  // 插入右子节点

};

template
int BinTree::updateHeight(BinNode* x) {
return x->_height = 1 + std::max(x->_lChild ? x->_lChild->_height : -1,
x->_rChild ? x->_rChild->_height : -1);
}

template
void BinTree::updateHeightAbove(BinNode* x) {
while (x) {
int oldHeight = x->_height; // 保存旧高度
updateHeight(x);
if (oldHeight == x->_height) { // 如果高度没有变化
break; // 提前终止更新
}
x = x->_parent;
}
}

template
int BinTree::updateDepth(BinNode* x) {
if (x == nullptr) return -1; // 深度以-1开始
x->_depth = x->_parent ? x->_parent->_depth + 1 : 0; // 更新深度
return x->_depth;
}

template
void BinTree::updateDepthBelow(BinNode* x) {
if (x) {
int oldDepth = x->_depth; // 保存旧深度
updateDepth(x); // 更新当前节点的深度
if (oldDepth == x->_depth) { // 如果深度没有变化
return; // 提前终止更新
}
updateDepthBelow(x->_lChild); // 递归更新左子节点深度
updateDepthBelow(x->_rChild); // 递归更新右子节点深度
}
}

template
void BinTree::release(BinNode* x) {
if (x) {
release(x->_lChild); // 释放左子节点
release(x->_rChild); // 释放右子节点
delete x; // 释放当前节点
}
}

template
BinTree::~BinTree() {
release(_root); // 释放根节点及其所有子节点
}

template
BinNode* BinTree::insertAsRoot(const T& elem) {
_root = new BinNode(elem);
_size = 1;
updateDepthBelow(_root); // 更新深度
return _root;
}

template
BinNode* BinTree::insertAsLC(BinNode* parent, const T& elem) {
if (!parent->_lChild) {
parent->_lChild = new BinNode(elem);
parent->_lChild->_parent = parent;
_size++;
updateHeightAbove(parent); // 更新高度
updateDepthBelow(parent->_lChild); // 更新深度
return parent->_lChild;
}
return nullptr; // 返回空表示插入失败
}

template
BinNode* BinTree::insertAsRC(BinNode* parent, const T& elem) {
if (!parent->_rChild) {
parent->_rChild = new BinNode(elem);
parent->_rChild->_parent = parent;
_size++;
updateHeightAbove(parent); // 更新高度
updateDepthBelow(parent->_rChild); // 更新深度
return parent->_rChild;
}
return nullptr; // 返回空表示插入失败
}

void visit(int& e) { std::cout << e << " "; }

int main() {
BinTree tree;
BinNode* root = tree.insertAsRoot(1);
BinNode* leftChild = tree.insertAsLC(root, 2);
BinNode* rightChild = tree.insertAsRC(root, 3);
tree.insertAsLC(leftChild, 4);
tree.insertAsRC(leftChild, 5);
tree.insertAsLC(rightChild, 6);
tree.insertAsRC(rightChild, 7);

std::cout << "Level Order: ";
root->travLevel(visit);
std::cout << "\nPre-order: ";
root->travPre(visit);
std::cout << "\nIn-order: ";
root->travIn(visit);
std::cout << "\nPost-order: ";
root->travPost(visit);
std::cout << std::endl;

return 0;

}
`