tree23node.h

2-3树的数据结构以及演示程序

#pragma once

template <class TYPE>
class Tree23Node
{
protected:
	char *name;					//结点名称
	TYPE *data;					//结点数据域
	TYPE *lmax;					//左子树最大结点值
	TYPE *mmax;					//中子树最大结点值
	TYPE *rmax;					//右子树最大结点值，也是整棵树的最大结点值
	Tree23Node <TYPE> *lchild;	//左子树指针
	Tree23Node <TYPE> *mchild;	//中子树指针
	Tree23Node <TYPE> *rchild;	//右子树指针
	Tree23Node <TYPE> *parent;	//父结点指针

public:
	//构造函数
	Tree23Node(
		TYPE *_data = NULL,
		Tree23Node <TYPE> *_lchild = NULL,
		Tree23Node <TYPE> *_mchild = NULL,
		Tree23Node <TYPE> *_rchild = NULL,
		Tree23Node <TYPE> *_parent = NULL,
		TYPE *_lmax = NULL,
		TYPE *_mmax = NULL,
		TYPE *_rmax = NULL,
		char *_name = NULL
	) {
		name = _name;
		if (name == NULL) {
			name = new char[1];
			name[0] = '\0';
		}
		data = _data;
		lchild = _lchild;
		rchild = _rchild;
		mchild = _mchild;
		parent = _parent;
		lmax = _lmax;
		mmax = _mmax;
		rmax = _rmax;
	}
	//析构函数
	void Destroy(void) {
		cout<<"Destructing Tree23Node"<<endl;
		delete name;
		cout<<"Destructing Tree23Node complete"<<endl;
	}
	//判断是否小于
	bool IsBelow(Tree23Node <TYPE> *b) {
		if (b == NULL) return false;
		else if (*data < *b->GetData()) return true;
		else return false;
	}
	bool IsBelow(TYPE *b) {
		if (b == NULL) return false;
		else if (*data < *b) return true;
		else return false;
	}
	//获得左子树最大结点值
	TYPE *GetLMax(void) {
		if (IsLeaf()) return data;
		else return lmax;
	}
	//获得中子树最大结点值
	TYPE *GetMMax(void) {
		if (IsLeaf()) return data;
		else return this->mmax;
	}
	//获得右子树最大结点值
	TYPE *GetRMax(void) {
		if (IsLeaf()) return data;
		return rmax;
	}
	//获得数据域
	TYPE *GetData() {
		return this->data;
	}
	//设置父结点
	void SetParent(Tree23Node <TYPE> *p) {
		parent = p;
	}
	//判断本结点是否为叶子结点
	bool IsLeaf() {
		if (lchild == NULL && mchild == NULL && rchild == NULL) return true;
		else return false;
	}
	//判断本结点是否为叶子的直接父结点
	bool IsLeafFather() {
		if (!IsLeaf())
			if (lchild->IsLeaf()) return true;
		return false;
	}
	//判断本结点是否是根结点
	bool IsRoot() {
		if (parent == NULL) return true;
		else return false;
	}
	//在本树中搜索和参数d相同的结点，返回NULL表示没有找到
	Tree23Node <TYPE> *Search(TYPE *d) {
		//cout<<"Searching..."<<endl;
		//if (data != NULL) cout<<"Current node: "<<*data<<endl;
		if (IsLeaf()) {
			if (*data == *d) return this;
			else return NULL;
		}
		else if (*d <= *lmax) return lchild->Search(d);
		else if (*d <= *mmax) return mchild->Search(d);
		else if (rchild != NULL) return rchild->Search(d);
		else return NULL;
	}
	Tree23Node <TYPE> *Search(Tree23Node <TYPE> *node) {
		if (IsLeaf()) {
			if (*data == *node->GetData()) return this;
			else return NULL;
		}
		else if (node->IsBelow(lmax)) return lchild->Search(node);
		else if (node->IsBelow(mmax)) return mchild->Search(node);
		else return rchild->Search(node);
	}

	//删除以本结点为根的子树
	void DelTree() {
		if (lchild != NULL) lchild->DelTree();
		if (mchild != NULL) mchild->DelTree();
		if (rchild != NULL) rchild->DelTree();
		this->Destroy();
	}
	//在本树中插入一个结点，返回新的根结点指针.返回空指针表示根结点没有改变。
	Tree23Node <TYPE> *InsertNode(Tree23Node <TYPE> *node) {
		Tree23Node <TYPE> *root = NULL;
		//如果是叶子结点
		if (IsLeaf()) {
			//如果既是叶子结点是根结点
			if (IsRoot()) {
				if (node->IsBelow(this)) root = new Tree23Node <TYPE> (NULL, node, this, NULL, NULL, node->GetData(), this->GetData(), this->GetData());
				else root = new Tree23Node <TYPE> (NULL, this, node, NULL, NULL, this->GetData(), node->GetData(), node->GetData());
				node->SetParent(root);
				this->SetParent(root);
			}
			//如果是叶子结点但不是根结点
			else root = this->parent->InsertTree(node);
		}
		//如果该插在左子树上
		else if (node->IsBelow(GetLMax())) root = lchild->InsertNode(node);
		//如果该插在中子树上
		else if (node->IsBelow(GetMMax()) || rchild == NULL) root = mchild->InsertNode(node);
		//如果该插在右子树上
		else root = rchild->InsertNode(node);

		return root;
	}
	//在本树中插入一棵子树
	Tree23Node <TYPE> *InsertTree(Tree23Node <TYPE> *node) {
		//如果当前结点未满三个子树，那么就在此结点上插入
		if (rchild == NULL) {
			if (*node->GetRMax() < *lchild->GetRMax()) {
				rchild = mchild;
				mchild = lchild;
				lchild = node;
				node->SetParent(this);
				rmax = mmax;
				mmax = lmax;
				lmax = node->GetRMax();
			}
			else if (*node->GetRMax() < *mchild->GetRMax()) {
				rchild = mchild;
				mchild = node;
				node->SetParent(this);
				lmax = lchild->GetRMax();
				rmax = mmax;
				mmax = node->GetRMax();
			}
			else {
				rchild = node;
				node->SetParent(this);
				lmax = lchild->GetRMax();
				mmax = mchild->GetRMax();
				rmax = node->GetRMax();
			}
			return NULL;
		}
		//如果当前结点已满三棵子树，那么就两两拆开，把左半子树接于当前结点，右半交付于上一层父结点重新插入
		else {
			Tree23Node <TYPE> *temp;
			Tree23Node <TYPE> *root;
			if (*node->GetRMax() < *lchild->GetRMax()) {
				temp = new Tree23Node <TYPE> (NULL, mchild, rchild, NULL, NULL, mchild->GetRMax(), rchild->GetRMax(), rchild->GetRMax(), NULL);
				mchild->SetParent(temp);
				rchild->SetParent(temp);
				mchild = lchild;
				lchild = node;
				rchild = NULL;
				node->SetParent(this);
				lmax = node->GetRMax();
				rmax = mmax = lmax;
			}
			else if (*node->GetRMax() < *mchild->GetRMax()) {
				temp = new Tree23Node <TYPE> (NULL, mchild, rchild, NULL, NULL, mchild->GetRMax(), rchild->GetRMax(), rchild->GetRMax(), NULL);
				mchild->SetParent(temp);
				rchild->SetParent(temp);
                mchild = node;
				rchild = NULL;
				node->SetParent(this);
				mmax = rmax = node->GetRMax();
			}
			else {
				if (*node->GetRMax() < *rchild->GetRMax())
					temp = new Tree23Node <TYPE> (NULL, node, rchild, NULL, NULL, node->GetRMax(), rchild->GetRMax(), rchild->GetRMax(), NULL);
				else temp = new Tree23Node <TYPE> (NULL, rchild, node, NULL, NULL, rchild->GetRMax(), node->GetRMax(), node->GetRMax(), NULL);
				rchild->SetParent(temp);
				node->SetParent(temp);
				rmax = mmax;
				rchild = NULL;
			}

			//如果当前结点是根结点，那么新建一结点作为根结点
			if (IsRoot()) {
				root = new Tree23Node <TYPE> (NULL, this, temp, NULL, NULL, this->GetRMax(), temp->GetRMax(), 0, NULL);
				this->parent = root;
				temp->SetParent(root);
			}
			//否则把右半树交给父结点处理
			else root = parent->InsertTree(temp);

			return root;
		}
	}
	//打印当前结点信息
	void ShowNode() {
		cout<<*data<<"\t";
	}
	//打印当前结点为根的树
	void ShowTree() {
		if (IsLeaf()) ShowNode();
		else {
			if (lchild != NULL) lchild->ShowTree();
			if (mchild != NULL) mchild->ShowTree();
			if (rchild != NULL) rchild->ShowTree();
		}
	}
	//树型打印本结点为根的子树
	void formatPrint(bool isEnd, char *prefix) {
		if (!this->IsRoot()) {
			cout<<prefix;
			if (!isEnd) cout<<"├";
			else cout<<"└";
		}

		if (IsLeaf()) cout<<"键值："<<*data<<endl;
		else cout<<"左子树最大值："<<*lmax<<"\t中子树最大值："<<*mmax<<endl;
        
		char *nextPrefix = new char[strlen(prefix) + 1];
		strcpy(nextPrefix, prefix);

		if (isEnd || IsRoot()) strcat(nextPrefix, "  ");
		else strcat(nextPrefix, "│");

		if (lchild) lchild->formatPrint(!mchild, nextPrefix);
		if (mchild) mchild->formatPrint(!rchild, nextPrefix);
		if (rchild) rchild->formatPrint(true, nextPrefix);
	}
};