什么是二叉搜索树？就是左子树的值比右子树的值小，按照这样方式的排列的二叉树。
二叉搜索树也叫二叉排序树或二叉查找树。
为什么要设计二叉搜索树，从字面上就可以看出，为了方便搜索元素。如果将二叉树设计成二叉搜索树，就可以使用二分查找算法。可以将算法复杂度O(n)降到O(log2(n))。
二叉搜索树二分查找尾递归实现代码：
|
1 2 3 4 5 6 7 8 9 10 |
Position Find(ElementType X, BinTree BST) { if (!BST) return NULL: //没有树查找失败 if (X > BST->Data) return Find(X,BST->Right); //在右子树中查找 else if (X < BST->Data) return Find(X, BST->Left); //在左子树中查找 else return BST; //相等查找成功 } |
二叉搜索树二分查找非递归实现代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Position Find(ElementType X, BinTree BST) { while(BST){ if (X > BST->Data) BST = BST->Right; //在右子树中查找 else if (X < BST->Data) BST = BST->Left; //在左子树中查找 else return BST; //相等查找成功 } return NULL; //未找到 } |
算法复杂度如果二叉树都只有左子树或只有右子树（就是一条链表），这样就要找n-1次，时间复杂度为O(n)，所以二叉树要做到左右子树平衡，搜索效率才会高。
查找二叉搜索树最大和最小元素
最大元素一定是在树的最右分枝的端点上。
最小元素一定是在树的最左分枝的端点上。
递归实现查找二叉树搜索树最大最小
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Position FindMin(BinTree BST) { if (!BST) return NULL; //空二叉树 else if(!BST->Left) return BST; //找到 else return FindMin(BST->Left); } Position FindMax(BinTree BST) { if (!BST) return NULL; //空二叉树 else if(!BST->Right) return BST; //找到 else return FindMin(BST->Right); } |
循环实现查找二叉树搜索树最大最小
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Position FindMin(BinTree BST) { if (BST) while(BST->Left) BST = BST->Left; return BST; } Position FindMax(BinTree BST) { if (BST) while(BST->Right) BST = BST->Right; return BST; } |