【文件属性】：
文件名称：事叉树模板类BinTree-web服务稳定性测试 负载测试 可靠性测试 测试报告
文件大小：10.35MB
文件格式：PDF
更新时间：2024-07-30 10:59:10
数据结构 邓俊辉 清华大学 mooc学堂在线 教材
代码5.5 事叉树模板类BinTree
其中，_root指向树根，_size动态记录树的规模，且_root = NULL当且仅当_size = 0。
高度更新
二叉树任一节点的高度，都等于其孩子节点的最大高度加一。于是，每当某一节点的孩子或
后代有所增减，其高度都有必要及时更新。然而实际上，节点自身很难发现后代的变化，因此这
里反过来采用另一处理策略：一旦有节点加入或离开二叉树，则更新其所有祖先的高度。请读者
自行验证，这一原则实际上与前一个等效（习题[5-3]）。
在每一节点v处，只需读出其左、右孩子的高度并取二者之间的大者，再计入当前节点本身，
就得到了v的新高度。通常，接下来还需要从v出发沿parent指针逆行向上，依次更新各代祖先
的高度记录。这一过程可具体实现如代码5.6所示。
1 template int BinTree::updateHeight(BinNodePosi(T) x) //更新节点x高度
2 { return x->height = 1 + max(stature(x->lChild), stature(x->rChild)); } //具体觃则因树丌同而异
3
4 template void BinTree::updateHeightAbove(BinNodePosi(T) x) //更新v及祖先癿高度
5 { while (x) { updateHeight(x); x = x->parent; } } //可优化：一旦高度未发，即可终止
代码5.6 事叉树节点癿高度更新
更新每一节点本身的高度，只需执行两次getHeight()操作、两次加法以及两次取最大操作，
不过常数时间，故updateHeight()算法总体运行时间也是O(depth(v) + 1)，其中depth(v)
为节点v的深度。当然，这一算法还可进一步优化（习题[5-4]）。
在某些种类的二叉树（例如8.3节将要介绍的红黑树）中，高度的定义有所不同，因此这里
将updateHeight()定义为保护级的虚方法，以便派生类在必要时重写（override）。
