搜索樹支持很多動態(tài)集合操作襟锐，包括尋找谎僻，最小項娄柳，最大項等等一系列操作。所以可以使用搜索樹當(dāng)作字典或者優(yōu)先隊列艘绍。
二叉搜索樹是以一棵二叉樹來組織的赤拒。在二叉搜索樹中任意一個節(jié)點(diǎn)x來說，其左子樹中的關(guān)鍵字最大不大于x.key，其右子樹中的關(guān)鍵字最小不小于x.key挎挖。大部分搜索樹操作的最壞運(yùn)行時間與樹的高度成正比这敬。
中序遍歷
public void inorder(TreeNode node){
while(node!=null){
inorder(node.left);
System.out.println(node.key);
inorder(node.right);
}
}
得出定理：遍歷一棵n個結(jié)點(diǎn)子樹的根，調(diào)用INORDER-TREE-WALK(x)需要O(n)的時間蕉朵。
找出二叉樹中的關(guān)鍵字K
public TreeNode search(TreeNode node, int key){
while(node!=null&&node.key!=key){
if(key<node.key)
node = node.left;
else
node = node.right;
}
return node;
}
二叉搜索樹中的最小元素
public TreeNode getMin(TreeNode node){
while(node.left!=null){
node = node.left;
}
return node;
}
二叉搜索樹中的最大元素
public TreeNode getMax(TreeNode node){
while(node.right!=null)
node = node.right;
return node;
}
二叉樹的插入元素
public void insert(TreeNode root,int key){
if(root==null)
return;
TreeNode parent;
while(root!=null){
parent = root;
if(key<root.key)
root = root.left;
else if(key>root.key)
root = root.right;
else
return;
}
if(key<parent.key)
parent.left = new TreeNode(key);
else if(key > parent.key)
parent.right = new TreeNode(key);
}
二叉樹的插入就是遍歷二叉樹找到合適的點(diǎn)崔涂。然后處理該點(diǎn)與二叉樹的關(guān)系。
二叉搜索樹刪除元素
二叉搜索樹刪除元素時需要考慮幾種情況：
- 要刪除的節(jié)點(diǎn)只有左節(jié)點(diǎn)或者只有右節(jié)點(diǎn)始衅，直接把節(jié)點(diǎn)替換到它的位置
- 沒有子節(jié)點(diǎn)冷蚂，直接刪除
- 有左節(jié)點(diǎn)和右節(jié)點(diǎn)。這種情況比較復(fù)雜觅闽，把
