Data Structures Algorithms 简明教程
Binary Search Tree
二叉查找树（BST）是其中所有节点都符合以下所述属性的树——
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −
-
The left sub-tree of a node has a key less than or equal to its parent node’s key.
-
The right sub-tree of a node has a key greater than or equal to its parent node’s key.
因此，BST 将其所有子树划分为两个部分；左子树和右子树，并且可以定义为——
Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)Binary Tree Representation
BST 是按照可以维持 BST 属性的方式排列的一组节点。每个节点都有一个键和一个相关值。在搜索时，将所需的键与 BST 中的键比较，如果找到，则检索相关值。
BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.
以下是 BST 的图像表示——
Following is a pictorial representation of BST −
我们观察到，根节点键（27）在左子树上具有所有值较小的键，在右子树上具有值较大的键。
We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.
Basic Operations
以下是二叉搜索树的基本操作 −
Following are the basic operations of a Binary Search Tree −
-
Search − Searches an element in a tree.
-
Insert − Inserts an element in a tree.
-
Pre-order Traversal − Traverses a tree in a pre-order manner.
-
In-order Traversal − Traverses a tree in an in-order manner.
-
Post-order Traversal − Traverses a tree in a post-order manner.
Defining a Node
定义一个节点，该节点存储一些数据以及对其左子节点和右子节点的引用。
Define a node that stores some data, and references to its left and right child nodes.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};Search Operation
每当要搜索一个元素时，从根节点开始搜索。然后，如果数据小于键值，则在左子树中搜索元素。否则，在右子树中搜索该元素。对每个节点遵循相同的算法。
Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.
Algorithm
1. START
2. Check whether the tree is empty or not
3. If the tree is empty, search is not possible
4. Otherwise, first search the root of the tree.
5. If the key does not match with the value in the root,
search its subtrees.
6. If the value of the key is less than the root value,
search the left subtree
7. If the value of the key is greater than the root value,
search the right subtree.
8. If the key is not found in the tree, return unsuccessful search.
9. ENDInsertion Operation
每当要插入一个元素时，首先找到它的适当位置。从根节点开始搜索，然后，如果数据小于键值，则在左子树中搜索空位置并插入该数据。否则，在右子树中搜索空位置并插入该数据。
Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.
Algorithm
1. START
2. If the tree is empty, insert the first element as the root node of the
tree. The following elements are added as the leaf nodes.
3. If an element is less than the root value, it is added into the left
subtree as a leaf node.
4. If an element is greater than the root value, it is added into the right
subtree as a leaf node.
5. The final leaf nodes of the tree point to NULL values as their
child nodes.
6. ENDInorder Traversal
二叉查找树中的中序遍历操作按照以下顺序访问其所有节点——
The inorder traversal operation in a Binary Search Tree visits all its nodes in the following order −
-
Firstly, we traverse the left child of the root node/current node, if any.
-
Next, traverse the current node.
-
Lastly, traverse the right child of the current node, if any.
Preorder Traversal
二叉搜索树的先序遍历操作将访问其所有节点。但是，首先打印根节点，然后是其左子树，最后是其右子树。
The preorder traversal operation in a Binary Search Tree visits all its nodes. However, the root node in it is first printed, followed by its left subtree and then its right subtree.
Postorder Traversal
与其他遍历类似，后序遍历也会访问二叉搜索树中的所有节点并显示它们。但是，首先打印左子树，然后是右子树，最后是根节点。
Like the other traversals, postorder traversal also visits all the nodes in a Binary Search Tree and displays them. However, the left subtree is printed first, followed by the right subtree and lastly, the root node.
Algorithm
1. START
2. Traverse the left subtree, recursively
3. Traverse the right subtree, recursively.
4. Then, traverse the root node
5. END