博客

首先，什么是二叉排序树（BST）?

二叉排序树(Binary Sort Tree)

具有如下性质的树

如果左子树不为空，则左子树上所有的节点的值均小于它的根节点

如果右子树不为空，则右子树上所有节点的值均大于它的根节点

它的左右子树一定是二叉排序树

如果想给一个无序数组中的数据排序，要如何排序？

首先，要找到二叉树的根节点，这里以“8”作为本树的根节点，根据性质，“3”放在“8”的左子树上，“10”放在“8”的右子树上：

“1”比“3”小，我们可以把“1”放在“3”的左子树处，“6”比“3”大，可以把它放到“3”的右子树上：

“14”比“6”和“10”都大。因此可以放到“10”的右子树上：

同理，“4”和“7”放到“6”的下面，“13”放到“14”的左边，排完后的树如下图所示：

排完后 ，数据变成：

不难发现规律，二叉排序树得到的结果是二叉树 的中序遍历结果

附上代码：

/*
二叉查找树
*/

struct node* search(struct node* root, int key) 
{ 
 // 如果root为空或者root的值和待查找的key相同，则返回root
 if (root == NULL || root->key == key) 
 return root; 
 
 // 当待查找的关键字大于根结点的值，则递归查找根结点的右子树
 if (root->key < key) 
 return search(root->right, key); 
 
 // 当待查找的关键字小于根结点的值，则递归查找根结点的左子树
 return search(root->left, key); 
}