将二叉排序樹轉化成雙連結清單

跟中序周遊原理一樣，隻要修改通路操作即可，下面提供遞歸與非遞歸方法：

bool bt2list(Tree *root, Tree ** head, Tree **tail, bool *sethead) {
	if (root == NULL)
		return false;
	if (root->left != NULL)
		tr2list(root->left, head, tail, sethead);
	if (*sethead == false) {
		*head = root;
		*tail = root;
		*sethead = true;
	} else {
		(*tail)->right = root;
		root->left = *tail;
		*tail = root;
	}
	if (root->right != NULL)
		tr2list(root->right, head, tail, sethead);
	return true;
}

bool bt2list(Tree *root, Tree **head, Tree **tail) {
	if (root == NULL)
		return false;
	Tree *cur = root;
	stack<Tree*> stk;
	while (cur != NULL) {
		stk.push(cur);
		cur = cur->left;
	}
	bool isHeadSeted = false;
	while (!stk.empty()) {
		cur = stk.top();
		if (!isHeadSeted) {
			isHeadSeted = true;
			*head = cur;
			*tail = cur;
		} else {
			(*tail)->right = cur;
			cur->left = *tail;
			(*tail) = (*tail)->right;
		}
		stk.pop();
		if (cur->right != NULL) {
			cur = cur->right;
			while (cur != NULL) {
				stk.push(cur);
				cur = cur->left;
			}
		}
	}
	return true;
}