二叉树常用代码合集【C++版】（详细注释）

二叉树常用代码合集【C++版】（详细注释）
关键的地方有详细的注释。如果需要更详细的注释，可以丢给大模型再注释一遍。

#include <iostream>  
#include <memory>  
#include <string>  
#define mv(x) std::move(x)  
#define coutln(x) cout << x << endl  
  
using namespace std;  
  
template <typename E>  
class LinkStack {  
private:  
    typedef unsigned long long ull;  
    ull size = 0;  
  
private:  
    struct Node {  
        E data;  
        std::unique_ptr<Node> nxt; // 使用智能指针  
        explicit Node(E x) : data(x), nxt(nullptr) {}  
    };  
  
    struct LStack {  
        std::unique_ptr<Node> base;  
        Node* top; // top 仍然是裸指针，但它指向的是唯一拥有者的智能指针管理的对象  
    };  
  
    LStack stk;  
  
public:  
    LinkStack() {  
        stk.base = std::make_unique<Node>(E()); // 创建一个 base 节点  
        stk.top = stk.base.get(); // top 指向 base    }  
  
    ~LinkStack() {  
        // 智能指针会自动释放内存，因此不需要显式释放  
    }  
  
    [[maybe_unused]] [[nodiscard]] E &getTop() const {  
        if (!stk.top) {  
            throw std::out_of_range("Stack is empty.");  
        }  
        return stk.top->data;  
    }  
  
    void push(const E &x) {  
        auto newNode = std::make_unique<Node>(x); // 创建新节点  
        newNode->nxt = std::move(stk.base->nxt); // 转移 base 中的 nxt 链接  
        stk.base->nxt = std::move(newNode); // 新节点成为栈顶  
        stk.top = stk.base->nxt.get(); // top 更新为栈顶节点  
        ++size;  
    }  
  
    E pop() {  
        if (size == 0) {  
            throw std::out_of_range("Stack is empty.");  
        }  
        E x = stk.top->data;  
        stk.base->nxt = std::move(stk.top->nxt); // top 移动到下一个节点  
        stk.top = stk.base->nxt.get(); // 更新 top        --size;  
        return x;  
    }  
  
    E operator--() {  
        return pop();  
    }  
  
    LinkStack &operator+=(const E &rhs) {  
        push(rhs);  
        return *this;  
    }  
    E top() {  
        return stk.top->data;  
    }  
    bool empty() {  
        return !(bool )size;  
    }  
    ull get_size() {  
        return this->size;  
    }  
  
};  
  
template<typename E>  
class BiTree {  
private:  
    struct Node {  
        E data;  
        unique_ptr<Node> lchild, rchild;  
        Node(E x) : data(x), lchild(nullptr), rchild(nullptr) {}  
    };  
  
private:  
    unique_ptr<Node> root;  
public:  
    const string _sep; // 用一个空格分隔输出  
private:  
    string _in_ordered_traverse_str_;  
    string _pre_ordered_traverse_str_;  
    string _post_ordered_traverse_str_;  
public:  
    // 构造函数，根据根节点的数据初始化  
    BiTree(char root_data) {  
        if (root_data == '#') root = nullptr;  
        else {  
            root = make_unique<Node>(root_data);  
        }  
    }  
  
    // 构造函数，根据前序遍历的字符串生成二叉树  
    BiTree(string &pre_str) {  
        if (!pre_str.empty()) {  
            int index = 0;  
            generate_by_pre_str(root, pre_str, index);  
        }  
    }  
  
    // 中序遍历（非递归）  
    string &InOrderTraverse_nonRecursive() {  
        _in_ordered_traverse_str_ = "";  
        InOrderTraverse_1(root.get()); // 使用 get() 获取裸指针  
        return _in_ordered_traverse_str_;  
    }  
  
    string &InOrderTraverse() {  
        _in_ordered_traverse_str_ = "";  
        InOrderTraverse_2(root.get());  
        return _in_ordered_traverse_str_;  
    }  
  
    string &PreOrderTraverse() {  
        _pre_ordered_traverse_str_ = "";  
        PreOrderTraverse_1(root.get());  
        return _pre_ordered_traverse_str_;  
    }  
  
    string &PreOrderTraverse_nonRecursive() {  
        _pre_ordered_traverse_str_ = "";  
        PreOrderTraverse_2(root.get());  
        return _pre_ordered_traverse_str_;  
    }  
  
    string &PostOrderTraverse() {  
        _post_ordered_traverse_str_ = "";  
        PostOrderTraverse_1(root.get());  
        return _post_ordered_traverse_str_;  
    }  
  
    string &PostOrderTraverse_nonRecursive() {  
        _post_ordered_traverse_str_ = "";  
        PostOrderTraverse_2(root.get());  
        return _post_ordered_traverse_str_;  
    }  
    // 添加一个公共的显示接口  
    void displayTree() const {  
        displayTree(root.get());  
    }  
  
    [[nodiscard]] int get_depth() const {  
        return get_depth_2(root.get());  
    }  
    [[nodiscard]] int countNodes() const {  
        return coutNodes_nonRecursive(root.get());  
    }  
    [[nodiscard]] int countLeaves() const {  
        return countLeaves_nonRecursive(root.get());  
    }  
  
    [[nodiscard]] int evaluateInfixExpression() const {  
        return evaluateInfixExpression_(root.get());  
    }  
    [[nodiscard]] string toInfixExpression() const {  
        return toInfixExpression_2(root.get());  
    }  
private:  
    // 通过前序遍历字符串生成二叉树  
    void generate_by_pre_str(unique_ptr<Node>& base, string &pre_str, int& index) {  
        if (index >= pre_str.size() || pre_str[index] == '#') {  
            base = nullptr; // 设置为空  
            index++; // 移动到下一个字符  
        } else {  
            base = make_unique<Node>(pre_str[index]); // 创建新节点  
            index++; // 移动到下一个字符  
            generate_by_pre_str(base->lchild, pre_str, index); // 递归生成左子树  
            generate_by_pre_str(base->rchild, pre_str, index); // 递归生成右子树  
        }  
    }  
  
    // 中序遍历（非递归实现）  
    inline void InOrderTraverse_1(Node* base) {  
        /*实现逻辑：  
         * 使用stack模拟递归访问的路径。  
         * 中序遍历中的节点顺序是（left, current, right）  
         *         * 1. 一直往左访问，直到NULL（这里用data='#'表示）  
         * 2. 取出栈顶元素（记为current）(栈素储存的即是Node*)  
         * 3. 将current添加到_in_ordered_traverse_末尾  
         * 4. 访问右节点  
         * */        /*         * 简单来说，这段代码中，内层循环会一直向左枝前进，直到遇到nullptr  
         * 而stack是后入先出的，因此取出元素的过程刚好是（left, current）的顺序。  
         * 之后访问right，于是整个过程顺序就是（left， current， right）  
         * */        LinkStack<Node*> stack;  
        Node* current = base;  
  
        // 当栈不为空时，继续出栈。当current==NULL时，已经遍历到了最右的叶子以外了。  
        while (current != nullptr || !stack.empty()) {  
            // 将当前节点的左子节点依次压栈  
            while (current != nullptr) {  
                stack.push(current);  
                current = current->lchild.get();  
            }  
            // 当前节点为空(压栈循环被退出了)，弹出栈顶元素并访问  
            current = stack.pop();  
//            coutln( current->data + _sep);  
            _in_ordered_traverse_str_ += current->data + _sep;  
            // 转向当前节点的右子节点  
            current = current->rchild.get();  
        }  
    }  
  
    // 中序遍历(递归)  
    void InOrderTraverse_2(Node* base) {  
        if (base/*!= nullptr*/) {  
            InOrderTraverse_1(base->lchild.get()); // 递归左子树  
            _in_ordered_traverse_str_ += base->data + _sep;  
            InOrderTraverse_1(base->rchild.get()); // 递归右子树  
        }  
    }  
  
    // 前序遍历(递归)  
    void PreOrderTraverse_1(Node *base) {  
        if (base /*!= nullptr*/) {  
            _pre_ordered_traverse_str_ += base->data + _sep;  
            PreOrderTraverse_1(base->lchild.get());  
            PreOrderTraverse_1(base->rchild.get());  
  
        }  
    }  
  
    // 前序遍历（非递归实现）  
    void PreOrderTraverse_2(Node *base) {  
        /*实现逻辑：  
         * 使用stack模拟递归访问的路径。  
         * 前序遍历的节点顺序是（current, left, right）  
         *         * 1. 一直往左访问，并记录数据，直到NULL（这里用data='#'表示）  
         * 2. 取出栈顶元素（记为current），访问它的右节点  
         * 3. 将current添加到_in_ordered_traverse_末尾  
         * 4. 访问右节点  
         * */        /*         * 简单来说，这段代码中，内层循环会一直向左枝前进，直到遇到nullptr  
         * 而stack是后入先出的，为了得到（current, left）的顺序，需要先记录数据再向左枝前进  
         * 之后再访问右枝。  
         * 于是整个过程顺序就是(current, left, right)  
         * */        LinkStack<Node *> stack;  
        Node *cur = base;  
        while (cur /*!= nullptr*/ || !stack.empty()) {  
            while (cur) {  
                _pre_ordered_traverse_str_ += cur->data + _sep;  
                stack.push(cur);  
                cur = cur->lchild.get();  
            }  
            cur = stack.pop();  
            cur = cur->rchild.get();  
  
        }  
    }  
  
    //后序遍历(递归)  
    void PostOrderTraverse_1(Node *base) {  
        if (base) {  
            PostOrderTraverse_1(base->lchild.get());  
            PostOrderTraverse_1(base->rchild.get());  
            _post_ordered_traverse_str_ += base->data + _sep;  
        }  
    }  
  
    //后序遍历(非递归)  
    void PostOrderTraverse_2(Node *base) {  
        if (!base) return;  
  
        LinkStack<Node *> stack;  
        Node *prev = nullptr;   // 上一个访问的节点  
        stack.push(base);  
  
        while (!stack.empty()) {  
            Node *cur = stack.top();  
            if ((!cur->lchild && !cur->rchild) || (prev && (prev == cur->lchild.get() || prev == cur->rchild.get()))) {  
                _post_ordered_traverse_str_ += cur->data + _sep;  
                stack.pop();  
                prev = cur;  
            } else {  
                // 先将右子节点压栈，再压左子节点  
                if (cur->rchild) stack.push(cur->rchild.get());  
                if (cur->lchild) stack.push(cur->lchild.get());  
            }  
        }  
    }  
  
    void displayTree(Node* node, const string& prefix = "", bool isLeft = true) {  
        if (!node) return;  
  
        // 输出当前节点  
        cout << prefix << (isLeft ? "|--" : u8"|-- ") << node->data << endl;  
  
        // 更新前缀，递归地处理左右子树  
        string newPrefix = prefix + (isLeft ? u8"|   " : u8"    ");  
        displayTree(node->lchild.get(), newPrefix, true);  
        displayTree(node->rchild.get(), newPrefix, false);  
    }  
  
    // 计算二叉树的深度（递归）  
    int get_depth_1(Node *base, int de) const {  
        if (!base) return de-1; // 如果已经到达了NULL，则这个路径的深度是上一个节点的深度  
        // 深度为左枝和右枝的最大深度  
        return max(get_depth_1(base->rchild.get(), de+1), get_depth_1(base->lchild.get(), de+1));;  
    }  
    int get_depth_2(Node *base) {  
        if (!base) return 0;  
        else return max(get_depth_2(base->lchild.get()), get_depth_2(base->rchild.get())) + 1;  
    }  
  
    int get_n_nodes_1() {  
        this->InOrderTraverse();  
        return this->_in_ordered_traverse_str_.length();  
    }  
  
    int coutNodes_Recursive(Node *base) {  
        // 节点个数 = 左子树节点个数 + 右子树节点个数 + 1（本节点）  
        if (!base) return 0;  
        else return coutNodes_Recursive(base->lchild.get()) + coutNodes_Recursive(base->rchild.get()) + 1;  
    }  
  
    int coutNodes_nonRecursive(Node *base) const {  
        LinkStack<Node *> stack;  
        Node *cur = base;  
        int n = 0;  
        while (cur /*!= nullptr*/ || !stack.empty()) {  
            while (cur) {  
                ++n;  
                stack.push(cur);  
                cur = cur->lchild.get();  
            }  
            cur = stack.pop();  
            cur = cur->rchild.get();  
        }  
        return n;  
    }  
  
    int countLeaves_Recursive(Node *base) const {  
        // 当前节点的分支下：总叶子数 = 左子树的叶子个数 + 右子树的叶子个数  
        if (!base->lchild && !base->rchild) return 1;   // 如果是叶子  
        else return countLeaves_Recursive(base->lchild.get()) + countLeaves_Recursive(base->rchild.get());  
    }  
  
    int countLeaves_nonRecursive(Node *base) const {  
        // 基于前序遍历计算 总叶子数  
        LinkStack<Node *> stack;  
        Node *cur = base;  
        int n = 0;  
        while (cur || !stack.empty()) {  
            while (cur) {  
                stack.push(cur);  
                cur = cur->lchild.get();  
            }  
            cur = stack.pop();  
            if (!cur->lchild && !cur->rchild) ++n;  
            cur = cur->rchild.get();  
        }  
        return n;  
    }  
private:  
    // 递归生成带括号的中缀表达式  
    [[nodiscard]] string toInfixExpression(Node* node) const {  
        if (!node) return "";  
  
        // 如果是叶节点，直接返回数据  
        if (!node->lchild && !node->rchild) {  
            return string(1, node->data);  
        }  
  
        // 左子树的表达式  
        string leftExpr = toInfixExpression(node->lchild.get());  
        // 右子树的表达式  
        string rightExpr = toInfixExpression(node->rchild.get());  
  
        // 如果节点有子节点，加上括号  
        return "(" + leftExpr + node->data + rightExpr + ")";  
    }  
  
    // 递归生成带括号的中缀表达式（简洁表达式版）  
    [[nodiscard]] string toInfixExpression_2(Node *base) const {  
        // 如果是叶节点，直接返回数据  
        if (!base->lchild && !base->rchild) {  
            return string(1, base->data);  
        }  
        // 左子树的表达式  
        string leftExpr = toInfixExpression_2(base->lchild.get());  
        // 右子树的表达式  
        string rightExpr = toInfixExpression_2(base->rchild.get());  
        if (rightExpr.length() == 1 || base->rchild->data == '*' || base->rchild->data == '/' || base->data == '+') {  
            // 如果满足任意一种情况(右节点是叶子，右节点运算符是*或/，当前节点运算符是+)，则不用加括号。  
            // -+a##*b##-c##d##/e##f## -> a+b*(c-d)-e/f  
            return leftExpr + base->data + rightExpr;  
        } else {  
            return leftExpr + base->data + "(" + rightExpr + ")";  
        }  
    }  
  
    [[nodiscard]] int evaluateInfixExpression_(Node *base) const {  
//        if (!base) return 0;  
        // 如果是叶节点，直接返回数据  
//        coutln(base->data);  
        if (!base->rchild && !base->lchild) return (int ) (base->data & 0xf);    // ASCII转数字  
        else {  
            auto eval = [&](int a, int b, char opr) constexpr {  
                switch (opr) {  
                    case '+': return a + b;  
                    case '-': return a - b;  
                    case '*': return a * b;  
                    case '/': return a / b;  
                    default: return 0;  
                }  
            };  
            return eval(evaluateInfixExpression_(base->lchild.get()), evaluateInfixExpression_(base->rchild.get()), base->data);  
        }  
    }  
};  
  
  
int main() {  
    string str;  
    cin >> str; // 输入前序遍历字符串  
//    string debug_s1 = "ABC##DE#G##F###";  
    BiTree<char> bt(str); // 使用前序遍历字符串构造二叉树  
  
    coutln(bt.toInfixExpression());  
  
    return 0;  
}