在节点类BinNode中添加插入节点函数
///***********插入孩子节点*******************************
/// 将数据e作为当前节点的左孩子或右孩子插入，并返回该节点指针
BinNodePosi(T) insertAsLC(T const&e)
{
return lc=new BinNode(e,this);
}
BinNodePosi(T) insertAsRC(T const&e)
{
return rc=new BinNode(e,this);
}
};
下面是节点类的源代码
#ifndef BINNODE #define BINNODE #include <iostream> //*************************************************************************************** ///代码5.2 ， BinNode状态与性质的判断 ///一、 判断该节点是什么！ /// 是否是根节点、是否是左子节点、是否是右子节点、是否是叶节点 #define isRoot(x) (!((x).parent)) #define isLChild(x) (!isRoot(x)&&(&(x)==(x).parent->lc)) //不是根节点，同时必须是父节点的左孩子 #define isRChild(x) (!isRoot(x)&&(&(x)==(x).parent->rc)) //不是根节点，同时必须是父节点的右孩子 ///二、判断该节点有什么 //判断是否有孩子 #define hasLChild(x) ((x).lc!=NULL) //判断节点x是否有左孩子 #define hasRChild(x) ( (x).rc ) //判断节点x 是否有右孩子 #define hasChild(x) ( hasLChild(x)||hasRChild(x)) //判断节点x是否有孩子（左、右至少有一个） //判断是否为叶节点 #define isLeaf(x) ( !hasChild(x) ) //判断节点x是否是叶子节点 //**************************************************************************************** #define BinNodePosi(T) BinNode<T>* //节点位置 typedef enum{RB_RED,RB_BLACK} RBColor;//节点颜色 template <typename T> class BinNode { public: T data;//数值 int height; int npl;//Null Path Length(左式堆，也可直接用height代替) RBColor color; BinNodePosi(T) parent;//父节点 BinNodePosi(T) lc;//左子节点 BinNodePosi(T) rc;//右子节点 //构造函数 BinNode():parent(NULL),lc(NULL),rc(NULL),height(0),npl(1),color(RB_RED){} BinNode(T e,BinNodePosi(T) p=NULL,BinNodePosi(T) lc=NULL,BinNodePosi(T) rc=NULL, int h=0,int l=1,RBColor c=RB_RED) { data=e; parent=p; this->lc=lc,this->rc=rc;//此处添加this指针，以便将成员变量lc、rc与形参lc和rc区分 height=h; npl=l; color=c; } ///***********插入孩子节点******************************* /// 将数据e作为当前节点的左孩子或右孩子插入，并返回该节点指针 BinNodePosi(T) insertAsLC(T const&e) { return lc=new BinNode(e,this); } BinNodePosi(T) insertAsRC(T const&e) { return rc=new BinNode(e,this); } }; #endif // BINNODE
下面是用于测试的main（）函数：
#include <iostream> #include <binnode.h> #include <string> using namespace std; //1、测试根节点函数isRoot void testRoot(BinNode<string> &node) { if(isRoot(node)) cout<<node.data<<" is root!"<<endl; else cout<<node.data<<" is not a root!"<<endl; } //2、测试左孩子函数isLChild void testLChild(BinNode<string> &node) { if(isLChild(node)) cout<<node.data<<" is "<<node.parent->data<<"'s left child!"<<endl; else cout<<node.data<<" is not left child!"<<endl; } //3、测试右孩子函数isRChild void testRChild(BinNode<string> &node) { if(isRChild(node)) cout<<node.data<<" is "<<node.parent->data<< "'s right child!"<<endl; else cout<<node.data<<" is not right child!"<<endl; } //4、测试是否有左孩子函数 void testHasLChild(BinNode<string> &node) { if(hasLChild(node)) cout<<node.data<<" has a left child: "<<endl; else cout<<node.data<<" has not left child!"<<endl; } //4、测试是否有右孩子函数 void testHasRChild(BinNode<string> &node) { if(hasRChild(node)) cout<<node.data<<" has a right child: "<<endl; else cout<<node.data<<" has not right child!"<<endl; } //5、测试是否是叶节点函数isLeaf（） void testLeaf(BinNode<string> &node) { if(isLeaf(node)) cout<<node.data<<" is "<<node.parent->data<< "'s leaf!"<<endl; else cout<<node.data<<" is not leaf"<<endl; } int main() { BinNode<string>* n[4];//数组指针 //2、将n2设定为n1的左节点，测试isLChild()函数 //创建n1与n2之间的父子关系 n[1]=new BinNode<string>("node1");//创建节点1 n[2]=n[1]->insertAsLC("node2"); testLChild(*n[2]); //3、将n3设定为n1的右节点，测试isRChild()函数 //创建n1、n3之间的父子关系 n[3]=n[1]->insertAsRC("node3"); testRChild(*n[3]); //4、测试n1是否有左孩子 testHasLChild(*n[1]); //5、测试n1是否有右孩子 testHasRChild(*n[1]); return 0; }
下面是运行结果：
