二叉树相关算法

TreeNode* ancestor(BiTree tree, TreeNode* p, TreeNode* q)
{
	if (tree == nullptr) {
		return nullptr;
	}

	#define PUSHSTK do { top = new stackNode; top->tnode = mov; top->next = stk->next; stk->next = top; } while (0)

	typedef struct stackNode {
		TreeNode* tnode = nullptr;
		stackNode* next = nullptr;
	} stackNode, *stack;

	stack stk = new stackNode; // header of stk;
	TreeNode* rtag = nullptr;
	TreeNode* mov = tree;

	stackNode* top = nullptr;

	// these two are actually not stack,
	// since comparison will be made sequentially these stackNode arrays;
	stack pstk = new stackNode;
	stack qstk = new stackNode;
	stackNode* cachemov = nullptr;
	stackNode* cache = nullptr;

	while (stk->next != nullptr || mov != nullptr) {
		if (mov != nullptr) {
			PUSHSTK;
			mov = mov->left;
		}
		else {
			mov = top->tnode;
			if (mov->right != nullptr && mov->right != rtag) {
				mov = mov->right;
			}
			else {
				/* visit node */
				// inverse the original stack for faster comparison later;
				if (pstk->next != nullptr && qstk->next != nullptr) {
					break;
				}

				if (mov == p) {
					cachemov = top;
					while (cachemov != nullptr) {
						cache = new stackNode;
						cache->tnode = cachemov->tnode;
						cache->next = pstk->next;
						pstk->next = cache;

						cachemov = cachemov->next;
					}
				}
				// caution that this should not be elseif,
				// as p == q is possible;
				if (mov == q) {
					cachemov = top;
					while (cachemov != nullptr) {
						cache = new stackNode;
						cache->tnode = cachemov->tnode;
						cache->next = qstk->next;
						qstk->next = cache;

						cachemov = cachemov->next;
					}
				}

				// update rtag;
				rtag = mov;

				// pop stk;
				stk->next = top->next;
				delete top;
				top = stk->next;
				// enforcing next check to top of stack;
				mov = nullptr;
			}
		}
	}

	// if p or q does not exist;
	if (pstk->next == nullptr || qstk->next == nullptr) {
		return nullptr;
	}

	// use top, cache and cachemov as probes;
	top = pstk;
	cache = pstk->next;
	cachemov = qstk->next;
	while (cache != nullptr && cachemov != nullptr && (cache->tnode == cachemov->tnode)) {
		top = top->next;
		cache = cache->next;
		cachemov = cachemov->next;
	}

	return top->tnode;
}

BiTree recCopyBiTree(BiTree src)
{
	BiTree result = nullptr;

	if (src != nullptr) {
		result = new TreeNode;
		result->data = src->data;
		result->lchild = recCopyBiTree(src->lchild);
		result->rchild = recCopyBiTree(src->rchild);
	}

	return result;
}

BiTree copyBiTree(BiTree src)
{
	if (src == nullptr) {
		return nullptr;
	}

	BiTree result = new TreeNode;

	typedef struct stackNode {
		TreeNode* tnode = nullptr;
		stackNode* next = nullptr;
	} stackNode, *stack;

	#define STKPUSH(m_stk, m_topcache, m_tnode) do { m_topcache = new stackNode; m_topcache->tnode = m_tnode; m_topcache->next = m_stk->next; m_stk->next = m_topcache; } while (0)
	
	#define SRCSTKPUSH(m_tnode) STKPUSH(stkSrc, topSrc, m_tnode)
	
	#define TARSTKPUSH(m_tnode) STKPUSH(stkTar, topTar, m_tnode)

	
	#define STKPOP(m_stk, m_topcache) do { m_stk->next = m_topcache->next; delete m_topcache; m_topcache = m_stk->next; } while (0)
	
	#define SRCSTKPOP STKPOP(stkSrc, topSrc)
	
	#define TARSTKPOP STKPOP(stkTar, topTar)

	stack stkSrc = new stackNode;
	stackNode* topSrc = nullptr;

	stack stkTar = new stackNode;
	stackNode* topTar = nullptr;

	TreeNode* movSrc = src;
	TreeNode* movTar = result;
	while (stkSrc->next != nullptr || movSrc != nullptr) {
		if (movSrc != nullptr) {
			SRCSTKPUSH(movSrc);

			/* visit node */
			movTar->data = movSrc->data;
			TARSTKPUSH(movTar);

			movSrc = movSrc->lchild;
			if (movSrc != nullptr) {
				movTar->lchild = new TreeNode;
				movTar = movTar->lchild;
			}
		}
		else {
			movSrc = topSrc->tnode->rchild;
			SRCSTKPOP;
			movTar = topTar->tnode;
			if (movSrc != nullptr) {
				movTar->rchild = new TreeNode;
				movTar = movTar->rchild;
			}
			TARSTKPOP;
		}
	}

	return result;
}