二叉搜索树（BST）学习笔记（一）

àì夳堔傛蜴生んèń 2022-06-01 09:06 165阅读 0赞

**看完邓俊辉的《数据结构（第三版）》中二叉搜索树BST后的学习总结**

二叉搜索树（Binary Search Tree）

**![SouthEast][]**

一.循关键码访问call-by-key

**1.**二叉搜索树由一组数据项构成，数据项之间，依照各自的关键码key彼此区分。类似

于汽车的车牌号。

**2.**关键码之间支持大小比较与相等比对。

**3.**数据集合中的数据项统一地表示和实现为词条entry形式。

![SouthEast 1][]

二.二叉搜索树的特性

二叉搜索树由节点构成，每个节点中都各自存有一个词条，每一个词条都唯一的对

应于某一个关键码。为了不混淆，往往将节点-词条-关键码这三个概念等同起来，相

互指代，不加严格区分。

**1.顺序性：**任一节点均不小于/不大于其左/右**后代**

![SouthEast 2][]

**2.单调性：**BST的中序遍历序列，必然单调非降

![SouthEast 3][]

总结：BST微观上处处满足顺序性，宏观上整体满足单调性。BST的中序遍历序列，

必然单调非降。最左的为最小的，最右的为最大的。

对于遇到的每个结点x，都会比较x.key与根节点的大小，如果相等，就终止查找，否

则，决定是继续往左子树还是右子树查找。因此，整个查找过程就是从根节点开始一

直向下的一条路径，若假设树的高度是h，那么查找过程的时间复杂度就是O(h)。

**3.接口：**

**1）search()**

**2）insert()**

**3）remove()**

**三.二叉搜索树的查找**

**![SouthEast 4][]**

**查找22，22>16,跳到16的右子树，22<25，跳到25的左子树，22>19,跳到19的右子树，找到了22。**

**四.二叉搜索树的查找的Java实现**

**参考：[http://blog.csdn.net/qq\_21688757/article/details/53843724][http_blog.csdn.net_qq_21688757_article_details_53843724]**

public class TreeNode \{

private int val;

private TreeNode leftChild;  
private TreeNode rightChild;  
private TreeNode parent;  
\}  
/\*\*  
\* 非递归查找方式  
\*/

public TreeNode Search(TreeNode root,int key)\{

if(root==null)\{   
 return null;  
 \}

TreeNode pNode = root;

while (pNode != null && pNode.val != key) \{

if (key < pNode.val) \{

pNode = pNode.leftChild;

\} else \{

pNode = pNode.rightChild;

\}   
 \}   
 return pNode;   
 \}  
  
 /\*\*  
\* 获取二叉查找树中的最小关键字结点（最左端）  
\*/

public TreeNode minElemNode(TreeNode node) \{

if (node == null) \{

return null;

TreeNode pNode = node;

while (pNode.leftChild != null) \{

pNode = pNode.leftChild;

\}   
 return pNode;   
 \}

/\*\*  
\* maxElemNode: 获取二叉查找树中的最大关键字结点  
\*/

public TreeNode maxElemNode(TreeNode node) \{

if (node == null) \{

return null ;

TreeNode pNode = node;

while (pNode.rightChild != null) \{

pNode = pNode.rightChild;

\}  
return pNode;  
\}

/\*\*

\* successor: 获取给定结点在中序遍历顺序下的后继结点

中序遍历二叉树得到的是递增序列，所以后继结点就是递增序列中该结点的下一位

\* 1.该结点有右子树，则右子数中最小值即为该结点后继结点

11 -13

\* 2.该结点无右子树且该结点是父节点的左子树，则该节点的父节点则为后继结点

27 - 28

\* 3.该结点无右子树且该结点是父节点的右子树，则不断往父节点遍历。

\*/

![70][]

public TreeNode successor(TreeNode node) throws Exception \{

if (node == null) \{

return null;

// 若该结点的右子树不为空，则其后继结点就是右子树中的最小关键字结点4

if (node.rightChild != null) \{

return minElemNode(node.rightChild);   
 \}

// 若该结点右子树为空

TreeNode parentNode = node.parent;

while (parentNode != null && node == parentNode.rightChild) \{

node = parentNode;

parentNode = parentNode.parent;   
 \}   
 return parentNode;

**五.二叉搜索树的插入**

**先利用查找方法确定插入位置及方向，再将新节点作为叶子插入**

**六.二叉搜索树的删除**

**参考：**[**https://www.cnblogs.com/fingerboy/p/5493786.html**][https_www.cnblogs.com_fingerboy_p_5493786.html]

![70 1][][ ][https_www.cnblogs.com_fingerboy_p_5493786.html]

e被插入后的父亲 - 正确

[SouthEast]: /images/20220601/abddb4d22222475faaf71b3d7f893d9c.png
[SouthEast 1]: /images/20220601/d2386076d8b94550bb219fa91f99ee54.png
[SouthEast 2]: /images/20220601/9c882654498448e5be775d0082df2d05.png
[SouthEast 3]: /images/20220601/a1d03837a0fb465eaac8eb74c28df946.png
[SouthEast 4]: /images/20220601/ec1628e40f994e0eb5b9d2258161bb4a.png
[http_blog.csdn.net_qq_21688757_article_details_53843724]: http://blog.csdn.net/qq_21688757/article/details/53843724
[70]: /images/20220601/3cb9b8b807234f99bd10525213719fda.png
[https_www.cnblogs.com_fingerboy_p_5493786.html]: https://www.cnblogs.com/fingerboy/p/5493786.html
[70 1]: /images/20220601/a724023a22bd43c7b9da60718528719c.png