二叉排序树相关算法

typedef struct TreeNode {
	int data = 0;
	TreeNode* lchild = nullptr;
	TreeNode* rchild = nullptr;
} TreeNode, * BiTree;

BiTree buildBST(void)
{
	std::cout << "A binary search tree (BST) is being built. " << std::endl;
	std::cout << "Enter data in the node after prompting, " << std::endl;
	std::cout << "or enter any non-digit character except whitespaces to exit. " << std::endl << std::endl;

	BiTree result = nullptr;
	TreeNode* mov = nullptr;
	TreeNode* newNode = nullptr;
	TreeNode* tempLink = nullptr;
	int cache = 0;

	// fill in root;
	if (scanf("%d", &cache) == 1) {
		result = new TreeNode;
		result->data = cache;
	}
	else {
		return nullptr;
	}

	while (scanf("%d", &cache) == 1) {
		newNode = new TreeNode;
		newNode->data = cache;

		mov = result;
		while (mov->data != cache) {
			if (cache < mov->data) {
				if (mov->lchild == nullptr) {
					mov->lchild = newNode;
				}
				mov = mov->lchild;
			}
			else if (cache > mov->data) {
				if (mov->rchild == nullptr) {
					mov->rchild = newNode;
				}
				mov = mov->rchild;
			}
		}

		// Notice that mov->data == cache is not an appropriate condition here, 
		// because this will be satified in the end no matter cache is a new value or not; 
		// Better solution is to compare the address of leaf and newNode; 
		if (mov != newNode) {
			delete newNode; // omit values that already exist in the BST; 
		}
	}

	return result;
}

static bool isBST_buildin(BiTree tree, int& maxElem)
{
	// For empty tree, return true; 
	if (tree == nullptr) {
		maxElem = INT_MIN; 
		return true; 
	}

	// Now tree != nullptr; 
	bool result = true;
	// If lchild tree exists; 
	if (tree->lchild != nullptr) {
		// If lchild tree is not BST, return false; 
		if (!(result = isBST_buildin(tree->lchild, maxElem))) {
			return result;
		}
		// Now lchild tree is BST; 
		// Now maxElem is the max element of lchild tree; 
		// If cur node data is not greater than max data of lchild tree, return false; 
		if (!(result = tree->data > maxElem)) {
			return result;
		}
	}
	else {
		maxElem = tree->data; 
	}
	// If rchild tree exists; 
	if (tree->rchild != nullptr) {
		// If rchild tree is not BST, return false; 
		if (!(result = isBST_buildin(tree->rchild, maxElem))) {
			return result;
		}
		// Now rchild tree is BST; 
		// Now maxElem is the max element of rchild tree, 
		// which is also the max element of cur node tree; 
		// If cur node data is not less than max data of rchild tree, return false; 
		if (!(result = tree->data < maxElem)) {
			return result;
		}
	}
	else {
		maxElem = tree->data;
	}

	// Now pass the examination, return true; 
	// Now maxElem is the max element of cur node tree; 
	return result; 
}

bool isBST(BiTree tree)
{
	int maxElem = INT_MIN; 

	return isBST_buildin(tree, maxElem); 
}

#include <stack>

using std::stack; 

bool isBST(BiTree tree)
{
	if (tree == nullptr) { // empty tree;
		return true;
	}

	stack<TreeNode*> stk = {};
	TreeNode* mov = tree;
	TreeNode* pred = nullptr; 

	while (!stk.empty() || mov != nullptr) {
		if (mov != nullptr) {
			stk.push(mov);
			mov = mov->lchild;
		}
		else { // the current nullptr node is not in the stack yet;
			mov = stk.top();

			/* visit node */
			if (pred != nullptr) {
				if (pred->data >= mov->data) {
					return false; 
				}
			}
			pred = mov; 

			mov = mov->rchild;
			stk.pop();
		}
	}

	return true;
}

bool delBSTNode(BiTree tree, int value)
{
	if (tree == nullptr) {
		return false;
	}
	if (tree->data == value) {
		printf("This function cannot deal with root deleting. \n");
		return false;
	}

	// Now tree != nullptr;
	TreeNode* mov = tree;
	TreeNode* cache = tree; // temporary cache for parent; 
	// Find node with data value;
	while (mov != nullptr && mov->data != value) {
		cache = mov;
		mov = (mov->data > value ? mov->lchild : mov->rchild);
	}
	if (mov == nullptr) { // Target node not found;
		return false;
	}

	// Now mov->data == value;
	// Check children of mov and operate accordingly;
	if (mov->lchild == nullptr && mov->rchild == nullptr) {// leaf;
		// delete directly and done;
		if (cache->lchild == mov) {
			cache->lchild = nullptr;
		}
		else {
			cache->rchild = nullptr; 
		}

		delete mov;
	}
	// Now not both children are nullptr;
	else if (mov->lchild == nullptr) {// i.e. rchild != nullptr;
		if (cache->lchild == mov) {
			cache->lchild = mov->rchild;
		}
		else {
			cache->rchild = mov->rchild;
		}

		delete mov;
	}
	else if (mov->rchild == nullptr) {// i.e. lchild != nullptr;
		if (cache->lchild == mov) {
			cache->lchild = mov->lchild;
		}
		else {
			cache->rchild = mov->lchild;
		}

		delete mov;
	}
	// Now neither of its children is nullptr;
	// Copy the value of inorder-successor of mov to mov's place;
	// Then delete this inorder-successor; 
	else {
		// Find inorder-successor;
		cache = mov->rchild; 
		while (cache->lchild != nullptr) {
			cache = cache->lchild;
		}
		// Do not update mov->data here,
		// since delBSTNode(mov, cache->data) have to find the successor by value;
		int temp = cache->data;
		delBSTNode(mov, cache->data);

		// Now update mov->data;
		mov->data = temp; 
	}

	return true; 
}