事叉树节点模板类BinNode-web服务稳定性测试 负载测试 可靠性测试 测试报告

时间:2024-07-30 10:59:09
【文件属性】:

文件名称:事叉树节点模板类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”的 约定相统一。


网友评论