二叉树的代码实现
看完你能亲手写出 BinNode 与 BinTree 的完整结构并说清每个设计取舍
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
二叉树的代码实现
看完你能亲手写出 BinNode 与 BinTree 的完整结构并说清每个设计取舍
BinNode 是什么
上一页说了二叉树要在代码里落地，那每个节点长什么样？想想你的家族谱系：一个格子记录你自己的信息，旁边标着父亲是谁、上面是长子、下面是次子——BinNode 就是这样一个格子。
格子里的姓名对应 data，父亲栏对应 parent，两栏子嗣对应 lc、rc
BinNode 类定义
逐行看 BinNode 的五个成员变量，每个字段对应树结构的一部分。
五个字段各司其职：data 存内容，parent/lChild/rChild 三条引用搭出树形，height 为 AVL 等平衡操作预留。
BinNode 接口
前两页我们写出了 BinNode 类的字段：数据、左右孩子、父亲。但用这个节点的人不该直接摸它的内部字段——就像遥控器只给你几个按键，电路细节都藏在里面。
按键对应接口方法，电视内部电路对应私有字段
接口的实现细节
宏封装胜过重复：一行宏生成接口，内联实现在头文件里完成，零调用开销。
宏让 BinNodePosi(T) 全程统一写法；类内定义即隐式 inline，size/insert/isLChild 这些高频小函数零调用开销，是接口实现的核心取舍。
BinTree 类
前面我们把每个节点 BinNode 造好了：它能存数据、认得左右孩子和父亲。但节点只是散落的砖块，还缺一堵墙——谁来记住根在哪？树总共多高？这一页看 BinTree 如何搭起整体框架。
前台只记公司大门（根）和人数（规模），具体事务转给各部门（节点）
updateHeight 实现
看一个节点的高度如何计算：取左右子树高度的较大者，再加一。
stature 统一处理空子树返回 -1，这样叶子取 max 后加一正好得 0；高度变化才返回 true，供上层判断是否继续向上更新。
updateHeightAbove 传播
局部调整后，高度变化要沿祖先链逐层上传，直到不再变化为止。
insertAsRoot
insertAsRoot 是让空树「出生」的第一步：只允许在空树上调用。
insertAsLC / insertAsRC
作为左/右孩子插入新节点：规模计数、节点接线、祖先高度传播，三处协作各干一件事。
树的职责（计数、更新高度）与节点的职责（接线）清晰分工：BinNode 一行完成孩子挂接，BinTree 负责全局信息的维护。
插入全流程图解
从调用插入到高度传回，箭头即执行顺序，编号标注四个阶段，自上而下走完整个链路。
自测：插入后谁变高
在叶子节点 x 的左孩子位置插入新节点后，哪些节点的高度会被 updateHeightAbove 更新？
要点收束
- ✓节点存数据与指针，树只是持有根
- ✓高度是懒更新：局部算，向上传播
- ✓插入分三步：建节点、接指针、更新高度
- ✓新节点祖先链都要 updateHeightAbove
- ✓边界先想全：空树、已有孩子、高度持平
课后思考
先合上讲义自己想，再对照参考答案，看看思路差在哪。
参考答案提示：高度只在子树高度真正变化时才需继续传播。想想 insertAsLC 后新子树高度从 -1 变 0，父节点若因此长高才继续上行；一旦高度不变即可停，最好情况 O(1)。
参考答案可以让节点携带哨兵式空节点（类似 BST 的叶哨兵），统一一个插入接口、统一 updateHeight 触发点。代价是每个节点多存空孩子、遍历多判一次；想想哪种场景值得换。
参考答案类比高度上行传播：增删时沿父链维护 size 也行，但删除无法沿链回退，得在插入时为每个祖先 +1 或在节点里存 size 修改入口。权衡：空间换时间，字段越多维护面越大。