gogoWebsite

Judgment conditions

For a binary tree, if the data obtained by its in-order traversal is an ascending sequence, then it is a binary sorting tree.

Ideas

Add an additional ascending order judgment condition on the basis of the middle-order traversal recursive function: for any node under the middle-order traversal, if the data of the current node isGreater thanFor data from the previous node, the tree is a binary sorting tree; otherwise it is not.

Code

bool isBST(BT* root, int MAX)
{
	if (root == NULL) {//The empty tree is a binary sorting tree
		return true;
	}
	bool bst_l = isBST(root->lChild, MAX);//Judge whether the left subtree is a binary sorting tree

	//Is the data of the current node greater than the data of the previous node?
	if (!bst_l || MAX >= root->data) {
		return false;//No, the tree is not a binary sorting tree, returns false
	}
	MAX = root->data;//Yes, refresh the value of MAX and then continue to judge the next node in this way

	return isBST(root->rChild, MAX);//Judge whether the right subtree is a binary sorting tree
}

Note：

1. There is no "bool" type in C language, so the int type can be set to "0,1" instead of "true, false".
2. Use "INT_MIN" and "INT_MAX"Need additional introduction<>Head file.