如何从字符串构建二叉树？代码输出与预期不符求排查

需求：按规则构建二叉树：取字符串长度一半位置的字符作为根节点，前半部分字符递归构建左子树，后半部分字符递归构建右子树，之后对二叉树执行后序遍历并输出结果。
原始文本：Cuando duerma con la soledad.
预期输出：uCnodadeum ar nol a oela.ddsc
实际输出：uCnodadeum ar o nas llded.aoc
以下是实现代码及BinTree类定义，无法定位错误，寻求帮助：

构建二叉树与后序遍历代码 #

void leer_mensaje_arbol(BinTree<char> &a, int ini, int fin) {
    if (ini > fin) a = BinTree<char>();
    else {
        int m = (ini + fin) / 2;
        BinTree<char> l;
        leer_mensaje_arbol(l,ini,m-1);
        BinTree<char> r;
        leer_mensaje_arbol(r,m+1,fin);
        a = BinTree<char>(msj[m],l,r);
    }
}

void escribir_inorden(const BinTree<char> &a) {
    if (not a.empty()) {
        escribir_inorden(a.left());
        escribir_inorden(a.right());
        cout << a.value();
    }
}

BinTree类定义 #

#ifndef BINTREE_HH
#define BINTREE_HH

#ifndef NO_DIAGRAM
#include <cassert>
#include <memory>
#endif

using namespace std;

// A BinTree<T> implements binary trees with values of type T.
template <typename T>
class BinTree {

    struct Node {
        T x;
        shared_ptr<Node> left;
        shared_ptr<Node> right;

        Node (const T& x, shared_ptr<Node> left, shared_ptr<Node> right)
        :   x(x), left(left), right(right)
        {   }

    };

    // A tree only holds a node pointer.
    shared_ptr<Node> p;

    // Constructs a tree from a node pointer.
    BinTree (shared_ptr<Node> p)
    :   p(p)
    {   }

    // Notes:
    //   - default operator=() is good.
    //   - default destructor is good. Θ(n) where n is the number of nodes in the tree.
    //   - std::swap() already works by default.

public:

    // Constructs an empty tree. Θ(1).
    BinTree ()
    :   p(nullptr)
    {   }

    // Constructs a tree with a value x and no subtrees. Θ(1).
    explicit BinTree (const T& x) {
        p = make_shared<Node>(x, nullptr, nullptr);
    }

    // Constructs a tree with a value x and two subtrees left and right. Θ(1).
    explicit BinTree (const T& x, const BinTree& left, const BinTree& right) {
        p = make_shared<Node>(x, left.p, right.p);
    }

    // Tells if this tree is empty. Θ(1).
    bool empty () const {
        return not p;
    }

    // Returns the left subtree of this tree (cannot be empty). Θ(1).
    BinTree left () const {
        assert(not empty());
        return BinTree(p->left);
    }

    // Returns the right subtree of this tree (cannot be empty). Θ(1).
    BinTree right () const {
        assert(not empty());
        return BinTree(p->right);
    }

    // Returns the value of this tree (cannot be empty). Θ(1).
    const T& value () const {
        assert(not empty());
        return p->x;
    }

};
#endif

错误原因与修正方案 #

错误出在根节点位置的计算逻辑：当前代码中int m = (ini + fin) / 2;使用整数除法取区间的下中位数，导致当区间长度为偶数时，左子树长度比右子树多1，不符合"前半部分、后半部分各占一半"的要求。

修正代码

将根节点位置计算语句修改为：

int m = ini + (fin - ini + 1) / 2;

逻辑说明

该计算方式取区间的上中位数，确保：

• 当区间长度为奇数时，左子树长度比右子树多1；
• 当区间长度为偶数时，左子树和右子树长度完全相等；
  完全匹配"前半部分构建左子树，后半部分构建右子树"的需求。修正后重新执行，即可得到预期输出。

内容的提问来源于stack exchange，提问作者user19104683