二叉树判断同构的非递归算法

关键问题是解决怎么判断两个同为倒Y形状的二叉树同构

        A                        B

C            D          E            F

如上图，怎么判断这两棵同构？ 如果C在右边EF里面找到了同构，D再和EF的另一个匹配成功，就说明这两棵树同构。 实现：用栈存放两棵树上遍历指针指向的度均为2的节点，以及该节点下的子树(无分左右)被访问了几次，以及每次访问子树传回来的子树同构布尔值。这样，重复访问同一Y形节点就能区分开了，而且每一次访问子树都会向该Y形点传回bool，根据次数和bool就能很好的实现这种节点行为的 树状图(仔细一想，其实都是在围绕树状图展开，树状图需要什么，就增加对应的条件)

status is_omorphism2(BiTree t1, BiTree t2) {
	
	sqStack<::tuple<::tuple, sqStack>> sqs;
	initStack(sqs);
	::tuple traPtr = { t1,t2 };//遍历指针，允许为空
	::tuple<::tuple, sqStack> info;//用来接收栈顶节点信息，//size(关键节点的“访问栈”不允许退栈，容量等价访问次数)
	while ((t1 && t2) || !emptyStack(sqs)) {//这个scope里面执行一次有两种结果{继续向下挖，向上反馈结果}，向下挖的已经写好了，向上反馈的可以用一个bool承载信息，在本scope的末尾统一上传
		bool FEEDBACK;
		if (traPtr.A && traPtr.B) {
			if (traPtr.A->lChild && traPtr.A->rChild && traPtr.B->lChild && traPtr.B->rChild) {
				//两个遍历指针都各自有两个孩子
				if ((getSize(sqs) && getTop_withQuot(sqs).A.A != traPtr.A) || (!getSize(sqs))) {//第一次访问关键节点
					sqStack boolStack;
					initStack(boolStack);
					push(sqs, { traPtr,boolStack });
					traPtr = { traPtr.A->lChild,traPtr.B->lChild };
					continue;
				}
				getTop(sqs, info);//不同访问次数之间需要共享信息，使用栈堆叠
				if (getSize(info.B) == 1) {//第一次子树匹配返回
					if (getTop_withQuot(info.B)) {//右匹配右
						traPtr = { traPtr.A->rChild,traPtr.B->rChild };
						continue;
					}
					else {//左匹配右
						traPtr = { traPtr.A->lChild,traPtr.B->rChild };
						continue;
					}
				}
				if (getSize(info.B) == 2) {//第二次匹配返回，需要用到第一次返回的情况
					if (info.B.data[0]) {//第一次返回true
						if (info.B.data[1]) {//本关键点判断同构
							FEEDBACK = true;
						}
						else {//本关键点判断不同构
							FEEDBACK = false;
						}
					}
					else {
						if (info.B.data[1]) {//右左匹配
							traPtr = { traPtr.A->rChild,traPtr.B->lChild };
							continue;
						}
						else {//本关键点不同构
							FEEDBACK = false;
						}
					}
				}
				if (getSize(info.B) == 3) {
					if (info.B.data[2]) {//本关键点同构
						FEEDBACK = true;
					}
					else {//本关键点不同构
						FEEDBACK = false;
					}
				}
			}
			else if ((traPtr.A->lChild && traPtr.A->rChild) == 0 && (traPtr.B->lChild && traPtr.B->rChild) == 0 && (traPtr.A->lChild || traPtr.A->rChild) && (traPtr.B->lChild || traPtr.B->rChild)) {
				//两指针都各有一个孩子,遍历指针指向他们实际存在的孩子
				traPtr.A = traPtr.A->rChild;
				if (traPtr.A->lChild) {
					traPtr.A = traPtr.A->lChild;
				}
				traPtr.B = traPtr.B->rChild;
				if (traPtr.B->lChild) {
					traPtr.B = traPtr.B->lChild;
				}
				continue;
			}
			else if ((!traPtr.A->lChild) && (!traPtr.A->rChild) && (!traPtr.B->lChild) && (!traPtr.B->rChild)) {
				//两指针都没有孩子，返回本子树匹配正常
				FEEDBACK = true;
			}
			else {
				//向最近关键点返回本子树匹配异常
				FEEDBACK = false;
			}
		}
		else if (!(traPtr.A && traPtr.B) && (traPtr.A || traPtr.B)) {
			FEEDBACK = false;
		}
		else {
			FEEDBACK = true;
		}
//######根据上述code特点，可以把反馈的信号放在末尾一并处理
		if (getSize(sqs) > 2) {
			pop(sqs, info);
			push(getTop_withQuot(sqs).B, FEEDBACK);
			traPtr = { getTop_withQuot(sqs).A.A,getTop_withQuot(sqs).A.B };
			continue;
		}
		else
			return FEEDBACK;//整棵树同构
	}
	return FALSE;
}