【文件属性】:
文件名称:事叉树节点模板类BinNode-web服务稳定性测试 负载测试 可靠性测试 测试报告
文件大小:10.35MB
文件格式:PDF
更新时间:2024-07-30 10:59:09
数据结构 邓俊辉 清华大学 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”的
约定相统一。