ege库基于前中后序动态建立二叉树、序列检错以及查找公共父节点C++

2023-11-07

一、需求分析

1、任意输入前序 + 中序序列或者中序 + 后序序列，生成二叉树
3、利用打印二叉树功能显示二叉树的逐步构造过程,使用自上而下的二叉树显示
4、使用EGE(xege.org) / SFML(www.sfml - dev.org / download / sfml / 2.5.1 / )库进行可视化
5、使用三叉链表，在构造链表的过程中同步更新每个节点的parent指针
6、输入两个节点值找到共同祖先
7、检测输入的前序，中序，后续序列的有效性例如当用户输入错误的序列时，程序应该有错误提示并构造二叉树至出错前状态

二、详细设计(均以前中序建树为例)

(1)节点的定义

template <class T>
struct BTNode
{
	T data;
	int depth;//depth of a node
	BTNode<T> *lchild, *rchild, *parent;
	BTNode() :lchild(NULL), rchild(NULL), parent(NULL) {}
	BTNode(T x, int a = 0, int b = 0, BTNode<T> *l = NULL, BTNode<T> *r = NULL, BTNode<T> *p = NULL)
		:data(x), depth(b), lchild(l), rchild(r), parent(p) {}
};

template <class T>
class BT {
protected:
	BTNode<T>* root;
public:
	BT() :root(NULL) {}
	~BT() { destory(root); }
	void destory(BTNode<T>*& tree);
	BTNode<T>* GetRoot() { return root; }//get the address of the root node
	BTNode<T>* getParent(BTNode<T>* tree) { return tree->parent; }
	BTNode<T>* creatreeVVR(char* VLR, char* LVR, int size, BTNode<T>*& tree, BTNode<T>* &temptree,
		double x0, double y0, double x, double y, int n);//establish binary tree in preorder and inorder
	BTNode<T>* creatreeLVV(char* LVR, char* LRV, int size, BTNode<T>*& tree, BTNode<T>* &temptree,
		double x0, double y0, double x, double y, int n);//establish binary tree in inorder and preorder
	BTNode<T>* SearchNode(BTNode<T>* &tree, T data);//get the address by the a value T
	BTNode<T>* SearchParentNode(BTNode<T>* &tree, T data);
	char comparent(BTNode<T>* tree1, BTNode<T>* tree2);//get the value of two node's common ancestor
	int getDepth(BTNode<T>* tree);//get the depth of a node
	void PrintVLR(BTNode<T>* tree);
	void PrintLVR(BTNode<T>* tree);
	void PrintLRV(BTNode<T>* tree);
	friend int main();
};

(2)前序和中序的检错

检错的第一个组成部分：检查a序列的元素是否在b中都存在以及b序列的元素是否在a中都存在

通过使用\0，来控制只对前k个元素操作

bool errorDetectionRecursion(char* a, char* b, int size)
{
	char temp;
	for (int i = 0; i < size; i++) {//strchr:在一个串中查找给定字符的第一个匹配之处 函数原型为：char *strchr(const char *str, int c)
		temp = b[size];
		b[size] = '\0';
		if (!strchr(b, a[i])) {
			cerr << "序列错误\n";
			return 0;//序列有错则直接返回，将序列截断在出错之处，从而达到构造二叉树到出错之前的状态
		}
		b[size] = temp;
	}
	for (int i = 0; i < size; i++) {
		temp = a[size];
		a[size] = '\0';
		if (!strchr(a, b[i])) {
			cerr << "序列错误\n";//序列无错则将\0处的元素还原
			return 0;
		}
		a[size] = temp;
	}
	return 1;
}

检错的第二个组成部分：通过递归和调用第一个检错函数，对整个序列进行检错

bool errorDetectionVVR(char* VLR, char* LVR, int size)
{
	if (size <= 0) return 1;
	//如果两个序列元素一致，就对比其左右子树
	if (errorDetectionRecursion(VLR, LVR, size))
	{
		int k = 0;
		while (VLR[0] != LVR[k])k++;
		//对比左子树两个序列元素
		//从前序的左子树开始，前序的左子树从第k+1个元素开始，中序的左子树在前k个元素位上
		if (errorDetectionVVR(VLR + 1, LVR, k))
		{//如果左子树两个序列元素相同，继续比较右子树
		 //前序的右子树从第k+2位开始，共size-k-1位
         //中序的右子树从第k+2位开始，共size-k-1位
			if (errorDetectionVVR(VLR + k + 1, LVR + k + 1, size - k - 1))
				return 1;//右子树也相同，返回1
			else return 0;//右子树两个序列不同，返回0
		}
		else return 0;//如果左子树两个序列元素不同，返回0
	}
	else return 0;//如果两个序列元素不同，返回0
}

思路来自于一位大佬,代码有所简化

(3)前序和中序的建树

参数BTNode<T>* &temptree用于同步更新parent指针

template<class T>
BTNode<T>*BT<T>::creatreeVVR(char* VLR, char* LVR, int size, BTNode<T>* &tree, BTNode<T>* &temptree,
	double x0, double y0, double x, double y, int n)
//传入的参数分别为：前序中序序列，目标树的根节点，辅助建树的树的节点，ege库函数里节点的当前x，y坐标，节点的下一次递归的x，y坐标
{
	if (size <= 0)return NULL;
	tree = new BTNode<T>(*VLR);//VLR[0]
	tree->parent = temptree;
	//ege操作
	setcaption("以前序和中序创建二叉树");
	initgraph(700, 500/*, INIT_WITHLOGO*/);//初始化图形界面
	setfont(20, 0, "微软雅黑");
	setbkcolor(WHITE);	//设置背景为白色
	//movewindow(800, 300, true);//罪恶之源
	setcolor(RED);
	circle(x, y, 22);//画圈
	setcolor(BLACK);
	outtextxy(x, y, tree->data);//outtextxy不支持\t \n这类格式化用的特殊字符//要使用特殊格式化字符请用outtextrect
	Sleep(30);//delay_ms(0);
	line(x0, y0, x, y);
	Sleep(150);//Sleep(300);
	//利用pow函数，每一次递归，都能得到不同的且合适的节点的x坐标，y坐标每次下沉100
	int t = pow(2, n);//1
	int x1 = x - 400 / t;
	int x2 = x + 400 / t;
	//找根节点
	int k = 0;
	while (VLR[0] != LVR[k]) {
		k++;
		if (k > size - 1) {//when the sequence is wrong, avoid entering the dead loop of k++
			system("pause");
		}
	}
	creatreeVVR(VLR + 1, LVR, k, tree->lchild, tree,
		x, y, x1, 100.0 * n, n + 1);
	//从前序的左子树开始，前序的左子树从第k+1个元素开始，中序的左子树在前k个元素位上
	creatreeVVR(VLR + 1 + k, LVR + 1 + k, size - 1 - k, tree->rchild, tree,
		x, y, x2, 100.0 * n, n + 1);
	//前序的右子树从第k+2位开始，共size-k-1位
    //中序的右子树从第k+2位开始，共size-k-1位
}

(4)查找共同祖先(父节点)

算法思路:

需要先设计一个按值搜索节点的函数BTNode<T>* BT<T>::SearchNode(BTNode<T>* &tree, T data)得到两个节点的地址

再设计一个由两个节点找出其公共父节点的函数char BT<T>::comparent(BTNode<T>* tree1, BTNode<T>* tree2)

问题等价于：查找两个链表的交叉（相同）元素

则需要知道两个节点的深度，所以还需要一个获取节点深度的函数int BT<T>::getDepth(BTNode<T>* tree)

1)SearchNode函数

template<class T>
BTNode<T>* BT<T>::SearchNode(BTNode<T>* &tree, T data)
{
	if (tree == NULL) return NULL;
	BTNode<T>* pTemp = NULL;
	if (tree->data == data) pTemp = tree;
	else {
		if (!pTemp) pTemp = SearchNode(tree->lchild, data);//递归到左子树
		if (!pTemp) pTemp = SearchNode(tree->rchild, data);
	}
	return pTemp;
}

2)getDepth函数

template<class T>
int BT<T>::getDepth(BTNode<T>* tree)
{
	int depth = 0;
	BTNode<T>* pTemp = tree;
	while (pTemp)
	{
		depth++;
		pTemp = pTemp->parent;//不断往上寻找父节点
	}
	return depth;
}

3)Comparent函数

template<class T>
char BT<T>::comparent(BTNode<T>* tree1, BTNode<T>* tree2)
{
	int length1 = getDepth(tree1);
	int length2 = getDepth(tree2);
	BTNode<T>* p1 = tree1;
	BTNode<T>* p2 = tree2;
	int oversize = length1 - length2;
	//为了始终让p1指向更深的节点
	if (length1 < length2) {
		oversize = length2 - length1;
		p1 = tree2;
		p2 = tree1;
	}
//需要等更深的节点上移oversize个节点之后
//两个节点才一起移动
	for (int i = 0; i < oversize; i++)
		p1 = p1->parent;
//中止条件包括p1、p2相遇时
	while (p1&&p2&&p1 != p2)
	{
		p1 = p1->parent;
		p2 = p2->parent;
	}
	return p1->data;//返回共同父节点的值
}

三、注意事项

ege库安装网站:xege.org

建树过程使用了ege库,需要在头文件里include

需要提前#define SHOW_CONSOLE,否则控制台黑窗口可能被禁用

Ps：由于本人才疏学浅，错误纰漏之处在所难免，如果您在阅读的过程中发现了文章的错误和不足，欢迎交流学习与指正。

附完整代码：

BinaryTree.rar-C/C++文档类资源-CSDN下载

内置ege的版本：

ege库基于前中后序动态建立二叉树源码(内附ege)-以太坊资源-CSDN下载

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)