What are the characteristics of a binary search tree?

The characteristic of a binary search tree is that for each node X in the tree, all key values ​​in its left subtree are less than the key value of X, and all key values ​​in its right subtree Keyword value greater than

Characteristics of binary search trees

Characteristics of binary search trees: For the For each node X, all key values ​​in its left subtree are less than the key value of X, and all key values ​​in its right subtree are greater than the key value of X.

According to this property, if an in-order traversal is performed on a binary tree, if it is monotonically increasing, it can be said that the tree is a binary search tree.

Binary search tree search

Process: First compare with the root node, and if it is equal to the root node, return. If it is less than the root node, search in the left subtree of the root node. If it is greater than the root node, search in the right subtree of the root node.

/* 查找以t为根节点的树中，是否包含x */
Position Find(ElementType x, SearchTree t)
{
    if (t == NULL) {
        return NULL;
    } else if (x < t->element) {
        return Find(x, t->left);
    } else if (x > t->element) {
        return Find(x, t->right);
    } else {
        return t;
    }
}

The above is the detailed content of What are the characteristics of a binary search tree?. For more information, please follow other related articles on the PHP Chinese website!