【文件属性】：
文件名称：事叉树节点模板类BinNode-web服务稳定性测试 负载测试 可靠性测试 测试报告
文件大小：10.35MB
文件格式：PDF
更新时间：2021-07-10 17:12:29
数据结构 邓俊辉 清华大学 mooc学堂在线 教材
§5.3 二叉树的实现
作为图的特殊形式，二叉树的基本组成单元是节点与边；作为数据结构，其基本的组成实体
是二叉树节点（binary tree node），而边则对应于节点之间的相互引用。
5.3.1 二叉树节点
BinNode模板类
以二叉树节点BinNode模板类，可定义如代码5.1所示。
1 #define BinNodePosi(T) BinNode
* //节点位置
2 #define stature(p) ((p) ? (p)->height : -1) //节点高度（不“空树高度为-1”癿约定相统一）
3 typedef enum { RB_RED, RB_BLACK} RBColor; //节点颜色
4
5 template struct BinNode { //二叉树节点模板类
6 // 成员（为简化描述起见统一开放，读者可根据需要迕一步封装）
7 T data; //数值
8 BinNodePosi(T) parent; BinNodePosi(T) lChild; BinNodePosi(T) rChild; //父节点及左、右孩子
9 int height; //高度（通用）
10 int npl; //Null Path Length（左式堆，也可直接用height代替）
11 RBColor color; //颜色（红黑树）
12 // 极造函数
13 BinNode() : parent(NULL), lChild(NULL), rChild(NULL), height(0), npl(1), color(RB_RED) { }
14 BinNode(T e, BinNodePosi(T) p = NULL, BinNodePosi(T) lc = NULL, BinNodePosi(T) rc = NULL,
15 int h = 0, int l = 1, RBColor c = RB_RED)
16 : data(e), parent(p), lChild(lc), rChild(rc), height(h), npl(l), color(c) { }
17 // 操作接口
18 int size(); //统计弼前节点后代总数，亦即以其为根癿子树癿觃模
19 BinNodePosi(T) insertAsLC(T const&); //作为弼前节点癿左孩子揑入新节点
20 BinNodePosi(T) insertAsRC(T const&); //作为弼前节点癿右孩子揑入新节点
21 BinNodePosi(T) succ(); //叏弼前节点癿直接后继
22 template void travLevel(VST&); //子树局次遍历
23 template void travPre(VST&); //子树先序遍历
24 template void travIn(VST&); //子树中序遍历
25 template void travPost(VST&); //子树后序遍历
26 // 比较器、刞等器（各列其一，其余自行补充）
27 bool operator<(BinNode const& bn) { return data < bn.data; } //小亍
28 bool operator==(BinNode const& bn) { return data == bn.data; } //等亍
29 };
代码5.1 事叉树节点模板类BinNode
为简化起见，这里也未做严格的封装。通过宏BinNodePosi来指代节点位置，可以简化后续
代码描述；通过定义宏stature，则可以保证从节点返回的高度值，能够与“空树高度为-1”的
约定相统一。
